En matemática combinatoria y teoría de grafos extremos , el problema de Ruzsa-Szemerédi o problema (6,3) pide el número máximo de aristas en una gráfica en la que cada arista pertenece a un triángulo único. De manera equivalente, solicita el número máximo de aristas en un gráfico bipartito balanceado cuyas aristas se pueden dividir en un número lineal de coincidencias inducidas , o el número máximo de triples que se puede elegir.puntos de modo que cada seis puntos contenga como máximo dos triples. El problema lleva el nombre de Imre Z. Ruzsa y Endre Szemerédi , quienes demostraron por primera vez que su respuesta es más pequeña quepor un factor de crecimiento lento (pero aún desconocido). [1]
Equivalencia entre formulaciones
Todas las siguientes preguntas tienen respuestas que son asintóticamente equivalentes: difieren, como máximo, en factores constantes entre sí. [1]
- ¿Cuál es el número máximo posible de aristas en un gráfico con vértices en los que cada arista pertenece a un triángulo único? [2] Las gráficas con esta propiedad se denominan gráficas localmente lineales [3] o gráficas de coincidencia local. [4]
- ¿Cuál es el número máximo posible de aristas en un gráfico bipartito con vértices en cada lado de su bipartición, cuyos bordes se pueden dividir en subgrafos inducidos que son coincidentes cada uno ? [1]
- ¿Cuál es el mayor número posible de triples de puntos que se pueden seleccionar? puntos dados, de tal manera que cada seis puntos contengan como máximo dos de los triples seleccionados? [5]
El problema Ruzsa-Szemerédi pide la respuesta a estas preguntas equivalentes.
Para convertir el problema de emparejamiento inducido por gráficos bipartitos en el problema de triángulo único, agregue un tercer conjunto de vértices al gráfico, uno para cada coincidencia inducida, y agregue aristas de vértices y del gráfico bipartito al vértice en este tercer conjunto siempre que el borde bipartito pertenece al emparejamiento inducido . El resultado es un gráfico tripartito equilibrado convértices y la propiedad de triángulo único. En la otra dirección, un gráfico arbitrario con la propiedad de triángulo único se puede convertir en un gráfico tripartito balanceado eligiendo una partición de los vértices en tres conjuntos iguales al azar y manteniendo solo los triángulos que respetan la partición. Esto retendrá (en expectativa) una fracción constante de los triángulos y aristas. Un gráfico tripartito equilibrado con la propiedad de triángulo único se puede convertir en un gráfico bipartito particionado eliminando uno de sus tres subconjuntos de vértices y haciendo una coincidencia inducida en los vecinos de cada vértice eliminado.
Para convertir una gráfica con un triángulo único por arista en un sistema triple, deje que las triples sean los triángulos de la gráfica. No hay seis puntos que puedan incluir tres triángulos sin que dos de los tres triángulos compartan un borde o los tres triángulos formen un cuarto triángulo que comparta un borde 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 participar en ningún otro triple, por lo que no pueden contribuir a un número total de triples más que lineal. Luego, forma una gráfica que conecte cualquier par de puntos que pertenezcan a cualquiera de los triples restantes.
Límite inferior
Un límite inferior casi cuadrático en el problema de Ruzsa-Szemerédi se puede derivar de un resultado de Felix Behrend , según el cual los números módulo un número primo impartienen 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 lado de la tripartición tiene vértices, hay bordes, y cada borde pertenece a un triángulo único. Así, con esta construcción, y el número de aristas es . [5]
Para construir una gráfica de esta forma a partir del subconjunto libre de progresión aritmética de Behrend , numera los vértices a cada lado de la tripartición desde a y construye triángulos de la forma modulo para cada en el rango de a y cada en . Por ejemplo, con y , el resultado es un gráfico tripartito equilibrado de nueve vértices con 18 aristas, que se muestra en la ilustración. La gráfica formada por la unión de estos triángulos tiene la propiedad deseada de que cada borde pertenece a un triángulo único. Porque, si no, habría un triángulo dónde , , y todos pertenecen a , violando el supuesto de que no hay progresiones aritméticas en . [5]
Límite superior
El lema de regularidad de Szemerédi se puede utilizar para demostrar que cualquier solución al problema de Ruzsa-Szemerédi tiene como máximobordes o triples. [5] Una forma más sólida del lema de eliminación de gráficos de Jacob Fox implica que el tamaño de una solución es como máximo. Aquí el y son instancias de notación Omega pequeña y grande , ydenota el logaritmo iterado . Fox demuestra que, en cualquier-Gráfico de vértice con triángulos para algunos , se puede encontrar un subgrafo sin triángulos quitando como máximobordes. [7] En un gráfico con la propiedad de triángulo único, hay (ingenuamente) triángulos, por lo que este resultado se aplica con . Pero en este gráfico, la eliminación de cada borde elimina solo un triángulo, por lo que el número de bordes que se deben eliminar para eliminar todos los triángulos es el mismo que el número de triángulos.
Historia
El problema lleva el nombre de Imre Z. Ruzsa y Endre Szemerédi , quienes estudiaron este problema, en la formulación que involucra triples de puntos, en una publicación de 1978. [5] Sin embargo, había sido estudiado previamente por WG Brown , Paul Erdős y Vera T. Sós , en dos publicaciones en 1973 que demostraron que el número máximo de triples puede ser, [8] y conjeturaba que era. [9] Ruzsa y Szemerédi proporcionaron límites superiores e inferiores casi cuadráticos (desiguales) para el problema, mejorando significativamente el límite inferior anterior de Brown, Erdős y Sós, y demostrando su conjetura. [5]
Aplicaciones
La existencia de gráficos densos que se pueden dividir en grandes coincidencias inducidas se ha utilizado para construir pruebas eficientes de 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 prueba de propiedades , los resultados conocidos del problema Ruzsa-Szemerédi se han aplicado para demostrar que es posible probar si un gráfico no tiene copias de un subgráfico determinado., con error unilateral en un número de consultas polinomio en el parámetro de error, si y solo si es un gráfico bipartito . [11]
En la teoría de los algoritmos de transmisión para la coincidencia de gráficos (por ejemplo, para hacer coincidir los anunciantes de Internet con espacios publicitarios), la calidad de las portadas coincidentes (subgrafos dispersos que conservan aproximadamente el tamaño de una coincidencia en todos los subconjuntos de vértices) está estrechamente relacionada con la densidad de gráficos que se pueden dividir en coincidencias inducidas. Esta construcción utiliza una forma modificada del problema de Ruzsa-Szemerédi en la que el número de emparejamientos inducidos puede ser mucho menor que el número de vértices, pero cada emparejamiento inducido 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 coincidencias inducidas de tamaño lineal, y este resultado conduce a límites casi estrechos en la relación de aproximación de los algoritmos de coincidencia de transmisión. [12] [13] [14] [15]
El límite superior subcuadrático del problema Ruzsa-Szemerédi también se utilizó para proporcionar un límite en el tamaño de los conjuntos de límites , [16] antes de los límites más fuertes del formulario por fueron probados para este problema. [17] También proporciona el límite superior más conocido en el embalaje de trípode . [18]
Referencias
- ↑ a b c Komlós, J .; Simonovits, M. (1996), "El lema de regularidad de Szemerédi y sus aplicaciones en la teoría de grafos", Combinatoria, Paul Erdős es ochenta, vol. 2 (Keszthely, 1993) , Bolyai Soc. Matemáticas. Stud., 2 , Budapest: János Bolyai Math. Soc., Págs. 295–352, CiteSeerX 10.1.1.31.2310 , MR 1395865
- ^ Clark, LH; Entringer, RC; McCanna, JE; Székely, LA (1991), "Problemas extremos para las propiedades locales de los gráficos" (PDF) , The Australasian Journal of Combinatorics , 4 : 25–31, MR 1129266
- ^ Fronček, Dalibor (1989), "Gráficos localmente lineales", Mathematica Slovaca , 39 (1): 3–6, hdl : 10338.dmlcz / 136481 , MR 1016323
- ^ Larrión, F .; Pizaña, MA; Villarroel-Flores, R. (2011), "Pequeños gráficos localmente nK 2 " (PDF) , Ars Combinatoria , 102 : 385–391, MR 2867738
- ^ a b c d e f Ruzsa, IZ ; Szemerédi, E. (1978), "Sistemas triples sin seis puntos que llevan tres triángulos", Combinatoria (Proc. Quinto Coloquio Húngaro, Keszthely, 1976), vol. II , Coloq. Matemáticas. Soc. János Bolyai, 18 , Amsterdam y Nueva York: North-Holland, págs. 939–945, MR 0519318
- ^ Behrend, FA (diciembre de 1946), "Sobre conjuntos de números enteros que no contienen tres términos en progresión aritmética", Actas de la Academia Nacional de Ciencias , 32 (12): 331–332, doi : 10.1073 / pnas.32.12.331 , PMC 1078964 , PMID 16578230
- ^ Fox, Jacob (2011), "Una nueva prueba del lema de eliminación de gráficos", Annals of Mathematics , Second Series, 174 (1): 561–579, arXiv : 1006.1300 , doi : 10.4007 / annals.2011.174.1.17 , MR 2811609
- ^ Sós, VT ; Erdős, P .; Brown, WG (1973), "Sobre la existencia de esferas trianguladas en 3 gráficos y problemas relacionados" (PDF) , Periodica Mathematica Hungarica , 3 (3–4): 221–228, doi : 10.1007 / BF02018585 , MR 0323647
- ^ Brown, WG ; Erdős, P .; Sós, VT (1973), "Some extreme problem on r -graphs" (PDF) , New Directions in the Theory of Graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971) , Nueva York : Academic Press, págs. 53–63, MR 0351888
- ^ Håstad, Johan ; Wigderson, Avi (2003), "Análisis simple de pruebas gráficas para linealidad y PCP" (PDF) , Estructuras y algoritmos aleatorios , 22 (2): 139-160, doi : 10.1002 / rsa.10068 , MR 1954608
- ^ Alon, Noga (2002), "Testing subgraphs in large graphs" (PDF) , Random Structures & Algorithms , 21 (3–4): 359–370, doi : 10.1002 / rsa.10056 , MR 1945375
- ^ Goel, Ashish; Kapralov, Michael; Khanna, Sanjeev (2012), "Sobre la complejidad de comunicación y transmisión de la máxima correspondencia bipartita" (PDF) , Actas del Vigésimo Tercer Simposio Anual ACM-SIAM sobre Algoritmos Discretos , Nueva York: ACM, págs. 468–485, MR 3205231
- ^ Kapralov, Michael (2013), "Mejores límites para las coincidencias en el modelo de transmisión", Actas del vigésimo cuarto simposio anual ACM-SIAM sobre algoritmos discretos , Filadelfia, Pensilvania: SIAM, págs. 1679-1697, arXiv : 1206.2269 , doi : 10.1137 / 1.9781611973105.121 , Señor 3203007
- ^ Konrad, Christian (2015), "Máxima coincidencia en corrientes de torniquete", Algoritmos — ESA 2015 , Lecture Notes in Comput. Sci., 9294 , Heidelberg: Springer, págs. 840–852, arXiv : 1505.01460 , doi : 10.1007 / 978-3-662-48350-3_70 , MR 3446428
- ^ Fox, Jacob ; Huang, Hao; Sudakov, Benny (2017), "En gráficos descomponibles en emparejamientos inducidos de tamaños lineales", Boletín de la London Mathematical Society , 49 (1): 45–57, arXiv : 1512.07852 , doi : 10.1112 / blms.12005 , MR 3653100
- ^ Frankl, P .; Graham, RL ; Rödl, V. (1987), "Sobre subconjuntos de grupos abelianos sin progresión aritmética de 3 términos", Journal of Combinatorial Theory , Serie A, 45 (1): 157-161, doi : 10.1016 / 0097-3165 (87) 90053-7 , MR 0883900
- ^ Ellenberg, Jordan S .; Gijswijt, Dion (2017), "En grandes subconjuntos desin progresión aritmética de tres términos ", Annals of Mathematics , Second Series, 185 (1): 339–343, arXiv : 1605.09223 , doi : 10.4007 / annals.2017.185.1.8 , MR 3583358
- ^ Gowers, WT ; Long, J. (2016), La longitud de un-secuencia creciente de -tuplas , arXiv : 1609.08688