In combinatorics, tripod packing is a problem of finding many disjoint tripods in a three-dimensional grid, where a tripod is an infinite polycube, the union of the grid cubes along three positive axis-aligned rays with a shared apex.
Several problems of tiling and packing tripods and related shapes were formulated in 1967 by Sherman K. Stein. Stein originally called the tripods of this problem "semicrosses", and they were also called Stein corners by Solomon W. Golomb. A collection of disjoint tripods can be represented compactly as a monotonic matrix, a square matrix whose nonzero entries increase along each row and column and whose equal nonzero entries are placed in a monotonic sequence of cells, and the problem can also be formulated in terms of finding sets of triples satisfying a compatibility condition called "2-comparability", or of finding compatible sets of triangles in a convex polygon.
The best lower bound known for the number of tripods that can have their apexes packed into an
n x n x n
\Omega(n1.546)
n2/\exp\Omega(log*n)
The coordinates
(xi,yi,zi)
Another equivalent two-dimensional version of the question asks how many cells of an
n x n
1
n
1
n
i
(xi,yi,zi)
zi
(xi,yi)
The problem is also equivalent to finding as many triangles as possible among the vertices of a convex polygon, such that no two triangles that share a vertex have nested angles at that vertex. This triangle-counting problem was posed by Peter Braß and its equivalence to tripod packing was observed by Aronov et al.
It is straightforward to find a solution to the tripod packing problem with
\Omega(n3/2)
k=\lfloor\sqrt{n}\rfloor
\Omega(n3/2)
After several earlier improvements to this naïve bound, Gowers and Long found solutions to the tripod problem of cardinality
\Omega(n1.546)
From any solution to the tripod packing problem, one can derive a balanced tripartite graph whose vertices are three copies of the numbers from
0
n-1
n x n x n
o(n2)
n2/\exp\Omega(log*n)
o(n2)
An argument of Dean Hickerson shows that, because tripods cannot pack space with constant density, the same is true for analogous problems in higher dimensions.
For small instances of the tripod problem, the exact solution is known. The numbers of tripods that can be packed into an
n x n x n
n\le11
5 x 5 x 5
The number of distinct monotonic matrices of order
n
n=1,2,3,...