Tripod packing

Last updated July 31, 2023

Unsolved problem in mathematics:

How many tripods can have their apexes packed into a given cube?

Several problems of tiling and packing tripods and related shapes were formulated in 1967 by Sherman K. Stein.^[2] Stein originally called the tripods of this problem "semicrosses", and they were also called Stein corners by Solomon W. Golomb.^[3] 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,^[4] 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.^[1]

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^{1.546})$ , and the best upper bound is $n^{2}/\exp \Omega (\log ^{*}n)$ , both expressed in big Omega notation.^[1]^[5]

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.^[1]

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.^[1]

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ß^[6] and its equivalence to tripod packing was observed by Aronov et al.^[1]

Lower bounds

It is straightforward to find a solution to the tripod packing problem with $\Omega (n^{3/2})$ tripods.^[1] For instance, for $k=\lfloor {\sqrt {n}}\rfloor$ , the $\Omega (n^{3/2})$ triples

{\bigl \{}(ak+b+1,bk+c+1,ak+c+1){\big |}a,b,c\in [0,k-1]{\bigr \}}

are 2-comparable.

After several earlier improvements to this naïve bound,^[7]^[8]^[9] Gowers and Long found solutions to the tripod problem of cardinality $\Omega (n^{1.546})$ .^[5]

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)$ .^[1]^[5]^[9]^[10] Although Tiskin writes that "tighter analysis of the parameters" can produce a bound that is less than quadratic by a polylogarithmic factor,^[9] 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.^[1]

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.^[4]

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\leq 11$ , are:^[9]^[11]^[12]^[13]

1, 2, 5, 8, 11, 14, 19, 23, 28, 32, 38, ...

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^[14]

2, 19, 712, 87685, 31102080, 28757840751, ...

Related Research Articles

Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory.

<span class="mw-page-title-main">Packing problems</span> Problems which attempt to find the most efficient way to pack objects into containers

Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.

<span class="mw-page-title-main">Arrangement of lines</span> Subdivision of the plane by lines

In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Problems of counting the features of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

In discrete geometry and discrepancy theory, the Heilbronn triangle problem is a problem of placing points in the plane, avoiding triangles of small area. It is named after Hans Heilbronn, who conjectured that, no matter how points are placed in a given area, the smallest triangle area will be at most inversely proportional to the square of the number of points. His conjecture was proven false, but the asymptotic growth rate of the minimum triangle area remains unknown.

<span class="mw-page-title-main">No-three-in-line problem</span> Geometry problem on grid points

The no-three-in-line problem in discrete geometry asks how many points can be placed in the $grid so that no three points lie on the same line. The problem concerns lines of all slopes, not only those aligned with the grid. It was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".$

<span class="mw-page-title-main">Guillotine cutting</span> Process of producing small rectangular items of fixed dimensions

Guillotine cutting is the process of producing small rectangular items of fixed dimensions from a given large rectangular sheet, using only guillotine-cuts. A guillotine-cut is a straight bisecting line going from one edge of an existing rectangle to the opposite edge, similarly to a paper guillotine.

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In number theory, a Sidon sequence is a sequence $of natural numbers in which all pairwise sums are different. Sidon sequences are also called Sidon sets; they are named after the Hungarian mathematician Simon Sidon, who introduced the concept in his investigations of Fourier series.$

Imre Z. Ruzsa is a Hungarian mathematician specializing in number theory.

András Hajnal was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.

In discrete geometry, the Erdős distinct distances problem states that every set of points in the plane has a nearly-linear number of distinct distances. It was posed by Paul Erdős in 1946 and almost proven by Larry Guth and Nets Katz in 2015.

In affine geometry, a cap set is a subset of $with no three elements in a line. The cap set problem is the problem of finding the size of the largest possible cap set, as a function of . The first few cap set sizes are 1, 2, 4, 9, 20, 45, 112, ....$

In mathematics, a square-difference-free set is a set of natural numbers, no two of which differ by a square number. Hillel Furstenberg and András Sárközy proved in the late 1970s the Furstenberg–Sárközy theorem of additive number theory showing that, in a certain sense, these sets cannot be very large. In the game of subtract a square, the positions where the next player loses form a square-difference-free set. Another square-difference-free set is obtained by doubling the Moser–de Bruijn sequence.

In graph theory, the graph removal lemma states that when a graph contains few copies of a given subgraph, then all of the copies can be eliminated by removing a small number of edges. The special case in which the subgraph is a triangle is known as the triangle removal lemma.

<span class="mw-page-title-main">Ruzsa–Szemerédi problem</span>

In combinatorial mathematics and extremal graph theory, the Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in a graph in which every edge belongs to a unique triangle. Equivalently it asks for the maximum number of edges in a balanced bipartite graph whose edges can be partitioned into a linear number of induced matchings, or the maximum number of triples one can choose from $points so that every six points contain at most two triples. The problem is named after Imre Z. Ruzsa and Endre Szemerédi, who first proved that its answer is smaller than by a slowly-growing factor.$

In graph theory, an induced matching or strong matching is a subset of the edges of an undirected graph that do not share any vertices and includes every edge connecting any two vertices in the subset.

<span class="mw-page-title-main">Locally linear graph</span> Graph where every edge is in one triangle

In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs. Their triangles form the hyperedges of triangle-free 3-uniform linear hypergraphs and the blocks of certain partial Steiner triple systems, and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems.

In probability theory, the van den Berg–Kesten (BK) inequality or van den Berg–Kesten–Reimer (BKR) inequality states that the probability for two random events to both happen, and at the same time one can find "disjoint certificates" to show that they both happen, is at most the product of their individual probabilities. The special case for two monotone events was first proved by van den Berg and Kesten in 1985, who also conjectured that the inequality holds in general, not requiring monotonicity. Reimer later proved this conjecture. The inequality is applied to probability spaces with a product structure, such as in percolation problems.

References

1 2 3 4 5 6 7 8 9 10 Aronov, Boris; Dujmović, Vida; Morin, Pat; Ooms, Aurélien; Schultz Xavier da Silveira, Luís Fernando (2019), "More Turán-type theorems for triangles in convex point sets", Electronic Journal of Combinatorics , 26 (1): P1.8
↑ Stein, S. K. (1967), "Factoring by subsets", Pacific Journal of Mathematics , 22: 523–541, doi: 10.2140/pjm.1967.22.523 , MR 0219435
↑ Golomb, S. W. (1969), "A general formulation of error metrics", IEEE Transactions on Information Theory , IT-15: 425–426, doi:10.1109/tit.1969.1054308, MR 0243902
1 2 Stein, Sherman K.; Szabó, Sándor (1994), Algebra and Tiling: Homomorphisms in the Service of Geometry, Carus Mathematical Monographs, vol. 25, Washington, DC: Mathematical Association of America, p. 97, ISBN 0-88385-028-1, MR 1311249
1 2 3 Gowers, W. T.; Long, J. (January 2021), "The length of an $s$ -increasing sequence of $r$ -tuples", Combinatorics, Probability and Computing : 1–36, arXiv: 1609.08688 , doi:10.1017/s0963548320000371
↑ Braß, Peter (2004), "Turán-type extremal problems for convex geometric hypergraphs", in Pach, János (ed.), Towards a theory of geometric graphs, Contemporary Mathematics, vol. 342, Providence, Rhode Island: American Mathematical Society, pp. 25–33, doi:10.1090/conm/342/06128, MR 2065250
↑ Hamaker, William; Stein, Sherman (1984), "Combinatorial packing of $\mathbf {R} ^{3}$ by certain error spheres", IEEE Transactions on Information Theory , 30 (2, part 2): 364–368, doi:10.1109/TIT.1984.1056868, MR 0754867
↑ Stein, Sherman K. (March 1995), "Packing tripods", Mathematical entertainments, The Mathematical Intelligencer , 17 (2): 37–39, doi:10.1007/bf03024896 . Reprinted in Gale, David (1998), Tracking the Automatic ANT, Springer-Verlag, pp. 131–136, doi:10.1007/978-1-4612-2192-0, ISBN 0-387-98272-8, MR 1661863
1 2 3 4 Tiskin, Alexander (2007), "Packing tripods: narrowing the density gap", Discrete Mathematics , 307 (16): 1973–1981, doi: 10.1016/j.disc.2004.12.028 , MR 2326159
↑ Loh, Po-Shen (2015), Directed paths: from Ramsey to Ruzsa and Szemerédi, arXiv: 1505.07312
↑ Szabó, Sándor (2013), "Monotonic matrices and clique search in graphs", Ann. Univ. Sci. Budapest Sect. Comput., 41: 307–322, doi:10.1080/00455091.2001.10717569, MR 3129145
↑ Östergård, Patric R. J.; Pöllänen, Antti (2019), "New results on tripod packings" (PDF), Discrete & Computational Geometry , 61 (2): 271–284, doi:10.1007/s00454-018-0012-2, MR 3903789
↑ Sloane, N. J. A. (ed.), "SequenceA070214", The On-Line Encyclopedia of Integer Sequences , OEIS Foundation
↑ Sloane, N. J. A. (ed.), "SequenceA086976", The On-Line Encyclopedia of Integer Sequences , OEIS Foundation

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[admos-1] 1 2 3 4 5 6 7 8 9 10 Aronov, Boris; Dujmović, Vida; Morin, Pat; Ooms, Aurélien; Schultz Xavier da Silveira, Luís Fernando (2019), "More Turán-type theorems for triangles in convex point sets", Electronic Journal of Combinatorics , 26 (1): P1.8

[s67-2] Stein, S. K. (1967), "Factoring by subsets", Pacific Journal of Mathematics , 22: 523–541, doi: 10.2140/pjm.1967.22.523 , MR 0219435

[g-3] Golomb, S. W. (1969), "A general formulation of error metrics", IEEE Transactions on Information Theory , IT-15: 425–426, doi:10.1109/tit.1969.1054308, MR 0243902

[ss-4] 1 2 Stein, Sherman K.; Szabó, Sándor (1994), Algebra and Tiling: Homomorphisms in the Service of Geometry, Carus Mathematical Monographs, vol. 25, Washington, DC: Mathematical Association of America, p. 97, ISBN 0-88385-028-1, MR 1311249

[gl-5] 1 2 3 Gowers, W. T.; Long, J. (January 2021), "The length of an $s$ -increasing sequence of $r$ -tuples", Combinatorics, Probability and Computing : 1–36, arXiv: 1609.08688 , doi:10.1017/s0963548320000371

[b-6] Braß, Peter (2004), "Turán-type extremal problems for convex geometric hypergraphs", in Pach, János (ed.), Towards a theory of geometric graphs, Contemporary Mathematics, vol. 342, Providence, Rhode Island: American Mathematical Society, pp. 25–33, doi:10.1090/conm/342/06128, MR 2065250

[hs-7] Hamaker, William; Stein, Sherman (1984), "Combinatorial packing of $\mathbf {R} ^{3}$ by certain error spheres", IEEE Transactions on Information Theory , 30 (2, part 2): 364–368, doi:10.1109/TIT.1984.1056868, MR 0754867

[s95-8] Stein, Sherman K. (March 1995), "Packing tripods", Mathematical entertainments, The Mathematical Intelligencer , 17 (2): 37–39, doi:10.1007/bf03024896 . Reprinted in Gale, David (1998), Tracking the Automatic ANT, Springer-Verlag, pp. 131–136, doi:10.1007/978-1-4612-2192-0, ISBN 0-387-98272-8, MR 1661863

[t-9] 1 2 3 4 Tiskin, Alexander (2007), "Packing tripods: narrowing the density gap", Discrete Mathematics , 307 (16): 1973–1981, doi: 10.1016/j.disc.2004.12.028 , MR 2326159

[l-10] Loh, Po-Shen (2015), Directed paths: from Ramsey to Ruzsa and Szemerédi, arXiv: 1505.07312

[s13-11] Szabó, Sándor (2013), "Monotonic matrices and clique search in graphs", Ann. Univ. Sci. Budapest Sect. Comput., 41: 307–322, doi:10.1080/00455091.2001.10717569, MR 3129145

[op-12] Östergård, Patric R. J.; Pöllänen, Antti (2019), "New results on tripod packings" (PDF), Discrete & Computational Geometry , 61 (2): 271–284, doi:10.1007/s00454-018-0012-2, MR 3903789

[A070214-13] Sloane, N. J. A. (ed.), "SequenceA070214", The On-Line Encyclopedia of Integer Sequences , OEIS Foundation

[A086976-14] Sloane, N. J. A. (ed.), "SequenceA086976", The On-Line Encyclopedia of Integer Sequences , OEIS Foundation

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]