El problema de Ruja - Semeredi

El problema de Rouge-Szemeredi o (6,3) pregunta sobre el número máximo de aristas en un gráfico en el que cualquier arista pertenece a un solo triángulo. De manera equivalente, el problema pregunta sobre el número máximo de aristas en un gráfico bipartito balanceado cuyas aristas se pueden descomponer en un número lineal de emparejamientos generados , o el número máximo de triples que se pueden seleccionar de puntos tales que cada seis puntos contienen como máximo dos triples. El problema lleva el nombre de Imre Z. Rougy y Endre Szemeredy , quienes fueron los primeros en demostrar que la respuesta es menos que un factor de crecimiento lento (pero aún desconocido) [1] .

Equivalencia entre formulaciones

Las siguientes preguntas tienen respuestas que son asintóticamente equivalentes; difieren entre sí en no más que un factor constante [1] :

Para reducir el problema de coincidencia generado para un gráfico bipartito a un problema de un solo triángulo, agregue un conjunto de vértices de gráfico, uno para cada coincidencia generada, y agregue bordes desde los vértices y el gráfico bipartito a un vértice en este tercer conjunto cuando un borde de el grafo bipartito pertenece a la coincidencia generada . Como resultado, obtenemos un grafo tripartito balanceado con vértices con la propiedad de unicidad de los triángulos. En la otra dirección, cualquier gráfico con la propiedad de unicidad de triángulos puede reducirse a un gráfico tripartito equilibrado distribuyendo partes de vértices en tres conjuntos iguales al azar y conservando los triángulos que definen la distribución de partes. Esto da como resultado una proporción constante de triángulos y aristas. Un grafo tripartito balanceado con la propiedad de unicidad triangular se puede transformar en un grafo bipartito particionado eliminando uno de sus tres subconjuntos de vértices, creando una coincidencia generada en los vecinos de cada uno de los vértices eliminados.

Para transformar un grafo con un único triángulo por arista en un sistema de triples, tomamos los triángulos del grafo como triples. Ningún seis puntos puede incluir tres triángulos sin que dos de los tres triángulos compartan una arista, o los tres triángulos formen un cuarto triángulo que comparta aristas con cada uno de ellos. En la otra dirección, para convertir un sistema triple en un gráfico, primero elimine cualquier conjunto de cuatro puntos que contenga dos triples. Estos cuatro puntos no pueden estar presentes en otras ternas, y por lo tanto no pueden sumar más que un número lineal de ternas. Ahora formamos un gráfico conectando cualquier par de puntos que pertenezcan a cualquiera de los tripletes restantes.

Límite inferior

Un límite casi cuadrático para el problema de Rouge-Szemeredi se puede derivar del resultado de Felix Behrend, según el cual los números módulo un número primo impar tienen grandes conjuntos de Salem-Spencer , subconjuntos de tamaño sin progresiones aritméticas de tres términos [6 ] . El resultado de Behrend se puede utilizar para construir gráficos tripartitos en los que cada segmento tiene un vértice, el gráfico contiene aristas y cada arista pertenece a un solo triángulo. Entonces, según esta construcción, el número de aristas también es [5] .

Para construir un gráfico de este tipo a partir del subconjunto de Berend libre de progresiones aritméticas , numeramos los vértices en cada acción desde hasta y construimos triángulos de la forma módulo para cada uno de los intervalos desde hasta y cada número pertenece a . Por ejemplo, con y como resultado obtenemos un gráfico tripartito balanceado con 9 vértices y 18 aristas, como se muestra en la figura. El gráfico formado por la combinación de estos triángulos tiene la propiedad deseada de que cada arista pertenece exactamente a un triángulo. Si este no fuera el caso, habría un triángulo donde , y pertenecen a , lo que viola la suposición de que no hay progresiones aritméticas en [5] .

Límite superior

El lema de regularidad de Szemeredi se puede utilizar para demostrar que cualquier solución al problema de Rouzi-Szemeredi tiene como máximo aristas o triángulos [5] . Una versión más fuerte del lema de eliminación de cuentas de Jacob Fox implica que el tamaño de la solución no excede . Aquí y son representantes de la notación "o pequeña" y , y significa logaritmo iterado . Fox demostró que en cualquier grafo con vértices y triángulos, para algunos se puede encontrar un subgrafo sin triángulos eliminando la mayoría de las aristas [7] . En un gráfico con la propiedad de unicidad de triángulos, hay (naturalmente) triángulos, por lo que el resultado viene con . Pero en este gráfico, cada eliminación de aristas elimina solo un triángulo, por lo que la cantidad de aristas que deben eliminarse para eliminar todos los triángulos es igual a la cantidad de triángulos.

Historia

El problema lleva el nombre de Imre Z. Rougy y Endre Szemeredy , quienes estudiaron el problema en la formulación de triples de puntos en una publicación de 1978 [5] . Sin embargo, el problema fue estudiado previamente por W. J. Brown, Pal Erdős y Vera T. Szos en dos publicaciones de 1973, en las que demostraron que el número máximo de triples puede ser [8] , y conjeturaron que en realidad es igual a [9 ] . Ruzsa y Szemeredy dieron cotas superior e inferior (desiguales) casi cuadráticas para el problema, mejorando significativamente la cota inferior de Brown, Erdős y Sosa y la prueba de su conjetura [5] .

Aplicaciones

La existencia de gráficos densos que se pueden descomponer en grandes coincidencias generadas se ha utilizado para construir pruebas eficientes sobre si una función booleana es lineal, un componente clave del teorema PCP en la teoría de la complejidad computacional [10] . En la teoría de los algoritmos de comprobación de propiedades , se utilizaron resultados conocidos del problema de Rouzi-Szemeredi para demostrar que es posible comprobar si un gráfico contiene un subgráfico determinado (con un error unilateral en el número de consultas polinomio en el parámetro de error) si y solo si, cuando es un grafo bipartito [11] .

En la teoría de los algoritmos de transmisión para coincidencias de gráficos (p. ej., para hacer coincidir anunciantes con espacios publicitarios), la calidad de la cobertura de coincidencias (subgráficos dispersos que conservan aproximadamente el tamaño de las coincidencias en todos los subconjuntos de vértices) está estrechamente relacionada con la densidad de los gráficos bipartitos. que se pueden descomponer en coincidencias generadas. Esta construcción utiliza una forma modificada del problema de Ruzi-Semeredi, en el que la cantidad de coincidencias generadas puede ser mucho menor que la cantidad de vértices, pero cada coincidencia generada debe cubrir la mayoría de los vértices del gráfico. En esta versión del problema, es posible construir gráficos con un número no constante de emparejamientos generados de tamaño lineal, y este resultado conduce a límites casi exactos en el coeficiente de aproximación para algoritmos de emparejamiento de transmisión [12] [13] [14 ] [15] .

La cota superior subcadrática del problema de Rouzi-Szemeredi también se usó para obtener una cota sobre el tamaño de los conjuntos cap [16] antes de que se probaran cotas más fuertes de la forma para este problema [17] . También proporciona el límite superior más conocido para trípodes de embalaje [18] .

Notas

  1. ↑ 1 2 3 Komlós J., Simonovits M. Combinatorics, Paul Erdős tiene ochenta años, vol. 2 (Keszthely, 1993). - Budapest: Janos Bolyai Matemáticas. Soc., 1996. - T. 2. - S. 295–352. - (Bolyai Soc. Math. Stud.).
  2. ↑ Clark LH, Entringer RC, McCanna JE, Székely LA Problemas extremos para propiedades locales de grafos  // The Australasian Journal of Combinatorics. - 1991. - T. 4 . — P. 25–31 .
  3. ↑ Dalibor Fronček. Gráficos localmente lineales  // Mathematica Slovaca. - 1989. - T. 39 , núm. 1 . — P. 3–6 .
  4. ↑ Larrión F., Pizaña MA, Villarroel-Flores R. Small localmente nK 2 graphs  // Ars Combinatoria. - 2011. - T. 102 . — S. 385–391 .
  5. ↑ 1 2 3 4 5 6 Ruzsa IZ, Szemerédi E. Sistemas triples sin seis puntos que llevan tres triángulos // Combinatorics (Proc. Fifthhungaro Colloq., Keszthely, 1976), vol. II. - Holanda Septentrional, 1978. - T. 18. - S. 939-945. - (Colloq. Math. Soc. Janos Bolyai).
  6. ↑ Behrend FA Sobre conjuntos de números enteros que no contienen tres términos en progresión aritmética // Actas de la Academia Nacional de Ciencias . - T. 32 , n. 12 _ — S. 331–332 . -doi : 10.1073/ pnas.32.12.331 .
  7. ↑ Jacob Zorro. Una nueva prueba del lema de eliminación de gráficos  // Annals of Mathematics . - 2011. - T. 174 , núm. 1 . — S. 561–579 . -doi : 10.4007 / annals.2011.174.1.17 .
  8. ↑ Sós VT , Erdős P. , Brown WG Sobre la existencia de esferas trianguladas en 3-grafos y problemas relacionados  // Periodica Mathematica Hungarica. - 1973. - T. 3 , núm. 3-4 . — Pág. 221–228 . -doi : 10.1007/ BF02018585 .
  9. ↑ Brown WG, Erdős P. , Sós VT Algunos problemas extremos en gráficos r  // Nuevas direcciones en la teoría de gráficos (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971). - Prensa Académica, 1973. - S. 53-63 .
  10. ↑ Johan Håstad, Avi Widderson. Análisis simple de pruebas gráficas para linealidad y PCP  // Estructuras aleatorias y algoritmos. - 2003. - T. 22 , núm. 2 . — S. 139–160 . -doi : 10.1002/ rsa.10068 .
  11. ↑ Noga Alon . Prueba de subgrafos en gráficos grandes  // Estructuras aleatorias y algoritmos. - 2002. - T. 21 , núm. 3-4 . — S. 359–370 . -doi : 10.1002/ rsa.10056 .
  12. ↑ Ashish Goel, Michael Kapralov, Sanjeev Khanna. Actas del vigésimo tercer simposio anual ACM-SIAM sobre algoritmos discretos. - ACM, 2012. - S. 468-485.
  13. ↑ Michael Kapralov. Actas del vigésimo cuarto simposio anual ACM-SIAM sobre algoritmos discretos. - SIAM, 2013. - S. 1679-1697. -doi : 10.1137/ 1.9781611973105.121 .
  14. ↑ Christian Konrad. Coincidencia máxima en flujos de torniquetes // Algoritmos - ESA 2015. - Heidelberg: Springer, 2015. - T. 9294. - P. 840–852. - (Apuntes de conferencias en Informática. Sci.). -doi : 10.1007/ 978-3-662-48350-3_70 .
  15. ↑ Jacob Fox, Hao Huang, Benny Sudakov. En gráficos descomponibles en coincidencias inducidas de tamaños lineales // Boletín de la Sociedad Matemática de Londres . - 2017. - T. 49 , núm. 1 . — págs. 45–57 . -doi : 10.1112/ blms.12005 . -arXiv : 1512.07852 . _
  16. ↑ Frankl P., Graham RL, Rödl V. Sobre subconjuntos de grupos abelianos sin progresión aritmética de 3 términos // Journal of Combinatorial Theory . - 1987. - T. 45 , núm. 1 . — S. 157–161 . - doi : 10.1016/0097-3165(87)90053-7 .
  17. ↑ Jordan Ellenberg, Dion Gijswijt. Sobre grandes subconjuntos sin progresión aritmética de tres términos // Annals of Mathematics . - 2017. - T. 185 , núm. 1 . — S. 339–343 . doi : 10.4007 / annals.2017.185.1.8 . -arXiv : 1605.09223 . _
  18. ↑ Gowers WT, Long J. La longitud de una secuencia creciente de tuplas. - 2016. - arXiv : 1609.08688 .