El lema de regularidad de Szemerédi es una de las herramientas más poderosas en la teoría de grafos extremos , particularmente en el estudio de grafos grandes y densos. Establece que los vértices de cada grafo lo suficientemente grandese pueden dividir en un número limitado de partes para que los bordes entre diferentes partes se comporten casi al azar.
De acuerdo con el lema, no importa cuán grande sea una gráfica, podemos aproximarla con las densidades de los bordes entre un número limitado de partes. Entre dos partes cualesquiera, la distribución de los bordes será pseudoaleatoria según la densidad del borde. Estas aproximaciones proporcionan valores esencialmente correctos para varias propiedades del gráfico, como el número de copias incrustadas de un subgrafo determinado o el número de eliminaciones de bordes necesarias para eliminar todas las copias de algún subgrafo.
Declaración
Para enunciar formalmente el lema de regularidad de Szemerédi, debemos formalizar lo que realmente significa la distribución de bordes entre partes que se comportan "casi al azar". Por 'casi aleatorio', nos referimos a una noción llamada ε -regularidad. Para entender lo que esto significa, primero establecemos algunas definiciones. En lo que sigue G es un gráfico con vértice conjunto V .
Definición 1. Let X , Y subconjuntos disjuntos de V . La densidad de aristas del par ( X , Y ) se define como:
donde E ( X , Y ) denota el conjunto de bordes que tienen un vértice final en X y uno en Y .
Llamamos a un par de partes ε -regular si, cada vez que toma un subconjunto grande de cada parte, su densidad de borde no está demasiado lejos de la densidad de borde del par de partes. Formalmente,
Definición 2. Para ε> 0 , un par de conjuntos de vértices X e Y se llama ε -regular , si para todos los subconjuntos A ⊆ X , B ⊆ Y satisfacen | A | ≥ ε | X | , | B | ≥ ε | Y | , tenemos
La forma natural de definir una partición ε- regular debería ser una en la que cada par de partes sea ε -regular. Sin embargo, algunas gráficas, como las medias gráficas , requieren que muchos pares de particiones (pero una pequeña fracción de todos los pares) sean irregulares. [1] Por lo tanto, definiremos ε- particiones regulares como aquellas en las que la mayoría de los pares de partes son ε -regulares.
Definición 3. Una partición de dentro conjuntos se llama un -partición regular si
Ahora podemos enunciar el lema:
Lema de regularidad de Szemerédi. Para cada ε> 0 y entero positivo m existe un entero M tal que si G es un gráfico con al menos M vértices, existe un entero k en el rango m ≤ k ≤ M y una ε- partición regular del conjunto de vértices de G en k conjuntos.
El límite M para el número de partes en la partición del gráfico dado por las demostraciones del lema de regularidad de Szemeredi es muy grande, dado por un exponencial iterado de nivel O (ε −5 ) de m . Hubo un tiempo en que se esperaba que el límite real fuera mucho más pequeño, lo que habría tenido varias aplicaciones útiles. Sin embargo, Gowers (1997) encontró ejemplos de gráficos para los cuales M de hecho crece muy rápido y es al menos tan grande como una exponencial iterada de nivel ε −1/16 de m . En particular, el mejor límite tiene exactamente el nivel 4 en la jerarquía de Grzegorczyk , por lo que no es una función recursiva elemental . [2]
Prueba
Encontraremos una partición ε-regular para un gráfico dado siguiendo un algoritmo. Un bosquejo aproximado:
- Comience con una partición arbitraria (podría ser solo 1 parte)
- Si bien la partición no es ε-regular:
- Encuentre los subconjuntos que son testigos de la irregularidad ε para cada par irregular.
- Simultáneamente, refine la partición utilizando todos los subconjuntos testigos.
Aplicamos una técnica llamada argumento de incremento de energía para mostrar que este proceso termina después de un número limitado de pasos. Básicamente, definimos una monovariante que debe aumentar en una cierta cantidad en cada paso, pero está limitada por encima y, por lo tanto, no puede aumentar indefinidamente. Esta monovariante se llama 'energía' ya que es una cantidad.
Definición 4. Let U , W subconjuntos de V . Colocar. La energía del par ( U , W ) se define como:
Para particiones de U yde W , definimos la energía como la suma de las energías entre cada par de partes:
Finalmente, para una partición de V , defina la energía de ser - estar . Específicamente,
Observe que la energía está entre 0 y 1 porque la densidad de los bordes está limitada por encima de 1:
Ahora, comenzamos probando que la energía no disminuye con el refinamiento.
Lema 1. (La energía no disminuye con la partición) Para cualquier partición y de conjuntos de vértices y , .
Prueba: dejar y . Elige vértices uniformemente desde y uniformemente desde , con en parte y en parte . Luego defina la variable aleatoria. Echemos un vistazo a las propiedades de. La expectativa es
El segundo momento es
Por convexidad, . Reorganizando, lo conseguimos para todos .
Si cada parte de se particiona aún más, la nueva partición se llama un refinamiento de . Ahora si, aplicando el Lema 1 a cada par demuestra que para cada refinamiento de , . Por lo tanto, el paso de refinamiento del algoritmo no pierde energía.
Lema 2. (Lema de aumento de energía) Si no es -regular como lo atestigua , luego,
Prueba: Definircomo anteriormente. Luego,
Pero observa que con probabilidad (correspondiente a y ), entonces
Ahora podemos probar el argumento del incremento de energía, que muestra que la energía aumenta sustancialmente en cada iteración del algoritmo.
Lema 3 ( Lema de incremento de energía) Si una partición de no es -regular, entonces existe un refinamiento de donde cada está dividido en como máximo partes tales que
Prueba: para todos tal que no es -regular, encontrar y que presencian irregularidades (haga esto simultáneamente para todos los pares irregulares). Dejar ser un refinamiento común de por 's. Cada está dividido en como máximo partes como desee. Luego,
Dónde es la partición de dada por . Según el Lema 1, la cantidad anterior es al menos
Desde es cortado por al crear , entonces es un refinamiento de . Según el lema 2, la suma anterior es al menos
Pero la segunda suma es al menos desde no es -regular, por lo que deducimos la desigualdad deseada.
Ahora, a partir de cualquier partición, podemos seguir aplicando Lemma 3 siempre que la partición resultante no sea -regular. Pero en cada paso la energía aumenta en, y está delimitado por encima de 1. Entonces este proceso se puede repetir como máximo veces, antes de que termine y debemos tener una -partición regular.
Aplicaciones
Si tenemos suficiente información sobre la regularidad de un gráfico, podemos contar el número de copias de un subgráfico específico dentro del gráfico hasta un pequeño error.
Lema de conteo de gráficos. Dejar ser un gráfico con , y deja . Dejar frijol -Gráfico de vértice con conjuntos de vértices tal que es -regular siempre . Luego, el número de copias etiquetadas de en está dentro de
Esto se puede combinar con el lema de regularidad de Szemerédi para probar el lema de eliminación de gráficos . El lema de eliminación de gráficos se puede usar para probar el teorema de Roth sobre progresiones aritméticas , [3] y una generalización del mismo, el lema de eliminación de hipergráficos , se puede usar para probar el teorema de Szemerédi . [4]
El lema de eliminación de gráficos se generaliza a subgráficos inducidos , al considerar las ediciones de los bordes en lugar de solo las eliminaciones de los bordes. Esto fue probado por Alon, Fischer, Krivelevich y Szegedy en 2000. [5] Sin embargo, esto requirió una variación más fuerte del lema de regularidad.
El lema de regularidad de Szemerédi no proporciona resultados significativos en gráficos dispersos . Dado que los gráficos dispersos tienen densidades de bordes subconstantes,-La regularidad se satisface trivialmente. Aunque el resultado parece puramente teórico, se han realizado algunos intentos [6] [7] para utilizar el método de regularidad como técnica de compresión para gráficos grandes.
Historial y extensiones
Szemerédi (1975) introdujo por primera vez una versión más débil de este lema, restringido a gráficos bipartitos, para probar el teorema de Szemerédi , [8] y en ( Szemerédi 1978 ) demostró el lema completo. [9] Extensiones del método regularidad a hypergraphs se obtuvieron por Rödl y sus colaboradores [10] [11] [12] y Gowers . [13] [14]
János Komlós , Gábor Sárközy y Endre Szemerédi más tarde (en 1997) demostraron en el lema ampliado [15] [16] que los pares regulares en el lema de regularidad de Szemerédi se comportan como gráficos bipartitos completos en las condiciones correctas. El lema permitió una exploración más profunda de la naturaleza de las incrustaciones de grandes gráficos dispersos en gráficos densos.
La primera versión constructiva fue proporcionada por Alon, Duke, Lefmann, Rödl y Yuster. [17] Posteriormente, Frieze y Kannan dieron una versión diferente y la ampliaron a hipergrafos. [18] Más tarde produjeron una construcción diferente debido a Alan Frieze y Ravi Kannan que usa valores singulares de matrices. [19] Se pueden encontrar algoritmos no deterministas más eficientes, como se detalla formalmente en el blog de Terence Tao [20] y se menciona implícitamente en varios artículos. [21] [22] [23]
Una desigualdad de Terence Tao extiende el lema de regularidad de Szemerédi, revisándolo desde la perspectiva de la teoría de la probabilidad y la teoría de la información en lugar de la teoría de grafos. [24] Terence Tao también ha proporcionado una prueba del lema basada en la teoría espectral, utilizando las matrices de adyacencia de los gráficos. [25]
No es posible probar una variante del lema de regularidad en la que todos los pares de conjuntos de particiones son regulares. Algunas gráficas, como las medias gráficas , requieren que muchos pares de particiones (pero una pequeña fracción de todos los pares) sean irregulares. [26]
Es una variante común en la definición de un -partición regular para requerir que todos los conjuntos de vértices tengan el mismo tamaño, mientras se recopilan los vértices sobrantes en un "error" -set cuyo tamaño es como máximo un -fracción del tamaño del conjunto de vértices de .
Alon, Fischer, Krivelevich y Szegedy demostraron una variación más fuerte del lema de regularidad, al mismo tiempo que demostraron el lema de eliminación de gráficos inducida. Esto funciona con una secuencia de en lugar de solo uno, y muestra que existe una partición con un refinamiento extremadamente regular, donde el refinamiento no tiene un incremento de energía demasiado grande.
El lema de regularidad de Szemerédi puede interpretarse en el sentido de que el espacio de todos los gráficos está totalmente acotado (y por lo tanto precompacto ) en una métrica adecuada (la distancia de corte ). Los límites de esta métrica se pueden representar mediante grafones ; otra versión del lema de regularidad simplemente establece que el espacio de grafones es compacto . [27]
Referencias
- ^ Conlon, David ; Fox, Jacob (2012), "Límites para la regularidad del gráfico y los lemas de eliminación", Análisis geométrico y funcional , 22 (5): 1191-1256, arXiv : 1107.4829 , doi : 10.1007 / s00039-012-0171-x , MR 2989432 , S2CID 1623986
- ^ Gowers, WT (1997), "Límites inferiores del tipo de torre para el lema de uniformidad de Szemerédi", Análisis geométrico y funcional , 7 (2): 322–337, doi : 10.1007 / PL00001621 , MR 1445389 , S2CID 115242956.
- ^ Roth, KF (1953), "Sobre ciertos conjuntos de números enteros", Journal of the London Mathematical Society , 28 (1): 104–109, doi : 10.1112 / jlms / s1-28.1.104 , MR 0051853
- ^ Tao, Terence (2006), "Una variante del lema de eliminación del hipergráfico", Journal of Combinatorial Theory , Serie A, 113 (7): 1257-1280, arXiv : math / 0503572 , doi : 10.1016 / j.jcta.2005.11. 006 , MR 2.259.060 , S2CID 14337591
- ^ Alon, Noga ; Fischer, Eldar; Krivelevich, Michael ; Szegedy, Mario (2000), "Prueba eficiente de gráficos grandes", Combinatorica , 20 (4): 451–476, doi : 10.1007 / s004930070001 , MR 1804820 , S2CID 44645628
- ^ Pelosin, Francesco (2018). "Compresión de gráficos utilizando el método de regularidad". arXiv : 1810.07275 . Cite journal requiere
|journal=
( ayuda ) - ^ Fiorucci, Marco; Pelosin, Francesco; Pelillo, Marcello (2020). "Separar la estructura del ruido en grandes gráficos utilizando el lema de regularidad". 98 . arXiv : 1905.06917 . Cite journal requiere
|journal=
( ayuda ) - ^ Szemerédi, Endre (1975), "Sobre conjuntos de enteros que no contienen k elementos en progresión aritmética" , Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica , 27 : 199–245, MR 0369312.
- ^ Szemerédi, Endre (1978), "Particiones regulares de gráficos", Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) , Colloq. Internat. CNRS, 260 , París: CNRS, págs. 399–401, MR 0540024.
- ^ Frankl, Peter ; Rödl, Vojtěch (2002), "Problemas extremos en sistemas de conjuntos", Estructuras y algoritmos aleatorios , 20 (2): 131-164, doi : 10.1002 / rsa.10017.abs , MR 1884430.
- ^ Rödl, Vojtěch ; Skokan, Jozef (2004), "Lema de regularidad para k- hipergramas uniformes", Estructuras y algoritmos aleatorios , 25 (1): 1–42, doi : 10.1002 / rsa.20017 , MR 2069663.
- ^ Nagle, Brendan; Rödl, Vojtěch ; Schacht, Mathias (2006), "El lema de conteo para hipergráficos uniformes k regulares ", Estructuras y algoritmos aleatorios , 28 (2): 113–179, CiteSeerX 10.1.1.378.8503 , doi : 10.1002 / rsa.20117 , MR 2198495.
- ^ Gowers, WT (2006), "Cuasirandomness, count and regularity for 3-uniform hypergraphs" , Combinatoria, Probabilidad y Computación , 15 (1–2): 143–184, doi : 10.1017 / S0963548305007236 , MR 2195580 , S2CID 14632612.
- ^ Gowers, WT (2007), "La regularidad hipergráfica y el teorema multidimensional de Szemerédi", Annals of Mathematics , Second Series, 166 (3): 897–946, arXiv : 0710.3032 , Bibcode : 2007arXiv0710.3032G , doi : 10.4007 / annals.2007.166 0.897 , MR 2.373.376 , S2CID 56118006.
- ^ Komlós, János ; Sárközy, Gábor N .; Szemerédi, Endre (1997), "Blow-up lemma", Combinatorica , 17 (1): 109–123, doi : 10.1007 / BF01196135 , MR 1466579 , S2CID 6720143
- ^ Komlós, János ; Sárközy, Gábor N .; Szemerédi, Endre (1998), "Una versión algorítmica del lema expandido", Estructuras y algoritmos aleatorios , 12 (3): 297–312, arXiv : math / 9612213 , doi : 10.1002 / (SICI) 1098-2418 ( 199805) 12: 3 <297 :: AID-RSA5> 3.3.CO; 2-W , MR 1635264
- ^ N. Alon y RA Duke y H. Lefmann y V. Rödl y R. Yuster (1994). "Los aspectos algorítmicos del lema de regularidad". J. Algoritmos . 16 : 80-109. CiteSeerX 10.1.1.102.681 . doi : 10.1006 / jagm.1994.1005 .
- ^ A. Frieze y R. Kannan (1996). "El lema de regularidad y esquemas de aproximación para problemas densos". FOCS '96: Actas del 37º Simposio Anual sobre Fundamentos de la Ciencia de la Computación . doi : 10.1109 / SFCS.1996.548459 .
- ^ A. Frieze y R. Kannan (1999). "Un algoritmo simple para construir la partición de regularidad de Szemerédi" (PDF) . Electrón. J. Comb . 6 .
- ^ Tao, Terence (2009), lema de regularidad de Szemeredi a través de particiones aleatorias
- ^ Alon, Noga ; Shapira, Asaf (2008), "Cada propiedad de un gráfico monótono es comprobable", SIAM J. Comput. , 38 (2): 505–522, doi : 10.1137 / 050633445 , ISSN 0097-5397 , MR 2411033
- ^ Ishigami, Yoshiyasu (2006), A Simple Regularization of Hypergraphs , arXiv : math / 0612838 , Bibcode : 2006math ..... 12838I
- ^ Austin, Tim (2008), "Sobre las variables aleatorias intercambiables y las estadísticas de gráficos grandes e hipergráficos", Encuestas de probabilidad , 5 : 80–145, arXiv : 0801.1698 , Bibcode : 2008arXiv0801.1698A , doi : 10.1214 / 08-PS124 , S2CID 15421306
- ^ Tao, Terence (2006), "Revisión del lema de regularidad de Szemerédi", Contribuciones a las matemáticas discretas , 1 (1): 8-28, arXiv : math / 0504472 , Bibcode : 2005math ... 4472T , MR 2212136.
- ^ Tao, Terence (2012), La prueba espectral del lema de regularidad de Szemeredi
- ^ Conlon, David ; Fox, Jacob (2012), "Límites para la regularidad del gráfico y los lemas de eliminación", Análisis geométrico y funcional , 22 (5): 1191-1256, arXiv : 1107.4829 , doi : 10.1007 / s00039-012-0171-x , MR 2989432 , S2CID 1623986
- ^ Lovász, László ; Szegedy, Balázs (2007), "El lema de Szemerédi para el analista", Geometric and Functional Analysis , 17 : 252-270, doi : 10.1007 / s00039-007-0599-6 , ISSN 1016-443X , MR 2306658 , S2CID 15201345
Otras lecturas
- 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 , János Bolyai Math. Soc., Budapest, págs. 295–352, MR 1395865.
- Komlós, J .; Shokoufandeh, Ali; Simonovits, Miklós ; Szemerédi, Endre (2002), "El lema de la regularidad y sus aplicaciones en la teoría de grafos", Aspectos teóricos de la informática (Teherán, 2000) , Lecture Notes in Computer Science , 2292 , Springer, Berlín, págs. 84-112, doi : 10.1007 / 3-540-45878-6_3 , ISBN 978-3-540-43328-6, Señor 1966181.