Lema de explosión

Lema importante en la teoría de grafos extremales

El lema de la explosión , demostrado por János Komlós , Gábor N. Sárközy y Endre Szemerédi en 1997, ^{[1] [2]} es un resultado importante en la teoría de grafos extremales , particularmente en el contexto del método de regularidad . Afirma que los pares regulares en el enunciado del lema de regularidad de Szemerédi se comportan como grafos bipartitos completos en el contexto de la incrustación de grafos generadores de grado acotado .

Definiciones y declaraciones

Para enunciar formalmente el lema de la explosión, primero debemos definir la noción de par superregular .

Pares superregulares

Un par de subconjuntos del conjunto de vértices se denomina -superregular si para cada y satisface ${\displaystyle (A,B)}$ ${\displaystyle (\varepsilon ,\delta )}$ ${\displaystyle X\subset A}$ ${\displaystyle Y\subset B}$

${\displaystyle |X|>\varepsilon |A|}$y ${\displaystyle |Y|>\varepsilon |B|}$

tenemos

${\displaystyle e(X,Y)>\delta |X||Y|}$

y además,

${\displaystyle \deg(a)>\delta |B|}$para todos y para todas . ^[1] ${\displaystyle a\in A}$ ${\displaystyle \deg(b)>\delta |A|}$ ${\displaystyle b\in B}$

Aquí se denota el número de pares con y tales que es una arista. ${\displaystyle e(X,Y)}$ ${\displaystyle (x,y)}$ ${\displaystyle x\in X}$ ${\displaystyle y\in Y}$ ${\displaystyle \{x,y\}}$

Declaración del lema de la explosión

Dado un grafo de orden y parámetros positivos , existe un positivo tal que se cumple lo siguiente. Sean números enteros positivos arbitrarios y reemplacemos los vértices de con conjuntos disjuntos de tamaños por pares (explosión). Construimos dos grafos en el mismo conjunto de vértices . El primer grafo se obtiene reemplazando cada arista de con el grafo bipartito completo entre los conjuntos de vértices correspondientes y . Un grafo más disperso G se construye reemplazando cada arista con un par -superregular entre y . Si un grafo con es integrable en entonces ya es integrable en G. ^[1] ${\displaystyle R}$ ${\displaystyle r}$ ${\displaystyle \delta ,\Delta }$ ${\displaystyle \varepsilon =\varepsilon (\delta ,\Delta ,r)}$ ${\displaystyle n_{1},n_{2},\dots ,n_{r}}$ ${\displaystyle v_{1},v_{2},\dots ,v_{r}}$ ${\displaystyle R}$ ${\displaystyle V_{1},V_{2},\dots ,V_{r}}$ ${\displaystyle n_{1},n_{2},\dots ,n_{r}}$ ${\displaystyle V=\bigcup V_{i}}$ ${\displaystyle \mathbf {R} }$ ${\displaystyle \{v_{i},v_{j}\}}$ ${\displaystyle R}$ ${\displaystyle V_{i}}$ ${\displaystyle V_{j}}$ ${\displaystyle \{v_{i},v_{j}\}}$ ${\displaystyle (\varepsilon ,\delta )}$ ${\displaystyle V_{i}}$ ${\displaystyle V_{j}}$ ${\displaystyle H}$ ${\displaystyle \Delta (H)\leq \Delta }$ ${\displaystyle \mathbf {R} }$

Bosquejo de prueba

La prueba del lema de la explosión se basa en el uso de un algoritmo voraz aleatorio (RGA) para incrustar los vértices de en secuencialmente. Luego, el argumento procede limitando la tasa de falla del algoritmo de modo que sea menor que 1 (y de hecho ) para una elección adecuada de parámetros. Esto significa que existe una probabilidad distinta de cero de que el algoritmo tenga éxito, por lo que debe existir una incrustación. ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle o(1)}$

Intentar incrustar directamente todos los vértices de de esta manera no funciona porque el algoritmo puede quedarse atascado cuando solo quede una pequeña cantidad de vértices. En su lugar, dejamos de lado una pequeña fracción del conjunto de vértices, llamada vértices de búfer , e intentamos incrustar el resto de los vértices. Los vértices de búfer se incrustan posteriormente utilizando el teorema de matrimonio de Hall para encontrar una coincidencia perfecta entre los vértices de búfer y los vértices restantes de . ${\displaystyle H}$ ${\displaystyle G}$

Notación

Tomamos prestada toda la notación introducida en las secciones anteriores. Sea . Como se puede incrustar en , podemos escribir con para todo . Para un vértice , sea . Para , ${\displaystyle n=|V(G)|=\sum n_{i}}$ ${\displaystyle H}$ ${\displaystyle \mathbf {R} }$ ${\displaystyle V(H)=X=\bigcup _{i\leq r}X_{i}}$ ${\displaystyle |X_{i}|=|V_{i}|}$ ${\displaystyle i}$ ${\displaystyle x\in X_{i}}$ ${\displaystyle V_{x}}$ ${\displaystyle V_{i}}$ ${\displaystyle x\in X_{i},y\in X_{j}}$

${\displaystyle d_{xy}={\frac {e(V_{i},V_{j})}{|V_{i}||V_{j}|}}}$

denota la densidad de aristas entre los conjuntos de vértices correspondientes de . es la incrustación que deseamos construir. es el tiempo final después del cual concluye el algoritmo. ${\displaystyle G}$ ${\displaystyle \phi :V(G)\to V(H)}$ ${\displaystyle T}$

Esquema del algoritmo

Fase 0: Inicialización

1. Elija con avidez el conjunto de vértices de búfer de entre los vértices de como un conjunto máximo de vértices distanciados al menos entre sí ${\displaystyle B}$ ${\displaystyle H}$ ${\displaystyle 4}$
2. Ordena los vértices restantes (los de ) en una lista , colocando los vecinos de primero. ${\displaystyle H\setminus B}$ ${\displaystyle L}$ ${\displaystyle B}$
3. Declarar una cola de vértices priorizados actualmente, que inicialmente está vacía. ${\displaystyle q}$
4. Declare una matriz de conjuntos indexados por los vértices de , que representan el conjunto de todos los "espacios libres" de , es decir, el conjunto de vértices desocupados en el vértice podría asignarse sin violar ninguna de las condiciones de adyacencia de los vecinos ya integrados de en . se inicializa a . ${\displaystyle F_{z}}$ ${\displaystyle H}$ ${\displaystyle z}$ ${\displaystyle G}$ ${\displaystyle z}$ ${\displaystyle z}$ ${\displaystyle H}$ ${\displaystyle F_{z}}$ ${\displaystyle V_{z}}$

Fase 1: Incorporación aleatoria y codiciosa

1. Elija un vértice del conjunto de vértices restantes de la siguiente manera: ${\displaystyle x}$
   1. Si la cola de vértices priorizados no está vacía, entonces elija el vértice de ${\displaystyle q}$ ${\displaystyle q}$
   2. De lo contrario, elija un vértice de la lista de vértices restantes. ${\displaystyle L}$
2. Elija la imagen para el vértice aleatoriamente del conjunto de opciones "buenas", donde una opción es buena solo si ninguno de los nuevos conjuntos libres difiere demasiado en tamaño del valor esperado. ${\displaystyle \phi (x)}$ ${\displaystyle G}$ ${\displaystyle x}$ ${\displaystyle F_{z}(t)}$
3. Actualizar los conjuntos libres y colocar los vértices cuyos conjuntos libres se han vuelto demasiado pequeños con respecto a su tamaño en la última actualización en el conjunto de vértices priorizados ${\displaystyle F_{z}(t)}$ ${\displaystyle q}$
4. Anular si la cola contiene una fracción suficientemente grande de cualquiera de los conjuntos ${\displaystyle q}$ ${\displaystyle X_{i}}$
5. Si aún quedan vértices que no son de búfer para incrustar en o , actualice el tiempo y vuelva al paso 1; de lo contrario, pase a la fase 2. ${\displaystyle L}$ ${\displaystyle q}$ ${\displaystyle t}$

Fase 2: Coincidencia de Kőnig-Hall para los vértices restantes

Considere el conjunto de vértices que quedan por incrustar, que es precisamente , y el conjunto de puntos libres . Forme un grafo bipartito entre estos dos conjuntos, uniendo cada uno a , y encuentre una correspondencia perfecta en este grafo bipartito. Incruste de acuerdo con esta correspondencia. ${\displaystyle B}$ ${\displaystyle \bigcup _{b\in B}F_{b}(T)}$ ${\displaystyle b\in B}$ ${\displaystyle F_{b}(T)}$

Prueba de corrección

La prueba de la exactitud es técnica y bastante compleja, por lo que omitimos los detalles. El argumento central se desarrolla de la siguiente manera:

Paso 1: la mayoría de los vértices son buenos y hay suficientes vértices libres

Demuestre simultáneamente por inducción que si el vértice está incrustado en el tiempo , entonces ${\displaystyle t}$ ${\displaystyle x}$ ${\displaystyle t}$

1. Sólo una pequeña fracción de las opciones son malas. ${\displaystyle F_{x}(t)}$
2. Todos los conjuntos libres son bastante grandes para vértices no incrustados. ${\displaystyle F_{z}(t+1)}$ ${\displaystyle z}$

Paso 2: el “lema principal”

Considere , y tal que no sea demasiado pequeño. Considere el evento donde ${\displaystyle 1\leq i\leq r,Y\subseteq X_{i}}$ ${\displaystyle A\subseteq V_{i}}$ ${\displaystyle |A|}$ ${\displaystyle E_{A,Y}}$

1. No se incrustan vértices durante la primera fase ${\displaystyle A}$
2. para cada hay un tiempo tal que la fracción de vértices libres de en ese momento era pequeña. ${\displaystyle y\in Y}$ ${\displaystyle t_{y}}$ ${\displaystyle y}$ ${\displaystyle A}$ ${\displaystyle t}$

Luego demostramos que la probabilidad de que esto ocurra es baja. ${\displaystyle E_{A,Y}}$

Paso 3: la fase 1 tiene éxito con alta probabilidad

La única forma en que la primera fase podría fallar es si se aborta, ya que por el primer paso sabemos que siempre hay una elección suficiente de buenos vértices. El programa se aborta solo cuando la cola es demasiado larga. El argumento luego procede mediante la unión de límites sobre todos los modos de falla, notando que para cualquier elección particular de , y con que representa un subconjunto de la cola que falló, el triple satisface las condiciones del "lema principal", y por lo tanto tiene una baja probabilidad de ocurrir. ${\displaystyle 1\leq i\leq r}$ ${\displaystyle Y\subseteq X_{i},|Y|\geq \delta _{Q}|X_{i}|}$ ${\displaystyle A=V_{i}}$ ${\displaystyle Y}$ ${\displaystyle (i,Y,A)}$

Paso 4: no hay cola en la fase inicial

Recuerde que la lista se configuró de modo que los vecinos de los vértices en el búfer se incrusten primero. El tiempo hasta que todos estos vértices se incrusten se denomina fase inicial . Pruebe por inducción en que no se agrega ningún vértice a la cola durante la fase inicial. De ello se deduce que todos los vecinos de los vértices del búfer se agregan antes que el resto de los vértices. ${\displaystyle t}$

Paso 5: los vértices del buffer tienen suficientes espacios libres

Para cualquier y , podemos encontrar un límite inferior suficientemente grande para la probabilidad de que , condicional al supuesto de que estaba libre antes de que cualquiera de los vértices en estuvieran incrustados. ${\displaystyle x\in B}$ ${\displaystyle v\in V_{x}}$ ${\displaystyle \phi (N_{H}(x))\subseteq N_{G}(v)}$ ${\displaystyle v}$ ${\displaystyle N_{H}(x)}$

Paso 6: la fase 2 tiene éxito con alta probabilidad

Por el teorema del matrimonio de Hall, la fase 2 falla si y solo si se viola la condición de Hall. Para que esto suceda, debe haber algunos y tales que . no puede ser demasiado pequeño por el tamaño de los conjuntos libres (paso 1). Si es demasiado grande, entonces con alta probabilidad , por lo que la probabilidad de falla en tal caso sería baja. Si no es ni demasiado pequeño ni demasiado grande, entonces notando que es un gran conjunto de vértices sin usar, podemos usar el lema principal y unir la probabilidad de falla. ^{[1] [2] [3]} ${\displaystyle 1\leq i\leq r}$ ${\displaystyle S\subseteq X_{i}}$ ${\displaystyle |\bigcup _{z\in S}F_{z}(T)|<|S|}$ ${\displaystyle |S|}$ ${\displaystyle |S|}$ ${\displaystyle \bigcup _{z\in S}F_{z}(T)=V_{i}(T)}$ ${\displaystyle |S|}$ ${\displaystyle A:=V_{i}(T)\setminus \bigcup _{z\in S}F_{z}(T)}$

Aplicaciones

El lema de explosión tiene varias aplicaciones en la incrustación de gráficos densos.

Conjetura de Pósa-Seymour

En 1962, Lajos Pósa conjeturó que todo grafo de vértice con grado mínimo contiene al menos el cuadrado de un ciclo hamiltoniano , ^[4] generalizando el teorema de Dirac . La conjetura fue ampliada por Paul Seymour en 1974 a lo siguiente: ${\displaystyle n}$ ${\displaystyle {\frac {2n}{3}}}$

Todo gráfico sobre vértices con grado mínimo contiene al menos la -ésima potencia de un ciclo hamiltoniano. ${\displaystyle n}$ ${\displaystyle {\frac {kn}{k+1}}}$ ${\displaystyle k}$

El lema de la explosión fue utilizado por Komlós, Sárközy y Szemerédi para demostrar la conjetura para todos los valores suficientemente grandes de (para un fijo ) en 1998. ^[5] ${\displaystyle n}$ ${\displaystyle k}$

Conjetura de Alon-Yuster

En 1995, Noga Alon y Raphael Yuster consideraron la generalización del conocido teorema de Hajnal-Szemerédi a factores arbitrarios (en lugar de solo gráficos completos) y demostraron la siguiente afirmación: ${\displaystyle H}$

Para cada grafo fijo con vértices, cualquier grafo G con n vértices y con grado mínimo contiene copias disjuntas de vértices de H. ${\displaystyle H}$ ${\displaystyle h}$ ${\displaystyle d\geq {\frac {\chi (H)-1}{\chi (H)}}n}$ ${\displaystyle (1-o(1))n/h}$

También conjeturaron que el resultado se mantiene sólo con un error constante (en lugar de lineal):

Para cada entero existe una constante tal que para cada grafo con vértices, cualquier grafo con vértices y con grado mínimo contiene al menos copias disjuntas de vértices de . ^[6] ${\displaystyle h}$ ${\displaystyle c(h)}$ ${\displaystyle H}$ ${\displaystyle h}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle d\geq {\frac {\chi (H)-1}{\chi (H)}}n}$ ${\displaystyle n/h-c(h)}$ ${\displaystyle H}$

Esta conjetura fue probada por Komlós, Sárközy y Szemerédi en 2001 utilizando el lema ampliado. ^[7]

Historia y variantes

El lema de la explosión, publicado por primera vez en 1997 por Komlós, Sárközy y Szemerédi, ^[1] surgió como un refinamiento de las técnicas de prueba existentes que usaban el método de regularidad para incrustar grafos generadores, como en la prueba de la conjetura de Bollobás sobre árboles generadores, ^[8] el trabajo sobre la conjetura de Pósa-Seymour sobre el grado mínimo necesario para contener la k-ésima potencia gráfica de un ciclo hamiltoniano , ^{[9] [4]} y la prueba de la conjetura de Alon-Yuster sobre el grado mínimo necesario para que un grafo tenga un factor H perfecto . ^[7] Las pruebas de todos estos teoremas se basaron en el uso de un algoritmo voraz aleatorio para incrustar la mayoría de los vértices y luego usar un argumento tipo Kőnig-Hall para encontrar una incrustación para los vértices restantes. ^[1] La primera prueba del lema de la explosión también usó un argumento similar. Sin embargo, más tarde en 1997, los mismos autores publicaron otro artículo que encontró una mejora en el algoritmo aleatorio para hacerlo determinista. ^[2]

Peter Keevash encontró una generalización del lema de explosión a los hipergrafos en 2010. ^[3]

Stefan Glock y Felix Joos descubrieron una variante del lema de explosión para gráficos de arco iris en 2018. ^[10]

En 2019, Peter Allen, Julia Böttcher , Hiep Hàn, Yoshiharu Kohayakawa y Yury Person encontraron análogos dispersos del lema de explosión para incrustar gráficos de grado acotado en gráficos aleatorios y pseudoaleatorios ^[11].

Referencias

1. Komlós, János ; Sárközy, Gábor N .; Szemerédi, Endre (1997), "Lema ampliado", Combinatorica , 17 (1): 109–123, doi : 10.1007/BF01196135 , MR  1466579, S2CID  6720143
2. 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, SEÑOR  1635264
3. Keevash, Peter (10 de mayo de 2011). "Un lema de explosión de hipergrafos". Random Structures & Algorithms . 39 (3): 275–367. arXiv : 1011.1355 . doi :10.1002/rsa.20362. S2CID  1395608.
4. Komlós, János; Sarközy, Gábor N.; Szemerédi, Endre (1996). "Sobre el cuadrado de un ciclo hamiltoniano en gráficos densos". Algoritmos y estructuras aleatorias . 9 (1–2): 193–211. doi :10.1002/(SICI)1098-2418(199608/09)9:1/2<193::AID-RSA12>3.0.CO;2-P. ISSN  1098-2418.
5. Komlós, János; Sarközy, Gábor N.; Szemerédi, Endre (1 de marzo de 1998). "Prueba de la conjetura de Seymour para gráficos grandes". Anales de combinatoria . 2 (1): 43–60. doi :10.1007/BF01626028. ISSN  0219-3094. S2CID  9802487.
6. Alon, Noga; Yuster, Raphael (1996-03-01). "Factores H en grafos densos". Journal of Combinatorial Theory, Serie B . 66 (2): 269–282. doi : 10.1006/jctb.1996.0020 . ISSN  0095-8956.
7. Komlós, János; Sarközy, Gábor; Szemerédi, Endre (28 de mayo de 2001). "Prueba de la conjetura de Alon-Yuster". Matemáticas Discretas . Checo y eslovaco 3. 235 (1): 255–269. doi : 10.1016/S0012-365X(00)00279-X . ISSN  0012-365X.
8. Komlós, János; Sarközy, Gábor N.; Szemerédi, Endre (1995). "Prueba de una conjetura del embalaje de Bollobás". Combinatoria, Probabilidad y Computación . 4 (3): 241–255. doi :10.1017/S0963548300001620. ISSN  1469-2163. S2CID  27736891.
9. Komlós, János; Sarközy, Gábor N.; Szemerédi, Endre (1998). "Sobre la conjetura de Pósa-Seymour". Revista de teoría de grafos . 29 (3): 167-176. doi :10.1002/(SICI)1097-0118(199811)29:3<167::AID-JGT4>3.0.CO;2-O. ISSN  1097-0118.
10. Glock, Stefan; Joos, Felix (20 de febrero de 2020). "Un lema de explosión de arcoíris". Estructuras y algoritmos aleatorios . 56 (4): 1031–1069. doi :10.1002/rsa.20907. S2CID  119737272.
11. Allen, Peter; Böttcher, Julia ; Hàn, Hiep; Kohayakawa, Yoshiharu; Person, Yury (19 de marzo de 2019). "Lemas de expansión para grafos dispersos". arXiv : 1612.00622 [math.CO].