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\times n\times n$ grid is $\Omega(n^)$, and the best upper bound is $n^2/\exp \Omega(\log^* n)$, both expressed in big Omega notation.

Equivalent problems

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.

Another equivalent two-dimensional version of the question 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^)$ tripods. For instance, for $k=\lfloor\sqrt\rfloor$, the $\Omega(n^)$ triples
$\bigl\$
are 2-comparable.

After several earlier improvements to this naïve bound, Gowers and Long found solutions to the tripod problem of cardinality $\Omega(n^)$.

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

{{reflist, refs=

{{cite OEIS, A070214, mode=cs2

{{cite OEIS, A086976, mode=cs2

{{citation
, last1 = Aronov , first1 = Boris , author1-link = Boris Aronov
, last2 = Dujmović , first2 = Vida , author2-link = Vida Dujmović
, last3 = Morin , first3 = Pat , author3-link = Pat Morin
, last4 = Ooms , first4 = Aurélien
, last5 = Schultz Xavier da Silveira , first5 = Luís Fernando
, issue = 1
, journal = Electronic Journal of Combinatorics
, page = P1.8
, title = More Turán-type theorems for triangles in convex point sets
, url = https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p8
, volume = 26
, year = 2019

{{citation
, last = Braß , first = Peter
, editor-last = Pach , editor-first = János , editor-link = János Pach
, contribution = Turán-type extremal problems for convex geometric hypergraphs
, doi = 10.1090/conm/342/06128
, mr = 2065250
, pages = 25–33
, publisher = American Mathematical Society , location = Providence, Rhode Island
, series = Contemporary Mathematics
, title = Towards a theory of geometric graphs
, volume = 342
, year = 2004

{{citation
, last = Golomb , first = S. W. , authorlink = Solomon W. Golomb
, doi = 10.1109/tit.1969.1054308
, journal = IEEE Transactions on Information Theory
, mr = 0243902
, pages = 425–426
, title = A general formulation of error metrics
, volume = IT-15
, year = 1969

{{citation
, last1 = Gowers , first1 = W. T. , author1-link = Timothy Gowers
, last2 = Long , first2 = J.
, arxiv = 1609.08688
, date = January 2021
, doi = 10.1017/s0963548320000371
, journal = Combinatorics, Probability and Computing
, pages = 1–36
, title = The length of an $s$-increasing sequence of $r$-tuples

{{citation
, last1 = Hamaker , first1 = William
, last2 = Stein , first2 = Sherman
, doi = 10.1109/TIT.1984.1056868
, issue = 2, part 2
, journal = IEEE Transactions on Information Theory
, mr = 754867
, pages = 364–368
, title = Combinatorial packing of $\mathbf{R}^3$ by certain error spheres
, volume = 30
, year = 1984

{{citation
, last = Loh , first = Po-Shen
, arxiv = 1505.07312
, title = Directed paths: from Ramsey to Ruzsa and Szemerédi
, year = 2015

{{citation
, last1 = Östergård , first1 = Patric R. J.
, last2 = Pöllänen , first2 = Antti
, doi = 10.1007/s00454-018-0012-2
, issue = 2
, journal = Discrete & Computational Geometry
, mr = 3903789
, pages = 271–284
, title = New results on tripod packings
, volume = 61
, year = 2019, url = https://research.aalto.fi/files/27004339/ELEC_ostergard_et_al_New_Results_Springer.pdf

{{citation
, last = Stein , first = S. K. , authorlink = Sherman K. Stein
, journal = Pacific Journal of Mathematics
, mr = 0219435
, pages = 523–541
, title = Factoring by subsets
, url = https://projecteuclid.org/euclid.pjm/1102992103
, volume = 22
, year = 1967
, doi = 10.2140/pjm.1967.22.523, doi-access = free

{{citation
, last = Stein , first = Sherman K. , authorlink = Sherman K. Stein
, date = March 1995
, department = Mathematical entertainments
, doi = 10.1007/bf03024896
, issue = 2
, journal = The Mathematical Intelligencer
, pages = 37–39
, title = Packing tripods
, volume = 17. Reprinted in {{citation
, last = Gale , first = David , authorlink = David Gale
, doi = 10.1007/978-1-4612-2192-0
, isbn = 0-387-98272-8
, mr = 1661863
, pages = 131–136
, publisher = Springer-Verlag
, title = Tracking the Automatic ANT
, year = 1998

{{citation
, last1 = Stein , first1 = Sherman K. , author1-link = Sherman K. Stein
, last2 = Szabó , first2 = Sándor
, isbn = 0-88385-028-1
, mr = 1311249
, page = 97
, publisher = Mathematical Association of America , location = Washington, DC
, series = Carus Mathematical Monographs
, title = Algebra and Tiling: Homomorphisms in the Service of Geometry
, title-link = Algebra and Tiling: Homomorphisms in the Service of Geometry
, volume = 25
, year = 1994

{{citation
, last = Szabó , first = Sándor
, journal = Ann. Univ. Sci. Budapest. Sect. Comput.
, mr = 3129145
, pages = 307–322
, title = Monotonic matrices and clique search in graphs
, volume = 41
, year = 2013
, doi = 10.1080/00455091.2001.10717569

{{citation
, last = Tiskin , first = Alexander
, doi = 10.1016/j.disc.2004.12.028
, issue = 16
, journal = Discrete Mathematics
, mr = 2326159
, pages = 1973–1981
, title = Packing tripods: narrowing the density gap
, volume = 307
, year = 2007, doi-access = free

Packing problems
Unsolved problems in geometry