Lema de regularidad de Szemerédi

Concepto en la teoría de grafos extremales

Los bordes entre las piezas se comportan de manera "aleatoria".

En la teoría de grafos extremales , el lema de regularidad de Szemerédi establece que un grafo puede dividirse en un número limitado de partes de modo que las aristas entre las partes sean regulares. El lema muestra que ciertas propiedades de los grafos aleatorios pueden aplicarse a grafos densos, como contar las copias de un subgrafo dado dentro de los grafos. Endre Szemerédi demostró el lema sobre grafos bipartitos para su teorema sobre progresiones aritméticas en 1975 y para grafos generales en 1978. Las variantes del lema utilizan diferentes nociones de regularidad y se aplican a otros objetos matemáticos como los hipergrafos .

Declaración

Para enunciar formalmente el lema de regularidad de Szemerédi, debemos formalizar lo que realmente significa la distribución de aristas entre partes que se comportan de manera "casi aleatoria". Por "casi aleatoria", nos referimos a una noción llamada ε -regularidad. Para entender lo que esto significa, primero enunciamos algunas definiciones. A continuación, G es un grafo con un conjunto de vértices V .

Definición 1. Sean X ,  Y subconjuntos disjuntos de V . La densidad de aristas del par ( X ,  Y ) se define como:

${\displaystyle d(X,Y):={\frac {\left|E(X,Y)\right|}{|X||Y|}}}$

donde E ( X ,  Y ) denota el conjunto de aristas que tienen un vértice final en X y uno en Y .

Los pares de subconjuntos de un par regular son similares en densidad de aristas al par original.

Llamamos a un par de partes ε -regular si, siempre que se toma un subconjunto grande de cada parte, su densidad de aristas no está muy alejada de la densidad de aristas 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 que satisfacen | A | ≥ ε| X | , | B | ≥ ε| Y | , tenemos

${\displaystyle \left|d(X,Y)-d(A,B)\right|\leq \varepsilon .}$

La forma natural de definir una partición ε -regular debería ser aquella en la que cada par de partes sea ε -regular. Sin embargo, algunos grafos, como los semigrafos , requieren que muchos pares de particiones (pero una pequeña fracción de todos los pares) sean irregulares. ^[1] Por lo tanto, definiremos las particiones ε -regulares como aquellas en las que la mayoría de los pares de partes sean ε -regulares.

Definición 3. Una partición de en conjuntos se denomina partición -regular si ${\displaystyle V}$ ${\displaystyle k}$ ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ ${\displaystyle \varepsilon }$

${\displaystyle \sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}|V_{i}||V_{j}|\leq \varepsilon |V(G)|^{2}}$

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 grafo 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 grafo dado por las pruebas del lema de regularidad de Szemeredi es muy grande, dado por una exponencial iterada de nivel O(ε ⁻⁵ ) de m . En un momento se esperaba que el límite verdadero fuera mucho menor, lo que habría tenido varias aplicaciones útiles. Sin embargo, Gowers (1997) encontró ejemplos de grafos 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 . ^[2]

Prueba

Los límites de los subconjuntos que presencian irregularidades refinan cada parte de la partición.

Encontraremos una partición ε-regular para un grafo dado siguiendo un algoritmo:

1. Empezar con una partición
2. Si bien la partición no es ε-regular:
   • Encuentre los subconjuntos que presentan ε-irregularidad para cada par irregular.
3. Refinar la partición utilizando todos los subconjuntos testigos.

Aplicamos una técnica llamada argumento de incremento de energía para demostrar que este proceso se detiene después de un número limitado de pasos. Para ello, definimos una medida que debe aumentar en una cierta cantidad en cada paso, pero está limitada por encima y, por lo tanto, no puede aumentar indefinidamente. Esta medida se llama "energía" porque es una cantidad. ${\displaystyle L^{2}}$

Definición 4. Sean U ,  W subconjuntos de V . Conjunto . La energía del par ( U ,  W ) se define como: ${\displaystyle |V|=n}$

${\displaystyle q(U,W):={\frac {|U||W|}{n^{2}}}d(U,W)^{2}}$

Para las particiones de U y de W , definimos la energía como la suma de las energías entre cada par de partes: ${\displaystyle {\mathcal {P}}_{U}=\{U_{1},\ldots ,U_{k}\}}$ ${\displaystyle {\mathcal {P}}_{W}=\{W_{1},\ldots ,W_{l}\}}$

${\displaystyle q({\mathcal {P}}_{U},{\mathcal {P}}_{W}):=\sum _{i=1}^{k}\sum _{j=1}^{l}q(U_{i},W_{j})}$

Finalmente, para una partición de V , definamos la energía de como . Específicamente, ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle q({\mathcal {P}},{\mathcal {P}})}$

${\displaystyle q({\mathcal {P}})=\sum _{i=1}^{k}\sum _{j=1}^{k}q(V_{i},V_{j})=\sum _{i=1}^{k}\sum _{j=1}^{k}{\frac {|V_{i}||V_{j}|}{n^{2}}}d(V_{i},V_{j})^{2}}$

Tenga en cuenta que la energía está entre 0 y 1 porque la densidad del borde está limitada por encima de 1:

${\displaystyle q({\mathcal {P}})=\sum _{i=1}^{k}\sum _{j=1}^{k}{\frac {|V_{i}||V_{j}|}{n^{2}}}d(V_{i},V_{j})^{2}\leq \sum _{i=1}^{k}\sum _{j=1}^{k}{\frac {|V_{i}||V_{j}|}{n^{2}}}=1}$

Ahora, comenzamos demostrando que la energía no disminuye con el refinamiento.

Lema 1. (La energía no es decreciente bajo partición) Para cualesquiera particiones y de conjuntos de vértices y , . ${\displaystyle {\mathcal {P}}_{U}}$ ${\displaystyle {\mathcal {P}}_{W}}$ ${\displaystyle U}$ ${\displaystyle W}$ ${\displaystyle q({\mathcal {P}}_{U},{\mathcal {P}}_{W})\geq q(U,W)}$

Demostración: Sean y . Elija vértices uniformemente de y uniformemente de , con en parte y en parte . Luego defina la variable aleatoria . Veamos las propiedades de . La expectativa es ${\displaystyle {\mathcal {P}}_{U}=\{U_{1},\ldots ,U_{k}\}}$ ${\displaystyle {\mathcal {P}}_{W}=\{W_{1},\ldots ,W_{l}\}}$ ${\displaystyle x}$ ${\displaystyle U}$ ${\displaystyle y}$ ${\displaystyle W}$ ${\displaystyle x}$ ${\displaystyle U_{i}}$ ${\displaystyle y}$ ${\displaystyle W_{j}}$ ${\displaystyle Z=d(U_{i},W_{j})}$ ${\displaystyle Z}$

${\displaystyle \mathbb {E} [Z]=\sum _{i=1}^{k}\sum _{j=1}^{l}{\frac {|U_{i}|}{|U|}}{\frac {|W_{j}|}{|W|}}d(U_{i},W_{j})={\frac {e(U,W)}{|U||W|}}=d(U,W)}$

El segundo momento es

${\displaystyle \mathbb {E} [Z^{2}]=\sum _{i=1}^{k}\sum _{j=1}^{l}{\frac {|U_{i}|}{|U|}}{\frac {|W_{j}|}{|W|}}d(U_{i},W_{j})^{2}={\frac {n^{2}}{|U||W|}}q({\mathcal {P}}_{U},{\mathcal {P}}_{W})}$

Por convexidad, . Reordenando, obtenemos que para todos . ${\displaystyle \mathbb {E} [Z^{2}]\geq \mathbb {E} [Z]^{2}}$ ${\displaystyle q({\mathcal {P}}_{U},{\mathcal {P}}_{W})\geq q(U,W)}$ ${\displaystyle U,W}$ ${\displaystyle \square }$

Si cada parte de se vuelve a dividir, la nueva partición se denomina refinamiento de . Ahora bien, si , al aplicar el Lema 1 a cada par se demuestra que para cada refinamiento de , . Por lo tanto, el paso de refinamiento del algoritmo no pierde energía. ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{m}\}}$ ${\displaystyle (V_{i},V_{j})}$ ${\displaystyle {\mathcal {P'}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle q({\mathcal {P'}})\geq q({\mathcal {P}})}$

Lema 2. (Lema del impulso energético) Si no es -regular como lo demuestra , entonces, ${\displaystyle (U,W)}$ ${\displaystyle \varepsilon }$ ${\displaystyle U_{1}\subset U,W_{1}\subset W}$

${\displaystyle q\left(\{U_{1},U\backslash U_{1}\},\{W_{1},W\backslash W_{1}\}\right)>q(U,W)+\varepsilon ^{4}{\frac {|U||W|}{n^{2}}}}$

Demostración: Definir como se indica arriba. Entonces, ${\displaystyle Z}$

${\displaystyle Var(Z)=\mathbb {E} [Z^{2}]-\mathbb {E} [Z]^{2}={\frac {n^{2}}{|U||W|}}\left(q\left(\{U_{1},U\backslash U_{1}\},\{W_{1},W\backslash W_{1}\}\right)-q(U,W)\right)}$

Pero observe que con probabilidad (correspondiente a y ), entonces ${\displaystyle |Z-\mathbb {E} [Z]|=|d(U_{1},W_{1})-d(U,W)|}$ ${\displaystyle {\frac {|U_{1}|}{|U|}}{\frac {|W_{1}|}{|W|}}}$ ${\displaystyle x\in U_{1}}$ ${\displaystyle y\in W_{1}}$

${\displaystyle Var(Z)=\mathbb {E} [(Z-\mathbb {E} [Z])^{2}]\geq {\frac {|U_{1}|}{|U|}}{\frac {|W_{1}|}{|W|}}(d(U_{1},W_{1})-d(U,W))^{2}>\varepsilon \cdot \varepsilon \cdot \varepsilon ^{2}}$ ${\displaystyle \square }$

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 del incremento de energía) Si una partición de no es -regular, entonces existe un refinamiento de donde cada se divide en como máximo partes tales que ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ ${\displaystyle V(G)}$ ${\displaystyle \varepsilon }$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle V_{i}}$ ${\displaystyle 2^{k}}$

${\displaystyle q({\mathcal {Q}})\geq q({\mathcal {P}})+\varepsilon ^{5}.}$

Demostración: Para todos los que no son -regulares, encuentre y que sean testigos de irregularidad (haga esto simultáneamente para todos los pares irregulares). Sea un refinamiento común de por . Cada uno se divide en la mayor cantidad de partes que se desee. Luego, ${\displaystyle (i,j)}$ ${\displaystyle (V_{i},V_{j})}$ ${\displaystyle \varepsilon }$ ${\displaystyle A^{i,j}\subset V_{i}}$ ${\displaystyle A^{j,i}\subset V_{j}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle A^{i,j}}$ ${\displaystyle V_{i}}$ ${\displaystyle 2^{k}}$

${\displaystyle q({\mathcal {Q}})=\sum _{(i,j)\in [k]^{2}}q({\mathcal {Q}}_{V_{i}},{\mathcal {Q}}_{V_{j}})=\sum _{(V_{i},V_{j}){\text{ }}\varepsilon {\text{-regular}}}q({\mathcal {Q}}_{V_{i}},{\mathcal {Q}}_{V_{j}})+\sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}q({\mathcal {Q}}_{V_{i}},{\mathcal {Q}}_{V_{j}})}$

¿Dónde está la partición de dada por ? Por el Lema 1, la cantidad anterior es al menos ${\displaystyle {\mathcal {Q}}_{V_{i}}}$ ${\displaystyle V_{i}}$ ${\displaystyle {\mathcal {Q}}}$

${\displaystyle \sum _{(V_{i},V_{j}){\text{ }}\varepsilon {\text{-regular}}}q(V_{i},V_{j})+\sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}q(\{A^{i,j},V_{i}\backslash A^{i,j}\},\{A^{j,i},V_{j}\backslash A^{j,i}\})}$

Dado que se corta por al crear , entonces es un refinamiento de . Por el lema 2, la suma anterior es al menos ${\displaystyle V_{i}}$ ${\displaystyle A^{i,j}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle {\mathcal {Q}}_{V_{i}}}$ ${\displaystyle \{A^{i,j},V_{i}\backslash A^{i,j}\}}$

${\displaystyle \sum _{(i,j)\in [k]^{2}}q(V_{i},V_{j})+\sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}\varepsilon ^{4}{\frac {|V_{i}||V_{j}|}{n^{2}}}}$

Pero la segunda suma es al menos ya que no es -regular, por lo que deducimos la desigualdad buscada. ${\displaystyle \varepsilon ^{5}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \varepsilon }$ ${\displaystyle \square }$

Ahora, a partir de cualquier partición, podemos seguir aplicando el Lema 3 siempre que la partición resultante no sea -regular. Pero en cada paso la energía aumenta en , y está acotada por encima en 1. Entonces este proceso se puede repetir la mayor cantidad de veces, antes de que finalice y debamos tener una partición -regular. ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon ^{5}}$ ${\displaystyle \varepsilon ^{-5}}$ ${\displaystyle \varepsilon }$

Aplicaciones

Lema de conteo de gráficos

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 con un pequeño error.

Lema de conteo de grafos. Sea un grafo con , y sea . Sea un grafo de -vértice con conjuntos de vértices tales que es -regular siempre que . Entonces, el número de copias etiquetadas de en está dentro de de ${\displaystyle H}$ ${\displaystyle V(H)=[k]}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle V_{1},\dots ,V_{k}\subseteq V(G)}$ ${\displaystyle (V_{i},V_{j})}$ ${\displaystyle \varepsilon }$ ${\displaystyle \{i,j\}\in E(H)}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle e(H)\varepsilon |V_{1}|\cdots |V_{k}|}$

${\displaystyle \left(\prod _{\{i,j\}\in E(H)}d(V_{i},V_{j})\right)\left(\prod _{i=1}^{k}|V_{i}|\right).}$

Esto se puede combinar con el lema de regularidad de Szemerédi para demostrar el lema de eliminación de grafos . El lema de eliminación de grafos se puede utilizar para demostrar el teorema de Roth sobre progresiones aritméticas [ ^3] y una generalización de este, el lema de eliminación de hipergrafos , se puede utilizar para demostrar el teorema de Szemerédi ^[4] .

El lema de eliminación de grafos se generaliza a subgrafos inducidos , al considerar ediciones de aristas en lugar de solo eliminaciones de aristas. Esto fue demostrado 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 grafos dispersos . Dado que los grafos dispersos tienen densidades de aristas subconstantes, la regularidad se satisface trivialmente. Aunque el resultado parece puramente teórico, se han realizado algunos intentos ^{[6] [7]} de utilizar el método de regularidad como técnica de compresión para grafos grandes. ${\displaystyle \varepsilon }$

Regularidad frisa-kannan

Frieze y Kannan introdujeron una noción diferente de regularidad, conocida como el lema de regularidad débil. ^[8] Este lema define una noción de regularidad más débil que la de Szemerédi que utiliza mejores límites y puede utilizarse en algoritmos eficientes.

Dado un gráfico , se dice que una partición de sus vértices es Frieze-Kannan -regular si para cualquier par de conjuntos : ${\displaystyle G=(V,E)}$ ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ ${\displaystyle \epsilon }$ ${\displaystyle S,T\subseteq V}$

${\displaystyle \left|e(S,T)-\sum _{i,j=1}^{k}d(V_{i},V_{j})|S\cap V_{i}||T\cap V_{j}|\right|\leq \epsilon |V|^{2}}$

El lema de regularidad débil para gráficos establece que cada gráfico tiene una partición débilmente regular en, como máximo, partes. ${\displaystyle \epsilon }$ ${\displaystyle 4^{\epsilon ^{-2}}}$

Esta noción se puede extender a los grafones definiendo un operador de escalonamiento. Dado un grafon y una partición de , podemos definir como un grafon escalonado con pasos dados por y valores dados por el promedio de cada paso. ${\displaystyle W}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle [0,1]}$ ${\displaystyle W_{\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle W}$

Una partición es débil -regular si: ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \epsilon }$

${\displaystyle \|W-W_{\mathcal {P}}\|_{\square }\leq \epsilon }$

El lema de regularidad débil para grafones establece que cada grafón tiene una partición débilmente regular en, como máximo, partes. Al igual que el lema de regularidad de Szemerédi, la regularidad débil también induce un lema de conteo. ${\displaystyle \epsilon }$ ${\displaystyle 4^{\epsilon ^{-2}}}$

Aplicaciones algorítmicas

Una de las motivaciones iniciales para el desarrollo del lema de regularidad débil fue la búsqueda de un algoritmo eficiente para estimar el corte máximo en un grafo denso . ^[8] Se ha demostrado que aproximar el problema de corte máximo más allá de 16/17 es NP-hard , ^[9] sin embargo, una versión algorítmica del lema de regularidad débil proporciona un algoritmo eficiente para aproximar el corte máximo para grafos densos dentro de un error aditivo. ^[8] Estas ideas se han desarrollado aún más en algoritmos de muestreo eficientes para estimar el corte máximo en grafos densos. ^[10] ${\displaystyle \epsilon n^{2}}$

Los límites más pequeños del lema de regularidad débil permiten algoritmos eficientes para encontrar una partición -regular. ^[11] La regularidad gráfica también se ha utilizado en varias áreas de la informática teórica , como la multiplicación de matrices ^[12] y la complejidad de la comunicación . ^[13] ${\displaystyle \epsilon }$

Lema de regularidad fuerte

El lema de regularidad fuerte es una variación más fuerte del lema de regularidad probado por Alon , Fischer, Krivelevich y Szegedy en 2000. ^[5] Intuitivamente, proporciona información entre pares no regulares y podría aplicarse para probar el lema de eliminación de grafos inducida .

Declaración

Para cualquier secuencia infinita de constantes , existe un entero tal que para cualquier grafo , podemos obtener dos particiones (equitativas) y tal que se satisfacen las siguientes propiedades: ${\displaystyle \epsilon _{0}\geq \epsilon _{1}\geq ...>0}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {Q}}}$

• ${\displaystyle {\mathcal {Q}}}$refina , es decir, cada parte de es la unión de alguna colección de partes en . ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {Q}}}$
• ${\displaystyle {\mathcal {P}}}$es -regular y es -regular. ${\displaystyle \epsilon _{0}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle \epsilon _{|{\mathcal {P}}|}}$
• ${\displaystyle q({\mathcal {Q}})<q({\mathcal {P}})+\epsilon _{0}}$
• ${\displaystyle |{\mathcal {Q}}|\leq M}$

Prueba

Aplicamos el lema de regularidad repetidamente para demostrar la versión más fuerte. Un esquema aproximado:

• Comience con una partición regular ${\displaystyle {\mathcal {P}}_{0}}$ ${\displaystyle \epsilon _{0}}$

• Encuentre repetidamente su refinamiento que es regular. Si el incremento de energía de , simplemente devolvemos . De lo contrario, reemplazamos con y continuamos. ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle \epsilon _{|{\mathcal {P}}|}}$ ${\displaystyle {\mathcal {Q}}\leq \epsilon _{0}}$ ${\displaystyle ({\mathcal {P}},{\mathcal {Q}})}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {Q}}}$

Comenzamos con una partición regular de con partes. Aquí corresponde al límite de partes en el lema de regularidad cuando . ${\displaystyle {\mathcal {P}}_{0}}$ ${\displaystyle \epsilon _{0}}$ ${\displaystyle G}$ ${\displaystyle \leq M(\epsilon _{0})}$ ${\displaystyle M(t)}$ ${\displaystyle \epsilon =t}$

Ahora bien, para , establecemos que sea un refinamiento regular de con partes. Por el argumento de incremento de energía, . Dado que la energía está limitada en , debe haber alguna tal que . Regresamos como . ${\displaystyle i=0,1,\cdots }$ ${\displaystyle {\mathcal {P_{i+1}}}}$ ${\displaystyle \epsilon _{|P_{i}|}}$ ${\displaystyle {\mathcal {P_{i}}}}$ ${\displaystyle \leq M(\epsilon _{|P_{i}|})|{\mathcal {P}}_{i}|}$ ${\displaystyle q({\mathcal {P}}_{i+1})\geq q({\mathcal {P}}_{i})}$ ${\displaystyle [0,1]}$ ${\displaystyle i\leq 1/\epsilon _{0}+1}$ ${\displaystyle q({\mathcal {P}}_{i+1})-q({\mathcal {P}}_{i})<\epsilon _{0}}$ ${\displaystyle ({\mathcal {P}}_{i},{\mathcal {P}}_{i+1})}$ ${\displaystyle ({\mathcal {P}},{\mathcal {Q}})}$

Por nuestra elección de las condiciones regulares y de refinamiento se cumplen. La condición de energía se cumple trivialmente. Ahora argumentamos a favor del número de partes. Usamos inducción para mostrar que , existe tal que . Al establecer , tenemos . Nótese que cuando , , entonces podríamos establecer y la afirmación es verdadera para . Al establecer , tenemos ${\displaystyle {\mathcal {P}}_{i+1},}$ ${\displaystyle \forall i}$ ${\displaystyle M_{i}}$ ${\displaystyle |{\mathcal {P}}_{i}|\leq M_{i}}$ ${\displaystyle M_{0}=M(\epsilon _{0})}$ ${\displaystyle |{\mathcal {P}}_{0}|\leq M_{0}}$ ${\displaystyle |P_{i}|\leq M_{i}}$ ${\displaystyle |P_{i+1}|\leq M(\epsilon _{|P_{i}|})|{\mathcal {P}}_{i}|\leq M(\epsilon _{|M_{i}|})M_{i}}$ ${\displaystyle M_{i+1}=M(\epsilon _{|M_{i}|})M_{i}}$ ${\displaystyle i+1}$ ${\displaystyle M=\max _{i\leq 1/\epsilon _{0}+2}M_{i}}$ ${\displaystyle |P|,|Q|\leq M.}$

Observaciones sobre la equidad

Una partición es equitativa si los tamaños de dos conjuntos cualesquiera difieren como máximo en . Al hacer equitativa la partición en cada ronda de iteración, el lema de la prueba de regularidad podría utilizarse para demostrar la versión equitativa del lema de regularidad. Y al reemplazar el lema de regularidad con su versión equitativa, la prueba anterior podría demostrar la versión equitativa del lema de regularidad fuerte, donde y son particiones equitativas. ${\displaystyle 1}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {Q}}}$

Un corolario útil

Declaración

Para cualquier secuencia infinita de constantes , existe tal que existe una partición y subconjuntos para cada una donde se satisfacen las siguientes propiedades: ${\displaystyle \epsilon _{0}\geq \epsilon _{1}\geq ...>0}$ ${\displaystyle \delta >0}$ ${\displaystyle {\mathcal {P}}={V_{1},...,V_{k}}}$ ${\displaystyle W_{i}\subset V_{i}}$ ${\displaystyle i}$

• ${\displaystyle |W_{i}|>\delta n}$
• ${\displaystyle (W_{i},W_{j})}$es -regular para cada par ${\displaystyle \epsilon _{|{\mathcal {P}}|}}$ ${\displaystyle 1\leq i\leq j\leq k}$
• ${\displaystyle |d(W_{i},W_{j})-d(V_{i},V_{j})|\leq \epsilon _{0}}$Para todos excepto parejas ${\displaystyle \epsilon _{0}|{\mathcal {P}}|^{2}}$ ${\displaystyle 1\leq i\leq j\leq k}$

Motivación

El corolario explora más profundamente el pequeño incremento de energía. Nos da una partición junto con subconjuntos con tamaños grandes de cada parte, que son regulares por pares. Además, la densidad entre los pares de subconjuntos correspondientes difiere "poco" de la densidad entre las partes correspondientes.

Prueba del corolario

Solo probaremos el resultado más débil, donde la segunda condición solo requiere ser regular para . La versión completa se puede probar eligiendo más subconjuntos de cada parte que sean en su mayoría regulares por pares y combinándolos. ${\displaystyle (W_{i},W_{j})}$ ${\displaystyle \epsilon _{|{\mathcal {P}}|}}$ ${\displaystyle 1\leq i<j\leq k}$

Sea . Aplicamos el lema de regularidad fuerte para encontrar equitativo que es una partición regular y equitativo que es un refinamiento regular de , tal que y . ${\displaystyle r=\epsilon _{0}^{3}/20}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle r}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle r/|P|^{4}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle q({\mathcal {Q}})-q({\mathcal {P}})\leq r}$ ${\displaystyle |{\mathcal {Q}}|\leq M}$

Ahora supongamos que , elegimos aleatoriamente un vértice de cada uno y dejamos que sea el conjunto que contiene en . Argumentamos que los subconjuntos satisfacen todas las condiciones con probabilidad . ${\displaystyle P=\{V_{1},\cdots ,V_{k}\}}$ ${\displaystyle v_{i}}$ ${\displaystyle V_{i}}$ ${\displaystyle W_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle W_{i}}$ ${\displaystyle >0}$

Al establecer la primera condición, es trivialmente verdadera ya que es una partición equitativa. Dado que, como máximo, los pares de vértices viven entre pares irregulares en , la probabilidad de que el par y sea irregular , por límite de unión, la probabilidad de que al menos un par , sea irregular . Nótese que ${\displaystyle \delta ={\frac {1}{2M}}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle {\frac {r}{|P|^{4}}}{\binom {n}{2}}\leq \epsilon _{0}{\frac {|V_{i}||V_{j}|}{3|P|^{2}}}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle W_{i}}$ ${\displaystyle W_{j}}$ ${\displaystyle \leq {\frac {1}{3|P|^{2}}}}$ ${\displaystyle W_{i}}$ ${\displaystyle W_{i}}$ ${\displaystyle \leq 1/3}$

${\displaystyle {\begin{aligned}r&\geq q({\mathcal {Q}})-q({\mathcal {P}})\\&=\sum _{i,j}{\frac {|V_{i}||V_{j}|}{n^{2}}}\mathbb {E} |d(W_{i},W_{j})-d(V_{i},V_{j})|^{2}\\&\geq \sum _{i,j}{\frac {1}{4|P|^{2}}}\mathbb {E} |d(W_{i},W_{j})-d(V_{i},V_{j})|^{2}\\&={\frac {1}{4|P|^{2}}}\mathbb {E} \sum _{i,j}|d(W_{i},W_{j})-d(V_{i},V_{j})|^{2}\end{aligned}}}$

Por lo tanto, según la desigualdad de Markov , con probabilidad , como máximo los pares podrían tener . Por el límite de unión, la probabilidad de que se cumplan todas las condiciones es . ${\displaystyle P(\sum _{i,j}|d(W_{i},W_{j})-d(V_{i},V_{j})|^{2}\geq 8|P|^{2}r)\leq 1/2}$ ${\displaystyle \geq 1/2}$ ${\displaystyle \epsilon _{0}|P|^{2}}$ ${\displaystyle d(W_{i},W_{j})-d(V_{i},V_{j})\geq \epsilon _{0}}$ ${\displaystyle \geq 1-1/2-1/3>0}$

Historia y extensiones

Construcción de Gowers para el límite inferior del lema de regularidad de Szemerédi

Szemerédi (1975) introdujo por primera vez una versión más débil de este lema, restringida a grafos bipartitos, para demostrar el teorema de Szemerédi , ^[14] y en (Szemerédi 1978) demostró el lema completo. ^[15] Rödl y sus colaboradores obtuvieron extensiones del método de regularidad a hipergrafos ^{[16] [17] [18]} y Gowers . ^{[19] [20]}

Más tarde (en 1997) , János Komlós , Gábor Sárközy y Endre Szemerédi demostraron en el lema de explosión ^{[21] [22]} que los pares regulares del lema de regularidad de Szemerédi se comportan como grafos bipartitos completos en las condiciones correctas. El lema permitió una exploración más profunda de la naturaleza de las incrustaciones de grandes grafos dispersos en grafos densos.

La primera versión constructiva fue proporcionada por Alon, Duke, Lefmann, Rödl y Yuster. ^[23] Posteriormente, Frieze y Kannan dieron una versión diferente y la extendieron a los hipergrafos. ^[24] Más tarde produjeron una construcción diferente debido a Alan Frieze y Ravi Kannan que utiliza valores singulares de matrices. ^[25] Se pueden encontrar algoritmos no deterministas más eficientes, como se detalla formalmente en el blog de Terence Tao ^[26] y se menciona implícitamente en varios artículos. ^{[27] [28] [29]}

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. ^[30] Terence Tao también ha proporcionado una prueba del lema basada en la teoría espectral, utilizando las matrices de adyacencia de grafos. ^[31]

No es posible demostrar una variante del lema de regularidad en la que todos los pares de conjuntos de particiones sean regulares. Algunos grafos, como los semigrafos , requieren que muchos pares de particiones (pero una pequeña fracción de todos los pares) sean irregulares. ^[1]

Una variante común en la definición de una partición -regular es requerir que todos los conjuntos de vértices tengan el mismo tamaño, mientras se recolectan los vértices sobrantes en un conjunto de "errores" cuyo tamaño es como máximo una fracción del tamaño del conjunto de vértices de . ${\displaystyle \varepsilon }$ ${\displaystyle V_{0}}$ ${\displaystyle \varepsilon }$ ${\displaystyle G}$

Alon, Fischer, Krivelevich y Szegedy demostraron una variante más fuerte del lema de regularidad al probar el lema de eliminación de grafos inducidos. Esto funciona con una secuencia de en lugar de solo una, y demuestra que existe una partición con un refinamiento extremadamente regular, donde el refinamiento no tiene un incremento de energía demasiado grande. ${\displaystyle \varepsilon }$

El lema de regularidad de Szemerédi puede interpretarse como que el espacio de todos los grafos está totalmente acotado (y por lo tanto es precompacto ) en una métrica adecuada (la distancia de corte ). Los límites en esta métrica pueden representarse mediante grafones ; otra versión del lema de regularidad simplemente establece que el espacio de los grafones es compacto . ^[32]

Referencias

1. Conlon, David ; Fox, Jacob (2012), "Límites para la regularidad de grafos y 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
2. 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
3. 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
4. Tao, Terence (2006), "Una variante del lema de eliminación de hipergrafos", Journal of Combinatorial Theory , Serie A, 113 (7): 1257–1280, arXiv : math/0503572 , doi : 10.1016/j.jcta.2005.11.006 , MR  2259060, S2CID  14337591
5. Alon, Noga ; Fischer, Eldar; Krivelevich, Michael ; Szegedy, Mario (2000), "Pruebas eficientes de gráficos grandes", Combinatorica , 20 (4): 451–476, doi :10.1007/s004930070001, MR  1804820, S2CID  44645628
6. Pelosin, Francesco (2018), Compresión de gráficos utilizando el método de regularidad (tesis de maestría), Universidad Ca' Foscari de Venecia , arXiv : 1810.07275
7. Fiorucci, Marco; Pelosin, Francesco; Pelillo, Marcello (febrero de 2020), "Separación de la estructura del ruido en gráficos grandes utilizando el lema de regularidad", Pattern Recognition , 98 : 107070, arXiv : 1905.06917 , Bibcode :2020PatRe..9807070F, doi :10.1016/j.patcog.2019.107070, S2CID  155100313
8. Frieze, Alan ; Kannan, Ravi (1999), "Aproximación rápida a matrices y aplicaciones", Combinatorica , 19 (2): 175–220, doi :10.1007/s004930050052, S2CID  15231198
9. Håstad, Johan (2001), "Algunos resultados de inaproximabilidad óptima", Journal of the ACM , 48 (4): 798–859, doi :10.1145/502090.502098, S2CID  5120748
10. Alon, Noga ; Fernandez de la Vega, W.; Kannan, Ravi; Karpinksi, Marek (2003), "Muestreo aleatorio y aproximación de MAX-CSP", Journal of Computer and System Sciences , 67 (2): 212–243, doi :10.1016/S0022-0000(03)00008-4, S2CID  34786604
11. Dellamonica, Domingos; Kalyanasundaram, Subrahmanyam; Martin, Daniel; Rödl, Vojtěch ; Shapira, Asaf (2012), "Muestreo aleatorio y aproximación de MAX-CSP", SIAM Journal on Discrete Mathematics , 26 (1): 15–29, doi :10.1137/110846373
12. Bansal, Nikhil; Williams, Ryan (2009), "Lemas de regularidad y algoritmos combinatorios", 50.º Simposio anual IEEE sobre fundamentos de la informática de 2009 , págs. 745-754, doi :10.1109/FOCS.2009.76, ISBN 978-1-4244-5116-6
13. Hajnal, András ; Maass, Wolfgang; Turán, Gyorgy (1988), "Sobre la complejidad de la comunicación de las propiedades de los grafos", Actas del vigésimo simposio anual de la ACM sobre teoría de la computación - STOC '88 , vol. 26, Association for Computing Machinery, págs. 186-191, doi :10.1145/62212.62228, ISBN 0897912640, Número de identificación del sujeto  17495443
14. Szemerédi, Endre (1975), "Sobre conjuntos de números enteros que no contienen k elementos en progresión aritmética", Polska Akademia Nauk. Instituto Matematyczny. Acta Arithmetica , 27 : 199–245, doi : 10.4064/aa-27-1-199-245 , SEÑOR  0369312.
15. Szemerédi, Endre (1978), "Particiones regulares de gráficos", Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) , vol. 260, París: CNRS, págs. 399–401, MR  0540024.
16. Frankl, Pedro ; Rödl, Vojtěch (2002), "Problemas extremos en sistemas establecidos", Algoritmos y estructuras aleatorias , 20 (2): 131–164, doi :10.1002/rsa.10017.abs, MR  1884430.
17. Rödl, Vojtěch ; Skokan, Jozef (2004), "Lema de regularidad para k -hipergrafos uniformes", Algoritmos y estructuras aleatorias , 25 (1): 1–42, doi :10.1002/rsa.20017, MR  2069663, S2CID  7458739.
18. Nagle, Brendan; Rödl, Vojtěch ; Schacht, Mathias (2006), "El lema de conteo para hipergrafos regulares k -uniformes", Random Structures & Algorithms , 28 (2): 113–179, CiteSeerX 10.1.1.378.8503 , doi :10.1002/rsa.20117, MR  2198495, S2CID  14126774 .
19. Gowers, WT (2006), "Cuasialeatoriedad, conteo y regularidad para hipergrafos 3-uniformes", Combinatorics, Probability and Computing , 15 (1–2): 143–184, doi :10.1017/S0963548305007236, MR  2195580, S2CID  14632612.
20. Gowers, WT (2007), "Regularidad de hipergrafos y el teorema multidimensional de Szemerédi", Anales de Matemáticas , Segunda serie, 166 (3): 897–946, arXiv : 0710.3032 , Bibcode :2007arXiv0710.3032G, doi :10.4007/annals.2007.166.897, MR  2373376, S2CID  56118006.
21. Komlós, János ; Sarközy, Gábor N .; Szemerédi, Endre (1997), "Lema ampliado", Combinatorica , 17 (1): 109–123, doi :10.1007/BF01196135, MR  1466579, S2CID  6720143
22. Komlós, János ; Sárközy, Gábor N .; Szemerédi, Endre (1998), "Una versión algorítmica del lema ampliado", 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
23. Alon, N.; Duke, RA; Lefmann, H.; Rödl, V.; Yuster, R. (1994), "Los aspectos algorítmicos del lema de regularidad", Journal of Algorithms , 16 : 80–109, CiteSeerX 10.1.1.102.681 , doi :10.1006/jagm.1994.1005 
24. Frieze, Alan M.; Kannan, Ravi (1996), "El lema de regularidad y los esquemas de aproximación para problemas densos", 37.º Simposio anual sobre fundamentos de la informática, FOCS '96, Burlington, Vermont, EE. UU., 14-16 de octubre de 1996 , IEEE Computer Society, págs. 12-20, doi : 10.1109/SFCS.1996.548459, ISBN 0-8186-7594-2, Número de identificación del sujeto  38681854
25. Frieze, Alan; Kannan, Ravi (marzo de 1999), "Un algoritmo simple para construir la partición de regularidad de Szemerédi", The Electronic Journal of Combinatorics , 6 (1), artículo R17, doi : 10.37236/1449
26. Tao, Terence (2009), Lema de regularidad de Szemeredi mediante particiones aleatorias
27. Alon, Noga ; Shapira, Asaf (2008), "Toda 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
28. Ishigami, Yoshiyasu (2006), Una regularización simple de hipergrafos , arXiv : math/0612838 , Bibcode :2006math.....12838I
29. Austin, Tim (2008), "Sobre variables aleatorias intercambiables y las estadísticas de gráficos grandes e hipergráficos", Probability Surveys , 5 : 80–145, arXiv : 0801.1698 , Bibcode :2008arXiv0801.1698A, doi :10.1214/08-PS124, S2CID  15421306
30. Tao, Terence (2006), "Revisitando el lema de regularidad de Szemerédi", Contribuciones a las matemáticas discretas , 1 (1): 8–28, arXiv : math/0504472 , Bibcode :2005math......4472T, doi : 10.11575/cdm.v1i1.61900 , MR  2212136.
31. Tao, Terence (2012), La prueba espectral del lema de regularidad de Szemeredi
32. Lovász, László ; Szegedy, Balázs (2007), "El lema de Szemerédi para el analista", Análisis geométrico y funcional , 17 : 252–270, doi : 10.1007/s00039-007-0599-6 , ISSN  1016-443X, MR  2306658, S2CID  15201345

Lectura adicional

• 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 tiene ochenta años, vol. 2 (Keszthely, 1993) , Bolyai Soc. Matemáticas. Stud., vol. 2, János Bolyai Matemáticas. 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 , vol. 2292, Springer, Berlín, págs. 84–112, doi :10.1007/3-540-45878-6_3, ISBN 978-3-540-43328-6, Sr.  1966181.

Enlaces externos

• Edmonds, Chelsea; Koutsoukou-Argyraki, Angeliki; Paulson, Lawrence C. Lema de regularidad de Szemerédi (Desarrollo de pruebas formales en Isabelle/HOL, Archive of Formal Proofs)