El lema de regularidad de Szemerédi

Question

Estoy tratando de entender la declaración del Lema de la Regularidad de Szemerédi como se explica aquí pero no soy capaz de entender lo que realmente significa. En particular el concepto de $ \epsilon $ -la regularidad y cómo se relaciona con el dibujo de bordes al azar no está claro para mí. Si alguien puede explicar la afirmación y el significado del teorema (no la prueba) estaría muy agradecido.

Gracias.

Answer 1

En cierto sentido $\epsilon-$ La regularidad es una forma de captar lo que significa que un gráfico sea "aleatorio". Para comparar, supongamos que $G$ es un grafo bipartito aleatorio en dos grandes subconjuntos $A$ y $B$ que tiene una probabilidad de borde $p$ (lo que significa que cada arista aparece con probabilidad $p$ de forma independiente; aquí $p$ es fijo). Aquí hay varias formas de intentar decir $G$ realmente "parece aleatorio".

-Los bordes de $G$ se reparten uniformemente: no hay grandes grupos ni grandes espacios vacíos en el gráfico.

-Cada gráfico bipartito pequeño $H$ aparece en $G$ sobre el número de veces que se espera que lo haga (aproximadamente $p^{E(H)}$ veces el número de apariciones en el grafo bipartito completo).

-Casi todos los vértices de $A$ tienen un grado más o menos $p |B|$ y casi todos los pares de vértices en $A$ tienen aproximadamente $p^2 |B|$ vecinos comunes (ser vecino de un vértice no hace que sea significativamente más o menos probable que sea vecino de otro vértice). Lo mismo ocurre si se intercambia $A$ y $B$ .

Resulta que las tres caracterizaciones anteriores son en realidad equivalente si se cuantifican de forma correcta (se trata de un fenómeno conocido como "cuasirandomismo"). La idea de $\epsilon-$ regularidad es cuantificar la primera de estas propiedades.

Para cada $S \subseteq A$ y $T \subseteq B$ se espera que nuestro gráfico aleatorio tenga $p|S| |T|$ bordes que conectan $S$ con $T$ . Reformulando esto ligeramente, el densidad $d(S,T):=\frac{|E(S,T)|}{|S||T|}$ es por término medio igual a $p$ . Así que podemos esperar que nuestra definición "aleatoria" sea algo así como

" Por cada $S$ y $T$ tenemos $|d(S,T)-p|<\epsilon$ "

Pero hay un problema aquí... si $S$ y $T$ son demasiado pequeños, no hay esperanza de que esto se mantenga (imagine el caso extremo en el que $|S|=|T|=1$ ). Así que añadiremos una condición adicional: Sólo queremos que el límite anterior se mantenga para subconjuntos de tamaño al menos $\epsilon n$ . La idea es que si un subconjunto pequeño está fuera de lugar, no tendrá demasiado impacto en cosas como el recuento de subconjuntos de todos modos, así que podríamos preocuparnos sólo de los subconjuntos grandes. Esta definición modificada es la que se utiliza para $\epsilon$ -regularidad en el Lemma de Szemerédi.

Lo que dice el propio Lemma es que cualquier gráfico denso puede ser aproximado por un limitado número de estos $\epsilon-$ gráficos regulares (dependiendo sólo de $\epsilon$ no en el tamaño del gráfico original). "Aproximado por" significa aquí que puede ser necesario borrar un número pequeño ( $\epsilon n^2$ ), pero una vez que los elimines te quedarás con un gráfico en $k$ subconjuntos $A_1, A_2, \dots, A_k$ de vértices, de modo que para cada $i$ y $j$ el gráfico entre $A_i$ y $A_j$ es aleatorio en todos los sentidos anteriores [El valor de $p$ puede ser diferente para cada par $(i,j)$ ].