Tripod packing

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 × n × n {\displaystyle n\times n\times n} grid is Ω ( n 1.546 ) {\displaystyle \Omega (n^{1.546})} , and the best upper bound is n 2 2 Ω ( log ∗ ⁡ n ) , {\displaystyle {\frac {n^{2}}{2^{\Omega (\log ^{*}n)}}},} both expressed in big Omega notation.

Equivalent problems A tripod is an infinite polycube, the union of sets of cubes in a three-dimensional grid that lie along three positive axis-aligned rays, all starting from the same grid cube. The cube at which these rays start is the apex of the tripod. The tripod packing problem asks for the maximum number of disjoint tripods, all of whose apexes lie within a larger cube consisting of n 3 {\displaystyle n^{3}} grid cubes, as the parameter n {\displaystyle n} varies. The coordinates ( x i , y i , z i ) {\displaystyle (x_{i},y_{i},z_{i})} of the apexes of a solution to the tripod problem form a 2-comparable sets of triples, where two triples are defined as being 2-comparable if there are either at least two coordinates where one triple is smaller than the other, or at least two coordinates where one triple is larger than the other. This condition ensures that the tripods defined from these triples do not have intersecting rays. For packing tripods in an n × n × n {\displaystyle n\times n\times n} cube, all of these coordinates can be assumed to be integers in the range from 1 {\displaystyle 1} to n {\displaystyle n} . Thus, an equivalent version of the problem asks for the maximum size of a 2-comparable set of triples of numbers in this range. Another equivalent version of the question, in two dimensions rather than three, asks how many cells of an n × n {\displaystyle n\times n} array of square cells (indexed from 1 {\displaystyle 1} to n {\displaystyle n} ) can be filled in by the numbers from 1 {\displaystyle 1} to n {\displaystyle n} in such a way that the non-empty cells of each row and each column of the array form strictly increasing sequences of numbers, and the positions holding each value i {\displaystyle i} form a monotonic chain within the array. An array with these properties is called a monotonic matrix. A collection of disjoint tripods with apexes ( x i , y i , z i ) {\displaystyle (x_{i},y_{i},z_{i})} can be transformed into a monotonic matrix by placing the number z i {\displaystyle z_{i}} in array cell ( x i , y i ) {\displaystyle (x_{i},y_{i})} and vice versa. 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.

Lower bounds It is straightforward to find a solution to the tripod packing problem with Ω ( n 3 / 2 ) {\displaystyle \Omega (n^{3/2})} tripods: For k = ⌊ n ⌋ {\displaystyle k=\lfloor {\sqrt {n}}\rfloor } , the Ω ( n 3 / 2 ) {\displaystyle \Omega (n^{3/2})} triples

… excerpt ends here. Continue reading the full article.