Lema de regularidad de Szemeredi

El lema de regularidad de Szemeredi es un lema de la teoría general de grafos , que establece que los vértices de cualquier gráfico suficientemente grande se pueden dividir en un número finito de grupos, de modo que casi todos los gráficos bipartitos que conectan vértices de dos grupos diferentes tienen bordes distribuidos casi uniformemente entre los vértices. En este caso, el número mínimo requerido de grupos en los que se debe dividir el conjunto de vértices del gráfico puede ser arbitrariamente grande, pero el número de grupos en la partición siempre está acotado desde arriba.

Hablando de manera informal, el lema afirma la presencia de un gran número de grandes estructuras pseudoaleatorias en absolutamente cualquier gráfico de un tamaño suficientemente grande.

El lema fue probado por Endre Szemeredi en 1975. [1] [2]

Redacción

El concepto de ε-uniformidad

Sea dado un grafo bipartito cuyas aristas conectan vértices del conjunto con vértices del conjunto . $G=(W=U\sqcup V,E)$ $tu$ $V$

Porque denotamos por la densidad de la distribución de aristas entre estos conjuntos, es decir, $S\subconjunto U,T\subconjunto V$ ${\ estilo de visualización d (S, T)}$

d(S,T)={\frac {\#\left\lbrace {(u,v)\in E:u\in S,v\in T}\right\rbrace}{|S|| T|}}

Definición [1] [3]

Un grafo bipartito se llama -uniforme si para cualquiera que satisfaga las condiciones , la desigualdad $G=(U\sqcup V,E)$ $\varepsilon$ $S\subconjunto U,T\subconjunto V$ $|S|>\varepsilon |U|,|T|>\varepsilon |V|$

|d(S,T)-d(U,V)|\leq\varepsilon

Hay varias definiciones que son equivalentes a esta (equivalente en el sentido de la existencia de una dependencia monótona en una definición de otra cuando las dos definiciones son equivalentes), pero todas usan una cantidad y algún tipo de comparación cuantitativa de sus valores . para diferentes pares de . $\varepsilon$ $\varepsilon$ ${\ estilo de visualización d (S, T)}$ $S T$

Obviamente, los gráficos bipartitos completos y vacíos son -regulares para cualquier . Cabe señalar que, en términos generales, esto no es cierto para un grafo bipartito arbitrario que es regular en el sentido habitual (como contraejemplo, podemos considerar, por ejemplo, la unión de varios grafos regulares que no se cortan en el conjunto de vértices). $\varepsilon$ $\varepsilon >0$

$\varepsilon$ -Los grafos uniformes para un determinado a veces también se denominan pseudoaleatorios , ya que son similares a los generados aleatoriamente en términos de la distribución uniforme de las aristas entre los vértices. $\varepsilon$

Enunciado del lema

Lema de regularidad de Szemeredi [3] [4]

Para cualquier , existen tales que para cualquier grafo con un número de vértices existe una partición en partes lo más iguales posible en tamaño , tal que para pares de estas partes el grafo bipartito de aristas que se encuentran entre ellas es -regular. ${\displaystyle\varepsilon>0,\m\geq 2}$ ${\ Displaystyle M, n_ {0}}$ $G=(V,E)$ $|V|>n_{0}$ $V=V_{1}\sqcup \dots \sqcup V_{k}\ (m\leq k\leq M)$ $|V_{1}|=\puntos =|V_{k-1}|\geq |V_{k}|$ $(1-\varepsilon){\binom {k}{2))$ $\varepsilon$

Notas

El lema de Szemeredi no impone ninguna restricción sobre los bordes entre los vértices del mismo conjunto de particiones.

El enunciado del lema no es trivial solo para gráficos con un número suficientemente grande de aristas. Si , cualquiera de sus subgráficos bipartitos en partes con dimensiones también será escaso (su densidad no excederá ) - por lo tanto, la condición de la diferencia de densidad siempre se cumplirá. [5] $|E|\leq {\frac {\varepsilon^{3}}{k^{2}}}|V|^{2}$ ${\frac {\varepsilon}{k}}|V|$ $\varepsilon$

También cabe señalar que la mención de la misma variable en dos características diferentes -el índice de regularidad y la proporción de subgrafos -bipartitos regulares- no crea ninguna relación adicional entre estas características. Tal formulación también se derivaría de una formulación más débil, donde se requeriría, por ejemplo, que los bordes se distribuyan regularmente solo entre pares de conjuntos, donde para (es decir, incluso para ). En este caso, para lograr la formulación original, bastaría considerar , ya que -regularidad de la gráfica implica -regularidad en . $\varepsilon$ $\varepsilon$ $\varepsilon$ $(1-\eta){\binom {k}{2))$ ${\ estilo de visualización \ eta = \ eta (\ varepsilon) \ a 0}$ ${\ estilo de visualización \ varepsilon \ a 0}$ $\eta >\varepsilon$ ${\ estilo de visualización \ varepsilon _ {0} = \ eta ^ {-1} (\ varepsilon)}$ $\varepsilon_{0}$ $\varepsilon$ ${\ estilo de visualización \ varepsilon _ {0} < \ varepsilon}$

Prueba

Algoritmo de partición

La partición se realiza mediante un algoritmo codicioso.

Primero, se elige una partición arbitraria de vértices en conjuntos , donde: $V_{1},\puntos,V_{k}$

$|V_{1}|=\puntos =|V_{k-1}|>|V_{k}|$
$k=\max \left({{\frac {1}{\varepsilon)),m}\right)$

Además, en cada iteración del algoritmo, se genera una nueva partición de cierta manera a partir de la partición existente con tamaños de partes más pequeños y una gran cantidad de ellas. Se construye como una subdivisión de la partición original, pero luego se normaliza mediante pequeños arreglos para que los tamaños de todas las partes (excepto, quizás, una) sean iguales.

Tal transformación continúa hasta que la partición resultante en conjuntos contiene al menos pares de conjuntos cuyos gráficos bipartitos no son regulares. La transición de una partición a la siguiente ocurre de tal manera que es posible probar que el algoritmo se detiene exactamente después de un número finito y limitado por un número constante (dependiendo de y ) de pasos. Además, el número de conjuntos resultantes en la partición en cada iteración específica del algoritmo también está limitado, por lo que el número máximo de conjuntos que se pueden formar en la última iteración será el valor deseado . [3] $k'$ $\varepsilon {\binom {k'}{2))$ $\varepsilon$ $\varepsilon$ $metro$ $METRO$

Transición de dividir a subdividir

Que la partición actual no satisfaga las condiciones del lema, es decir, hay pares para los que el grafo bipartito entre ellos no es -regular. Denotemos esta condición como . ${\mathcal {P}}=(V_{1},\dots,V_{k})$ $\varepsilon {\binom {k}{2))$ ${\ estilo de visualización (V_ {i}, V_ {j}), i \ no = j}$ $\varepsilon$ $P_{\varepsilon}(V_{i},V_{j})$

Si , entonces hay algunos subconjuntos "problemáticos" particulares que violan la regularidad del gráfico bipartito que conecta estos componentes. Es decir, para ellos: $P_{\varepsilon}(V_{i},V_{j})$ ${\displaystyle S_{ij}\en V_{i},S_{ji}\en V_{j))$ $\varepsilon$

$|S_{ij}|>\varepsilon |V_{i}|$
$|S_{ji}|>\varepsilon |V_{j}|$
$|d(S_{ij},S_{ji})-d(V_{i},V_{j})|>\varepsilon$

Parece una idea razonable deshacerse de estos subconjuntos problemáticos simplemente separándolos en un componente separado, formando un cuádruple en lugar de un par de componentes . Sin embargo, un mismo componente puede entrar en conflicto con varios otros componentes a la vez, por lo que la división debe hacerse no uno por uno, sino por varios conjuntos de problemas a la vez. ${\ estilo de visualización (V_ {i}, V_ {j})}$ $(S_{ij},V_{i}\setminus S_{ij},S_{ji},V_{j}\setminus S_{ji})$ $V_i$

Para formalizar este proceso, para cada componente individual , se consideran todos los subconjuntos "problemáticos" que surgen en él: $V_i$

{\mathcal {S}}(V_{i})=\left\lbrace {S_{ij}:1\leq j\leq k,P_{\varepsilon}(V_{i},V_{j} )}\right\rbrace

y la σ-álgebra formada sobre (es decir, se subdivide en partes tales que dos vértices cualesquiera, uno de los cuales pertenece a unos y el otro no, acaban en distintas partes de la subdivisión). ${\mathcal {S}}(V_{i})$ $V_i$ $V_i$ $S_{{ij}}$

Dado que para un individuo no hay más subconjuntos problemáticos (y, en consecuencia, no más elementos del σ-álgebra construidos sobre ellos), como resultado, no se forman más nuevos a partir de un componente. $V_i$ $k-1$ $2^{k-1}$ $2^{k-1}$

Si subdivide cada componente de esta manera , obtiene una nueva subdivisión . $V_i$ ${\mathcal {P))'$

A continuación, debe alinear los tamaños de los componentes (de los cuales no hay más de ). Para hacer esto, cada uno de sus componentes se puede dividir en nuevos componentes del tamaño (y, posiblemente, un componente restante de un tamaño más pequeño: el "resto"), y todos los vértices de los "restos" se pueden combinar arbitrariamente en nuevos componentes del mismo tamaño y, posiblemente, un tamaño de componente más pequeño. ${\mathcal {P))'$ ${\ Displaystyle k2^{k-1}}$ $\left\lfloor {\frac {n}{{(k2^{k-1})}^{2))}\right\rfloor$ $\left\lfloor {\frac {n}{{(k2^{k-1})}^{2))}\right\rfloor$

La partición resultante será el resultado de una iteración del algoritmo.

Estimación del número de pasos en un algoritmo

La prueba de que el algoritmo se detiene después de un número finito de pasos se lleva a cabo mediante la introducción de una función potencial, un valor numérico que depende de la partición actual, y el seguimiento de su cambio al cambiar las iteraciones del algoritmo.

"Potencial" puede definirse, por ejemplo, como sigue:

\Phi ({\mathcal {P}})=\sum \limits _{1\leq i<j\leq |{\mathcal {P}}|}{{\frac {|V_{i}| |V_{j}|}{|V|^{2}}}d(V_{i},V_{j})^{2}}

Esta función tiene varias propiedades importantes:

$0\leq \Phi ({\mathcal {P))\leq 1$

si la partición se forma subdividiendo un componente en dos conjuntos y , entonces ${\mathcal {Q}}$ ${\mathcal {P}}=(V_{1},\dots,V_{k})$ $V_{1}$ $S\subconjunto V_{1}$ $V_{1}\setminus S$ $\Phi ({\mathcal {Q}})\geq \Phi ({\mathcal {P}})$

Prueba

Esto se sigue de la desigualdad , que es cierta para , que implica la desigualdad $(x+y)^{2}\leq {\frac {1}{\alpha }}x^{2}+{\frac {1}{\beta }}y^{2}$ ${\ estilo de visualización \ alfa + \ beta = 1}$

{\frac {E(V_{1},V_{j})^{2}}{|V_{1}|}}\leq {\frac {E(S,V_{j})^{ 2}}{|S|}}+{\frac {E(V_{1}\setminus S,V_{j})^{2}}{|V_{1}\setminus S|}}

para la partición del algoritmo descrito en la sección anterior, es cierto ${\mathcal {P))'$ $\Phi ({\mathcal {P))')>\Phi ({\mathcal {P)))+\Omega (\varepsilon ^{5})$

si se obtiene una partición a partir de una partición reparticionando los vértices de varios componentes en otros componentes (no necesariamente por una subpartición), entonces ${\mathcal {Q}}$ ${\mathcal {P}}=(V_{1},\dots,V_{k})$ $V_{1},\puntos,V_{s}$ $\Phi ({\mathcal {Q))\geq \Phi ({\mathcal {P)))-{\frac {|V_{1}|+\dots +|V_{s}|}{ | V|}}$

Prueba

Basta con mostrar que la unión reduce como mucho (la subdivisión adicional no reduce , según otra propiedad). $V_{1},\puntos,V_{s}$ $\Fi$ ${\frac {|V_{1}|+\puntos +|V_{s}|}{|V|}}$ $\Fi$

Cuando se combinan los componentes , algunos términos desaparecen de la suma y aparecen otros nuevos. Como todos los términos son positivos, basta con considerar los que se anulan. La suma de tales términos es fácil de estimar: $\Fi$

$\sum \limits _{i=1}^{s}{\sum \limits _{j>i}({\frac {|V_{i}||V_{j}|}{|V| ^{2}}}d(V_{i},V_{j})}}\leq \sum \limits _{i=1}^{s}{|V_{i}|\sum \limits _{j >i}{\frac {|V_{j}|}{|V|^{2))))\leq {\frac {1}{|V|^{2))}\sum \limits _{i =1}^{s}{|V_{i}|\sum \limits _{j=1}^{k}{|V_{j}|}}={\frac {|V_{1}|+\ puntos +|V_{s}|}{|V|}}$

Dado que, al obtener una nueva partición, según el algoritmo, no se reconstruyen más que vértices en la subdivisión, y dado que para cualquier constante suficientemente grande , se deduce de las propiedades de la función potencial que el algoritmo se detendrá después de los pasos. ${\mathcal {P))'$ $k2^{k-1}\izquierda\lpiso {\frac {n}{{(k2^{k-1})}^{2))}\derecha\rpiso \leq {\frac {n} {k2^{k-1}}}$ ${\frac{1}{k2^{k-1}}}<c\varepsilon^{5}$ $k$ $C$ $O\left({\frac {1}{\varepsilon ^{5))}\right)$

En el primer trabajo sobre este tema, Szemeredi utilizó una función potencial ligeramente diferente [1] :

\Phi ({\mathcal {P)))={\frac {1}{|{\mathcal {P}}|^{2}}}\sum \limits _{1\leq i<j\ leq |{\mathcal {P}}|}{d(V_{i},V_{j})^{2}}

A pesar de las diferencias, ambas funciones comparten la idea de promediar las densidades al cuadrado.

Estimación del tamaño de una partición

Como se desprende de la descripción del algoritmo, la estimación superior para el número de componentes en la partición en la -ésima iteración del algoritmo se expresa mediante la relación recursiva $norte$

a_{n}={a_{n}}^{2}2^{a_{n}-1}

El número de iteraciones con las que funcionará el algoritmo se estima en . $O\left({\frac {1}{\varepsilon ^{5))}\right)$

Por lo tanto, el número total de componentes solo puede estimarse elevando una torre a la potencia de la altura . ${\displaystyle 2^{2^{\cdot ^{\cdot ^{\cdot ^{k))))))$ $O\left({\frac {1}{\varepsilon ^{5))}\right)$

Algoritmo eficiente de búsqueda dividida

La demostración matemática típica del lema de Szemeredi no se preocupa por la complejidad computacional del algoritmo.

Sin embargo, un grupo de cinco matemáticos en un documento separado investigó el aspecto algorítmico de encontrar la partición deseada; en particular, describieron un algoritmo que permite encontrar una partición de un gráfico de vértice en el tiempo para fijo y . El tiempo de ejecución de su algoritmo está limitado por el tiempo de multiplicación de dos matrices que consisten en ceros y unos. Además, el algoritmo se puede paralelizar y ejecutar en el tiempo en un polinomio que depende del número de procesadores. [6] $norte$ $O(n^{2.376})$ $\varepsilon$ $metro$ $n\veces n$ $O(\registro{n})$ $norte$

Límite inferior en el tamaño de la partición requerida

En 1997, William Gowers demostró que la estimación del tamaño del número de componentes en la partición requerida no se puede mejorar más que hasta la altura de la torre del exponente . A saber, mostró que siempre existe un gráfico, cuya partición en un número menor de partes no satisface las condiciones del lema. ${\displaystyle 2^{2^{\cdot ^{\cdot ^{\cdot ^{k))))))$ $O\left({\log {\left({\frac {1}{\varepsilon }}\right)))\right)$

Consideró una noción aún más general de -regularidad, donde un subconjunto de partes de un gráfico bipartito , cuya desviación de densidad está limitada por la definición, está restringida en lugar de , y también demostró la existencia de un contraejemplo para ello. $(\varepsilon, \delta)$ $S\subconjunto U,T\subconjunto V$ $|S|\geq \delta |U|,|T|\geq \delta |V|$ $|S|\geq \varepsilon |U|,|T|\geq \varepsilon |V|$

Gowers usó un método probabilístico para encontrar un contraejemplo , por lo que su prueba no es constructiva . El documento consideró gráficos ponderados con pesos del intervalo . Para tales gráficos, podemos considerar una formulación completamente similar del lema, donde la densidad se considerará la suma de los pesos de los bordes en lugar de su número. Al construir un contraejemplo en forma de un gráfico ponderado, Gowers también mostró que un gráfico aleatorio generado por el esquema de Bernoulli con probabilidades de borde correspondientes a los pesos en este gráfico ponderado será con una alta probabilidad un contraejemplo para el lema habitual (además, con una alta probabilidad, las densidades no se desviarán mucho de densidades similares en un gráfico ponderado, siempre que sean lo suficientemente grandes). [7] ${\ estilo de visualización (0; 1)}$ ${\ estilo de visualización d (U, V)}$ ${\ estilo de visualización d (U, V)}$ ${\ estilo de visualización | U |}$ $|V|$

diseño de gowers

Un gráfico ponderado, que sirve como contraejemplo del lema con la definición habitual de -regularidad, se construye como una combinación con diferentes pesos de varios gráficos grandes específicamente dispuestos. Al construir cada gráfico siguiente a partir de este conjunto, los vértices se combinan en grupos cada vez más grandes de igual tamaño, de modo que los vértices de dos grupos diferentes están conectados entre sí mediante un gráfico bipartito completo o no están conectados en absoluto (los nuevos grupos siempre son unión de las anteriores). $\varepsilon$

Deje que los vértices se dividan en grupos del mismo tamaño. Combina estos grupos en bloques. $X_{1},\puntos,X_{s}$

B_{1}=(X_{1},\puntos,X_{t})

B_{2}=(X_{t+1},\puntos,X_{2t})

\puntos

B_{k}=(X_{(m-1)t+1},\puntos,X_{s})

donde (supongamos que es un número entero). $k={\frac{s}{t))$

Para cada par de bloques diferentes, elegimos una partición de grupos de en dos partes y una partición de grupos de en dos partes. Agregue al gráfico todos los bordes de gráficos bipartitos completos y . ${\ estilo de visualización (B_ {i}, B_ {j})}$ ${\displaystyle B_{i}=B_{ij}^{(1)}\sqcup B_{ij}^{(2)))$ $Bi}$ ${\displaystyle B_{j}=B_{ji}^{(1)}\sqcup B_{ji}^{(2)))$ $b_j$ ${\ estilo de visualización (B_{ij}^{(1)},B_{ji}^{(1)})}$ ${\ estilo de visualización (B_{ij}^{(2)},B_{ji}^{(2)})}$

Si se eligen particiones de tal manera que ninguna , perteneciente a la misma , no tenga más bloques en los que haya vértices adyacentes a ambas, entonces con la selección correcta , la construcción resultante será la construcción de Gowers. Pero esta es la construcción de un solo gráfico: para construir el siguiente gráfico, los bloques se colocan en lugar de grupos y todo el proceso comienza de nuevo hasta que todos los vértices se combinan en un grupo. ${\ estilo de visualización X_ {j}, X_ {j'))$ $Bi}$ ${\frac{3}{4}}k$ $s$ $t$ ${\displaystyle B_{1},\puntos,B_{m))$ $X_{1},\puntos,X_{s}$

La cadena de gráficos resultante se combina en un gráfico ponderado de acuerdo con la fórmula (los gráficos en los que los grupos combinados de vértices son muy grandes tienen los mayores pesos). $G_{1},\puntos,G_{s}$ $G=\sum \limits _{r=1}^{s}{2^{rs-1}G_{r))$

El contraejemplo de -regularidad se construye de manera similar, pero con algunas diferencias: $(\varepsilon, \delta)$

los grupos dentro de un bloque no se dividen en dos, en un número arbitrario de conjuntos ; $Bi}$ $d$ ${\displaystyle B_{i}=B_{i}^{(1)}\sqcup \dots \sqcup B_{i}^{(d)))$

el número de grupos en cada conjunto está limitado por el tamaño (no deben ser demasiado pequeños); ${\displaystyle B_{i}^{(j)))$

al final, los gráficos resultantes se combinan no en forma de un gráfico ponderado, sino por un "o" exclusivo (el gráfico final incluye solo aquellos bordes que estaban presentes en un número impar de gráficos ). $G_{1},\puntos,G_{s}$ $G_{r},1\leqr\leqs$

Generalizaciones

En 2007, William Gowers generalizó el lema de regularidad a las hipergrafías y utilizó la generalización para probar el teorema multidimensional de Szemerédy. [ocho]

También existe un análogo del lema de Szemeredi para gráficos dispersos (en la formulación habitual, el lema es trivial para dichos gráficos, ya que cualquier partición satisface las condiciones necesarias). [9]

Aplicaciones

La aplicación más famosa del lema de regularidad es para la prueba combinatoria del teorema de Szemeredi y sus generalizaciones (por ejemplo, el teorema de la esquina ). [5] Sin embargo, el lema y sus ideas también tienen una serie de aplicaciones en la teoría general de grafos [10] - El primer artículo de Szemeredy sobre este lema se cita en más de 500 artículos sobre diversos temas. [una]

También de particular interés es el lema de eliminación de triángulos , que se deriva del lema de regularidad y se utiliza en el curso de la demostración del teorema de Szemeredi.

Véase también

Endre Semeredy
Teorema de Szemeredi
Lema de eliminación de triángulos

Notas

↑ 1 2 3 4 E. Szemeredi, "Particiones regulares de gráficos", Departamento de Informática, Facultad de Humanidades y Ciencias, Universidad de Stanford, 1975
↑ E. Szemeredi, "Particiones regulares de gráficos", Departamento de Informática, Facultad de Humanidades y Ciencias, Universidad de Stanford, 1975 . Consultado el 29 de julio de 2018. Archivado desde el original el 23 de febrero de 2020. (indefinido)
↑ 1 2 3 "Mini curso de combinatoria aditiva", notas de conferencias de la Universidad de Princeton . Consultado el 29 de julio de 2018. Archivado desde el original el 29 de agosto de 2017. (indefinido)
↑ Laboratorio de matemáticas. Chebyshev, curso de conferencias "Combinatoria aditiva", conferencia 3
↑ 1 2 I. D. Shkredov, "Teorema y problemas de Szemeredi sobre progresiones aritméticas" . Consultado el 29 de julio de 2018. Archivado desde el original el 24 de julio de 2018. (indefinido)
↑ N. Alon, R.A. Duke, H. Lefmann, V. Rodl, R. Yusterk, "Los aspectos algorítmicos del lema de regularidad", Universidad de Tel Aviv . Consultado el 29 de julio de 2018. Archivado desde el original el 8 de agosto de 2017. (indefinido)
↑ WT Gowers, "Límites inferiores del tipo de torre para el lema de uniformidad de Szemerédi", Análisis geométrico y funcional GAFA, mayo de 1997, Volumen 7, Número 2, págs. 322–337 . Consultado el 29 de julio de 2018. Archivado desde el original el 18 de junio de 2018. (indefinido)
↑ WT Gowers, "La regularidad del hipergráfico y el teorema multidimensional de Szemer´edi", Annals of Mathematics, 166 (2007), 897–946 . Consultado el 29 de julio de 2018. Archivado desde el original el 20 de julio de 2018. (indefinido)
↑ Y. Kohayakawa, "Lema de regularidad de Szemeredi para gráficos dispersos" . Consultado el 29 de julio de 2018. Archivado desde el original el 10 de junio de 2018. (indefinido)
↑ Janos Komlos, Miklos Simonovits, "Lema de regularidad de Szemeredi y sus aplicaciones en la teoría de grafos", Universidad de Rutgers, Academia de Ciencias de Hungría . Fecha de acceso: 29 de julio de 2018. Archivado desde el original el 23 de abril de 2005. (indefinido)

diccionarios y enciclopedias	Britannica (en línea)