Embalaje de trípode

Problema no resuelto en matemáticas :

¿Cuántos trípodes pueden tener sus vértices empaquetados en un cubo dado?

(más problemas sin resolver en matemáticas)

Un trípode de embalaje y su correspondiente matriz monótona. Este ejemplo corresponde al conjunto 2-comparable {(1,1,1), (1,3,3), (2,1,2), (2,4,3), (3,1,4), (3, 4, 5), (4, 2, 1), (4, 5, 3), (5, 2, 2), (5, 3, 4), (5, 5, 5)}. ^[1]

En combinatoria , el empaquetamiento de trípode es un problema de encontrar muchos trípodes disjuntos en una cuadrícula tridimensional, donde un trípode es un policubo infinito , la unión de los cubos de la cuadrícula a lo largo de tres rayos alineados con ejes positivos con un ápice compartido. ^[1]

En 1967, Sherman K. Stein formuló varios problemas de alicatado y empaquetado de trípodes y formas relacionadas . ^[2] Stein originalmente llamó a los trípodes de este problema "semicruzos", y también fueron llamados esquinas de Stein por Solomon W. Golomb . ^[3] Una colección de trípodes disjuntos se puede representar de forma compacta como una matriz monótona , una matriz cuadrada cuyas entradas distintas de cero aumentan a lo largo de cada fila y columna y cuyas entradas iguales distintas de cero se colocan en una secuencia monótona de celdas, ^[4]y el problema también se puede formular en términos de encontrar conjuntos de triples que satisfagan una condición de compatibilidad llamada "2-comparabilidad", o de encontrar conjuntos de triángulos compatibles en un polígono convexo. ^[1]

El mejor límite inferior conocido por la cantidad de trípodes que pueden tener sus vértices empaquetados en una cuadrícula es , y el mejor límite superior , ambos expresados ​​en notación Omega grande . ^{[1] [5]}${\displaystyle n\times n\times n}$${\displaystyle \Omega (n^{1.546})}$${\displaystyle n^{2}/\exp \Omega (\log ^{*}n)}$

Problemas equivalentes

Las coordenadas de los vértices de una solución al problema del trípode forman un conjunto de triples comparables en 2 , donde dos triples se definen como comparables en 2 si hay al menos dos coordenadas donde una triple es más pequeña que la otra, o en al menos dos coordenadas donde un triple es más grande que el otro. Esta condición asegura que los trípodes definidos a partir de estos triples no tengan rayos que se crucen. ^[1]${\displaystyle (x_{i},y_{i},z_{i})}$

Otra versión bidimensional equivalente de la pregunta pregunta cuántas celdas de una matriz de celdas cuadradas (indexadas de a ) se pueden completar con los números de a de tal manera que las celdas no vacías de cada fila y cada columna de la matriz forma secuencias de números estrictamente crecientes, y las posiciones que contienen cada valor forman una cadena monótona dentro de la matriz. Una matriz con estas propiedades se llama matriz monótona. Una colección de trípodes disjuntos con vértices se puede transformar en una matriz monótona colocando el número en una celda de matriz y viceversa. ^[1]${\displaystyle n\times n}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle i}$${\displaystyle (x_{i},y_{i},z_{i})}$${\displaystyle z_{i}}$${\displaystyle (x_{i},y_{i})}$

El problema también es equivalente a encontrar tantos triángulos como sea posible entre los vértices de un polígono convexo, de modo que no haya dos triángulos que compartan un vértice con ángulos anidados en ese vértice. Peter Braß ^[6] planteó este problema de conteo de triángulos y Aronov et al. ^[1]

Límites inferiores

Es sencillo encontrar una solución al problema de empaquetado del trípode con trípodes. ^[1] Por ejemplo, para los triples${\displaystyle \Omega (n^{3/2})}$${\displaystyle k=\lfloor {\sqrt {n}}\rfloor }$${\displaystyle \Omega (n^{3/2})}$

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

son 2 comparables.

Después de varias mejoras anteriores a este límite ingenuo, ^{[7] [8] [9]} Gowers y Long encontraron soluciones al problema del trípode de cardinalidad . ^[5]${\displaystyle \Omega (n^{1.546})}$

Límites superiores

De cualquier solución al problema de empaquetamiento del trípode, se puede derivar un grafo tripartito balanceado cuyos vértices son tres copias de los números de a (uno para cada una de las tres coordenadas) con un triángulo de aristas que conecta los tres vértices correspondientes a las coordenadas de la ápice de cada trípode. No hay otros triángulos en estos gráficos (son gráficos localmente lineales ) porque cualquier otro triángulo conduciría a una violación de la comparabilidad 2. Por lo tanto, según los límites superiores conocidos del problema de Ruzsa-Szemerédi (una versión del cual es encontrar la densidad máxima de bordes en un gráfico localmente lineal tripartito balanceado), el número máximo de trípodes disjuntos que se pueden empaquetar en una cuadrícula es , y más precisamente .${\displaystyle 0}$${\displaystyle n-1}$${\displaystyle n\times n\times n}$${\displaystyle o(n^{2})}$${\displaystyle n^{2}/\exp \Omega (\log ^{*}n)}$^{[1] [5] [9] [10]} Aunque Tiskin escribe que "un análisis más estricto de los parámetros" puede producir un límite que es menor que cuadrático por un factor polilogarítmico, ^[9] no proporciona detalles y su prueba de que el El númeroutiliza solo las mismas técnicas que se conocen para el problema Ruzsa-Szemerédi, por lo que esta afirmación más fuerte parece ser un error. ^[1]${\displaystyle o(n^{2})}$

Un argumento de Dean Hickerson muestra que, debido a que los trípodes no pueden llenar espacio con densidad constante, lo mismo es cierto para problemas análogos en dimensiones superiores. ^[4]

Pequeñas instancias

Para casos pequeños del problema del trípode, se conoce la solución exacta. Los números de trípodes que se pueden empaquetar en un cubo son: ^{[9] [11] [12] [13]}${\displaystyle n\times n\times n}$${\displaystyle n\leq 11}$

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

Por ejemplo, la figura muestra los 11 trípodes que se pueden empaquetar en un cubo.${\displaystyle 5\times 5\times 5}$

El número de matrices monótonas distintas de orden , para es ^[14]${\displaystyle n}$${\displaystyle n=1,2,3,\dots }$

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

Referencias

1. Aronov, Boris ; Dujmović, Vida ; Morin, Pat ; Ooms, Aurélien; Schultz Xavier da Silveira, Luís Fernando (2019), "Más teoremas tipo Turán para triángulos en conjuntos de puntos convexos" , Electronic Journal of Combinatorics , 26 (1): P1.8
2. Stein, SK (1967), "Factorización por subconjuntos" , Pacific Journal of Mathematics , 22 : 523–541, doi : 10.2140 / pjm.1967.22.523 , MR 0219435 
3. Golomb, SW (1969), "Una formulación general de métricas de error", IEEE Transactions on Information Theory , IT-15: 425–426, doi : 10.1109 / tit.1969.1054308 , MR 0243902 
4. Stein, Sherman K .; Szabó, Sándor (1994), Algebra and Tiling: Homomorphisms in the Service of Geometry , Carus Mathematical Monographs, 25 , Washington, DC: Asociación Matemática de América, p. 97, ISBN 0-88385-028-1, MR  1311249
5. Gowers, WT ; Long, J. (enero de 2021), "La longitud de una secuencia creciente de tuplas", Combinatoria, probabilidad y computación : 1–36, arXiv : 1609.08688 , doi : 10.1017 / s0963548320000371${\displaystyle s}$${\displaystyle r}$
6. Braß, Peter (2004), "Problemas extremos de tipo Turán para hipergráficos geométricos convexos", en Pach, János (ed.), Hacia una teoría de gráficos geométricos , Matemáticas contemporáneas, 342 , Providence, Rhode Island: American Mathematical Society, págs. 25–33, doi : 10.1090 / conm / 342/06128 , MR 2065250 
7. Hamaker, William; Stein, Sherman (1984), "Empaquetamiento combinatorio de determinadas esferas de error", IEEE Transactions on Information Theory , 30 (2, parte 2): 364–368, doi : 10.1109 / TIT.1984.1056868 , MR 0754867${\displaystyle \mathbf {R} ^{3}}$ 
8. Stein, Sherman K. (marzo de 1995), "Trípodes de embalaje", Entretenimiento matemático, The Mathematical Intelligencer , 17 (2): 37–39, doi : 10.1007 / bf03024896. Reimpreso en Gale, David (1998), Tracking the Automatic ANT , Springer-Verlag, págs. 131-136, doi : 10.1007 / 978-1-4612-2192-0 , ISBN 0-387-98272-8, MR  1661863
9. Tiskin, Alexander (2007), "Trípodes de embalaje: estrechamiento de la brecha de densidad", Matemáticas discretas , 307 (16): 1973-1981, doi : 10.1016 / j.disc.2004.12.028 , MR 2326159 
10. Loh, Po-Shen (2015), Caminos dirigidos: de Ramsey a Ruzsa y Szemerédi , arXiv : 1505.07312
11. Szabó, Sándor (2013), "Matrices monotónicas y búsqueda de camarillas en gráficos", Ann. Univ. Sci. Budapest. Secta. Computación. , 41 : 307–322, doi : 10.1080 / 00455091.2001.10717569 , MR 3129145 
12. Östergård, Patric RJ; Pöllänen, Antti (2019), "Nuevos resultados sobre empaquetaduras de trípode" (PDF) , Geometría discreta y computacional , 61 (2): 271–284, doi : 10.1007 / s00454-018-0012-2 , MR 3903789  
13. Sloane, N. J. A. (ed.), "Secuencia A070214" , La enciclopedia en línea de secuencias de enteros , Fundación OEIS
14. Sloane, N. J. A. (ed.), "Secuencia A086976" , La enciclopedia en línea de secuencias de enteros , Fundación OEIS