Juego de gorras

La solución de Pellegrino para el problema del conjunto de tapas de cuatro dimensiones también conduce a cotas inferiores mayores que${\displaystyle 2^{n}}$para cualquier dimensión superior, que fue mejorada aún más para${\displaystyle 2.2173^{n}}$por Edel (2004) ^{[ 2 ]} y luego a${\displaystyle 2.2180^{n}}$por Tyrrell (2022) . ^{[ 10 ]} En diciembre de 2023, un equipo de investigadores de DeepMind de Google publicó un artículo donde combinaron un modelo de lenguaje grande (LLM) con un evaluador y lograron mejorar la cota a${\displaystyle 2.2202^{n}}$. ^{[ 11 ]}

En 1984, Tom Brown y Joe Buhler ^{[ 9 ]} demostraron que el tamaño máximo posible de un conjunto de tapas en${\displaystyle \mathbb {Z} _{3}^{n}}$es${\displaystyle o(3^{n})}$como${\displaystyle n}$crece; en términos generales, esto significa que los conjuntos de tapas tienen densidad cero. Péter Frankl , Ronald Graham y Vojtěch Rödl demostraron ^{[ 12 ]} en 1987 que el resultado de Brown y Buhler se deduce fácilmente del lema de eliminación de triángulos de Ruzsa - Szemerédi y preguntaron si existe una constante ${\displaystyle c<3}$de tal manera que, efectivamente, para todos los valores suficientemente grandes de ${\displaystyle n}$, cualquier límite establecido en${\displaystyle \mathbb {Z} _{3}^{n}}$tiene tamaño como máximo${\displaystyle c^{n}}$; es decir, si algún conjunto en${\displaystyle \mathbb {Z} _{3}^{n}}$de tamaño superior a${\displaystyle c^{n}}$contiene una línea afín. Esta cuestión también apareció en un artículo ^{[ 13 ]} publicado por Noga Alon y Moshe Dubiner en 1995. En el mismo año, Roy Meshulam demostró ^{[ 14 ]} que el tamaño de un conjunto de tapas no excede ${\displaystyle 2\cdot 3^{n}/n}$. Michael Bateman y Nets Katz ^{[ 15 ]} mejoraron el límite a${\displaystyle O(3^{n}/n^{1+\varepsilon })}$con una constante positiva${\displaystyle \varepsilon }$.

Determinar si la cota de Meshulam puede mejorarse ${\displaystyle c^{n}}$con ${\displaystyle c<3}$Se consideró uno de los problemas abiertos más intrigantes en combinatoria aditiva y teoría de Ramsey durante más de 20 años, destacado, por ejemplo, por las publicaciones de blog sobre este problema de los medallistas Fields Timothy Gowers ^{[ 16 ]} y Terence Tao . ^{[ 17 ]} En su publicación de blog, Tao se refiere a él como "quizás, mi problema abierto favorito" y da una demostración simplificada de la cota exponencial en conjuntos de tapas, a saber, que para cualquier potencia prima${\displaystyle p}$, un subconjunto${\displaystyle S\subset F_{p}^{n}}$que no contiene ninguna progresión aritmética de longitud${\displaystyle 3}$tiene tamaño como máximo${\displaystyle c_{p}^{n}}$para algunos${\displaystyle c_{p}<p}$. ^{[ 17 ]}

La conjetura del conjunto de tapas se resolvió en 2016 debido a una serie de avances en el método polinomial. Ernie Croot , Vsevolod Lev y Péter Pál Pach publicaron una preimpresión sobre el problema relacionado de subconjuntos libres de progresión de${\displaystyle \mathbb {Z} _{4}^{n}}$y el método fue utilizado por Jordan Ellenberg y Dion Gijswijt para demostrar una cota superior de${\displaystyle 2.756^{n}}$sobre el problema del conjunto de tapas. ^{[ 5 ] [ 6 ] [ 18 ] [ 19 ] [ 20 ]} En 2019, Sander Dahmen, Johannes Hölzl y Rob Lewis formalizaron la demostración de esta cota superior en el demostrador de teoremas Lean . ^{[ 21 ]}

A marzo de 2023, no hay una mejora exponencial en la cota superior de Ellenberg y Gijswijt. Jiang demostró que al examinar con precisión los coeficientes multinomiales que se derivan de la demostración de Ellenberg y Gijswijt, se puede obtener un factor de${\displaystyle {\sqrt {n}}}$. ^{[ 22 ]} Este ahorro se produce por las mismas razones que existe un${\displaystyle {1/{\sqrt {n}}}}$factor en el coeficiente binomial central .

La solución al problema del conjunto de tapas también se puede utilizar para demostrar una forma parcial de la conjetura del girasol , a saber, que si una familia de subconjuntos de un${\displaystyle n}$Si el conjunto de elementos no tiene tres subconjuntos cuyas intersecciones por pares sean todas iguales, entonces el número de subconjuntos en la familia es como máximo${\displaystyle c^{n}}$por una constante${\displaystyle c<2}$. ^{[ 5 ] [ 24 ] [ 6 ] [ 25 ]}

Los límites superiores de los conjuntos de tapas implican límites inferiores de ciertos tipos de algoritmos para la multiplicación de matrices . ^{[ 26 ]}

El grafo de Juegos es un grafo fuertemente regular con 729 vértices. Cada arista pertenece a un triángulo único, por lo que es un grafo localmente lineal , el grafo localmente lineal fuertemente regular más grande conocido. Su construcción se basa en el conjunto único de 56 puntos en el espacio proyectivo ternario de cinco dimensiones (en lugar del espacio afín en el que comúnmente se definen los conjuntos de 56 puntos). ^{[ 27 ]}