Tripod packing

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 grid cubes, as the parameter n varies. The coordinates (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\times n\times n cube, all of these coordinates can be assumed to be integers in the range from 1 to 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\times n array of square cells (indexed from 1 to n) can be filled in by the numbers from 1 to 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 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) can be transformed into a monotonic matrix by placing the number z_i in array cell (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 \Omega(n^{3/2}) tripods: For k=\lfloor\sqrt{n}\rfloor, the \Omega(n^{3/2}) triples \bigl\{ (ak+b+1,bk+c+1,ak+c+1) \mathrel{\big|} a,b,c\in[0,k-1]\bigr\} are 2-comparable. For example, for n=9 and k=3 this construction produces a 9\times 9 monotonic matrix with 27 entries: \begin{pmatrix} &&&&&&7&8&9\\ &&&7&8&9&&&\\ 7&8&9&&&&&&\\ &&&&&&4&5&6\\ &&&4&5&6&&&\\ 4&5&6&&&&&&\\ &&&&&&1&2&3\\ &&&1&2&3&&&\\ 1&2&3&&&&&&\\ \end{pmatrix} After several earlier improvements to this naïve bound, Gowers and Long found solutions to the tripod problem of cardinality \Omega(n^{1.546}). As they observe, any tripod packing having more than n^{1.5} tripods for its problem size n could be expanded, through a recursive construction resembling the Kronecker product of matrices, into a family of solutions with exponent greater than 1.5. However, their searches did not find a suitable tripod packing to start this recursive construction. Instead, they formulate a geometric relaxation of the problem in which one must pack 2-comparable cuboids within a larger cuboid, allowing the cuboids to have coordinates that are real numbers rather than integers. They find five cuboids, distorted from the unit cuboids describing the five-tripod solution to the n=3 tripod problem, for which recursively expanding these cuboids into copies of the same five cuboids yields solutions of the geometric problem that can be translated back into tripod packings of cardinality \Omega(n^{1.546}). The exponent of this solution was calculated numerically as 3\alpha where \alpha is the largest real number for which 1\le \sup_{0 ==Upper bounds==

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 to n-1 (one for each of the three coordinates) with a triangle of edges connecting the three vertices corresponding to the coordinates of the apex of each tripod. There are no other triangles in these graphs (they are locally linear graphs) because any other triangle would lead to a violation of 2-comparability. Therefore, by the known upper bounds to the Ruzsa–Szemerédi problem (one version of which is to find the maximum density of edges in a balanced tripartite locally linear graph), the maximum number of disjoint tripods that can be packed in an n\times n\times n grid is o(n^2), and more precisely n^2/\exp\Omega(\log^* n). Although Tiskin writes that "tighter analysis of the parameters" can produce a bound that is less than quadratic by a polylogarithmic factor, he does not supply details and his proof that the number is o(n^2) uses only the same techniques that are known for the Ruzsa–Szemerédi problem, so this stronger claim appears to be a mistake. 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. ==Small instances==

For small instances of the tripod problem, the exact solution is known. The numbers of tripods that can be packed into an n\times n\times n cube, for n\le 11, are: For instance, the figure shows the 11 tripods that can be packed into a 5\times 5\times 5 cube. The number of distinct monotonic matrices of order n, for n=1,2,3,\dots is ==References==