Embalaje del trípode

Problema no resuelto en matemáticas :

¿Cuántos trípodes pueden tener sus vértices dentro de un cubo determinado?

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

Una empaquetadura de trípode y su correspondiente matriz monótona. Este ejemplo corresponde al conjunto de 2 comparables {(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 separados 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 vértice compartido. ^[1]

En 1967 , Sherman K. Stein formuló varios problemas de colocación y embalaje de trípodes y formas relacionadas . ^[2] Stein originalmente llamó a los trípodes de este problema "semicruces", y Solomon W. Golomb también los llamó esquinas Stein . ^[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 puede También puede formularse en términos de encontrar conjuntos de triples que satisfagan una condición de compatibilidad llamada "comparabilidad 2", o de encontrar conjuntos compatibles de triángulos en un polígono convexo. ^[1]

El mejor límite inferior conocido para el número de trípodes que pueden tener sus vértices empaquetados en una cuadrícula es , y el mejor límite superior es , ambos expresados ​​en notación Omega grande . ^{[ 15]} ${\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 conjuntos de triples 2-comparables , donde dos triples se definen como 2-comparables si hay al menos dos coordenadas donde un triple es más pequeño que el otro, o en al menos dos coordenadas donde una tripleta es mayor que la otra. 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 desde hasta ) se pueden completar con los números desde hasta 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 separados con vértices se puede transformar en una matriz monótona colocando el número en la celda de la 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 equivale 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 que tengan ángulos anidados en ese vértice. Este problema de conteo de triángulos fue planteado por Peter Braß ^[6] y Aronov et al. observaron su equivalencia con el embalaje de trípode. ^[1]

límites inferiores

Es sencillo encontrar una solución al problema del embalaje 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 \}}}$$

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 la cardinalidad . ^[5] ${\displaystyle \Omega (n^{1.546})}$

Límites superiores

De cualquier solución al problema del embalaje del trípode, se puede derivar un gráfico tripartito equilibrado 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 del vértice 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 con 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 aristas en un gráfico tripartito localmente lineal equilibrado), el número máximo de trípodes disjuntos que se pueden empaquetar en una cuadrícula es , y más precisamente . ^{[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 ni su prueba de que el El número utiliza sólo las mismas técnicas que se conocen para el problema de Ruzsa-Szemerédi, por lo que esta afirmación más contundente parece ser un error. ^[1] ${\displaystyle 0}$ ${\displaystyle n-1}$ ${\displaystyle n\times n\times n}$ ${\displaystyle o(n^{2})}$ ${\displaystyle n^{2}/\exp \Omega (\log ^{*}n)}$ ${\displaystyle o(n^{2})}$

Un argumento de Dean Hickerson muestra que, como los trípodes no pueden llenar el espacio con una densidad constante, lo mismo se aplica a 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. La cantidad de trípodes que se pueden empaquetar en un cubo, para , 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 ; Morín, Pat ; Ooms, Aurélien; Schultz Xavier da Silveira, Luís Fernando (2019), "Más teoremas de tipo Turán para triángulos en conjuntos de puntos convexos", Revista Electrónica de Combinatoria , 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), Álgebra y mosaico: homomorfismos al servicio de la geometría , Carus Mathematical Monographs, vol. 25, Washington, DC: Asociación Matemática de América, pág. 97, ISBN 0-88385-028-1, SEÑOR  1311249
5. Gowers, PESO ; 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 tipo Turán para hipergrafos geométricos convexos", en Pach, János (ed.), Hacia una teoría de los grafos geométricos , Matemáticas contemporáneas, vol. 342, Providence, Rhode Island: Sociedad Matemática Estadounidense, págs. 25–33, doi :10.1090/conm/342/06128, SEÑOR  2065250
7. Hamaker, William; Stein, Sherman (1984), "Embalaje combinatorio de ciertas 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), "Empacar trípodes", Entretenimientos matemáticos, 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, señor  1661863
9. Tiskin, Alexander (2007), "Empacar trípodes: reducir 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 monótonas y búsqueda de camarillas en gráficos", Ann. Univ. Ciencia. Secta Budapest. Computadora. , 41 : 307–322, doi : 10.1080/00455091.2001.10717569, SEÑOR  3129145
12. Östergård, Patric RJ; Pöllänen, Antti (2019), "Nuevos resultados sobre empaquetaduras de trípode" (PDF) , Geometría computacional y discreta , 61 (2): 271–284, doi :10.1007/s00454-018-0012-2, MR  3903789
13. Sloane, N. J. A. (ed.), "Sequence A070214", La enciclopedia en línea de secuencias enteras , Fundación OEIS
14. Sloane, N. J. A. (ed.), "Sequence A086976", La enciclopedia en línea de secuencias enteras , Fundación OEIS