lema de eliminación de grafos

Dejar${\displaystyle H}$ser un gráfico en${\displaystyle h}$vértices, cuyo conjunto de vértices es${\displaystyle V=\{1,2,\ldots ,h\}}$y el conjunto de bordes es${\displaystyle E}$. Dejar${\displaystyle X_{1},X_{2},\ldots ,X_{h}}$sean conjuntos de vértices de algún grafo${\displaystyle G}$de tal manera que, para todos${\displaystyle ij\in E}$, la pareja${\displaystyle (X_{i},X_{j})}$es${\displaystyle \epsilon }$- regular (en el sentido del lema de regularidad). Sea también${\displaystyle d_{ij}}$sea ​​la densidad entre los conjuntos${\displaystyle X_{i}}$y${\displaystyle X_{j}}$Intuitivamente, un par regular${\displaystyle (X,Y)}$con densidad${\displaystyle d}$debería comportarse como un grafo aleatorio tipo Erdős-Rényi , donde cada par de vértices${\displaystyle (x,y)\in (X\times Y)}$se selecciona para ser un borde independientemente con probabilidad${\displaystyle d}$Esto sugiere que el número de copias de${\displaystyle H}$en los vértices${\displaystyle x_{1},x_{2},\ldots ,x_{h}}$de tal manera que${\displaystyle x_{i}\in X_{i}}$debería estar cerca del número esperado según el modelo de Erdős-Rényi,$${\displaystyle \prod _{ij\in E(H)}d_{ij}\prod _{i\in V(H)}|X_{i}|,}$$dónde${\displaystyle E(H)}$y${\displaystyle V(H)}$son el conjunto de aristas y el conjunto de vértices de${\displaystyle H}$.

La formalización directa de la afirmación heurística anterior es la siguiente. Sea${\displaystyle H}$ser un gráfico en${\displaystyle h}$vértices, cuyo conjunto de vértices es${\displaystyle V=\{1,2,\ldots ,h\}}$y cuyo conjunto de aristas es${\displaystyle E}$. Dejar${\displaystyle \delta >0}$ser arbitrario. Entonces existe${\displaystyle \epsilon >0}$de tal manera que para cualquier${\displaystyle X_{1},X_{2},\ldots ,X_{h}}$como se indicó anteriormente, satisfaciendo${\displaystyle d_{ij}>\delta}$a pesar de${\displaystyle ij\in E}$, el número de homomorfismos de grafos de${\displaystyle H}$a${\displaystyle G}$de tal manera que el vértice${\displaystyle i\in V(H)}$está asignado a${\displaystyle X_{i}}$no es más pequeño que$${\displaystyle (1-\delta )\prod _{ij\in E}(d_{ij}-\delta )\prod _{i\in V}|X_{i}|.}$$

Incluso se pueden encontrar subgrafos de grado limitado de explosiones de${\displaystyle H}$En un contexto similar, la siguiente afirmación aparece en la literatura con el nombre de lema de explosión y fue demostrada por primera vez por Komlós , Sárközy y Szemerédi. ^{[ 9 ]} La formulación precisa aquí es una versión ligeramente simplificada debida a Komlós, quien también se refirió a ella como el lema clave, ya que se utiliza en numerosas demostraciones basadas en regularidades. ^{[ 10 ]}

Dejar${\displaystyle H_{1}}$Sea un grafo arbitrario y sea${\displaystyle t\in \mathbb {Z} _{+}}$Construir${\displaystyle H(t)}$reemplazando cada vértice${\displaystyle i}$de${\displaystyle H}$por un conjunto independiente${\displaystyle V_{i}}$de tamaño${\displaystyle t}$y reemplazando cada borde${\displaystyle ij}$de${\displaystyle H}$por el grafo bipartito completo en${\displaystyle (V_{i},V_{j})}$. Dejar${\displaystyle \epsilon ,\delta >0}$sean reales arbitrarios, sea${\displaystyle N}$Sea un número entero positivo, y sea${\displaystyle H_{2}}$ser un subgrafo de${\displaystyle H(t)}$con${\displaystyle h}$vértices y grado máximo${\displaystyle \Delta }$. Definir${\displaystyle \epsilon _{0}=\delta ^{\Delta }/(2+\Delta )}$. Finalmente, dejemos${\displaystyle G}$ser un gráfico y${\displaystyle X_{1},X_{2},\ldots ,X_{h}}$sean conjuntos disjuntos de vértices de${\displaystyle G}$de tal manera que, siempre que${\ Displaystyle ij \ en E (H_ {2})}$, entonces${\displaystyle (X_{i},X_{j})}$es un${\displaystyle \epsilon }$-par regular con densidad al menos${\displaystyle \épsilon +\delta}$. Entonces si${\displaystyle \epsilon \leq \epsilon _ {0}}$y${\displaystyle 1-t\leq N\epsilon _{0}}$, entonces el número de homomorfismos de grafos inyectivos de${\displaystyle H_{2}}$a${\displaystyle G}$es al menos${\displaystyle (\epsilon _ {0}N)^{h}}$.

De hecho, uno puede restringirse a contar solo aquellos homomorfismos tales que cualquier vértice${\displaystyle k\in [h]}$de${\displaystyle H_{2}}$con${\displaystyle k\in V_{i}}$se asigna a un vértice en${\displaystyle X_{i}}$.

Proporcionaremos una demostración del lema de conteo en el caso en que${\displaystyle H}$es un triángulo ( lema de conteo de triángulos ). La demostración del caso general, así como la demostración del lema de explosión , son muy similares y no requieren técnicas diferentes.

Llevar${\displaystyle \epsilon =\delta /2}$. Dejar${\displaystyle X_{1}'\subset X_{1}}$sea ​​el conjunto de esos vértices en${\displaystyle X_{1}}$que tienen al menos${\displaystyle (d_{12}-\epsilon )|X_{2}|}$vecinos en${\displaystyle X_{2}}$y al menos${\displaystyle (d_{13}-\epsilon )|X_{3}|}$vecinos en${\displaystyle X_{3}}$. Tenga en cuenta que si hubiera más de${\displaystyle \epsilon |X_ {1}|}$vértices en${\displaystyle X_{1}}$con menos de${\displaystyle (d_{12}-\epsilon )|X_{2}|}$vecinos en${\displaystyle X_{2}}$, entonces estos vértices junto con el todo${\displaystyle X_{2}}$sería testigo${\displaystyle \epsilon }$-irregularidad del par${\displaystyle (X_{1},X_{2})}$. Repitiendo este argumento para${\displaystyle X_{3}}$muestra que debemos tener${\displaystyle |X_{1}'|>(1-2\epsilon )|X_{1}|}$. Ahora tomemos un arbitrario${\displaystyle x\in X_{1}'}$y definir${\displaystyle X_{2}'}$y${\displaystyle X_{3}'}$como vecinos de${\displaystyle x}$en${\displaystyle X_{2}}$y${\displaystyle X_{3}}$, respectivamente. Por definición,${\displaystyle |X_{2}'|\geq (d_{12}-\epsilon )|X_{2}|\geq \epsilon |X_{2}|}$y${\displaystyle |X_{3}'|\geq \epsilon |X_{3}|}$, así que por la regularidad de${\displaystyle (X_{2},X_{3})}$obtenemos la existencia de al menos$${\displaystyle (d_{23}-\epsilon )|X_{2}'||X_{3}'|\geq (d_{12}-\epsilon )(d_{23}-\epsilon )(d_{13}-\epsilon )|X_{2}||X_{3}|}$$triángulos que contienen${\displaystyle x}$. Desde${\displaystyle x}$fue elegido arbitrariamente del conjunto${\displaystyle X_{1}'}$de tamaño al menos${\displaystyle (1-2\epsilon )|X_ {1}|}$, obtenemos un total de al menos$${\displaystyle (1-2\epsilon )|X_{1}|(d_{23}-\epsilon )|X_{2}'||X_{3}'|\geq (1-2\epsilon )(d_{12}-\epsilon )(d_{23}-\epsilon )(d_{13}-\epsilon )|X_{1}||X_{2}||X_{3}|,}$$lo cual finaliza la prueba como${\displaystyle \epsilon =\delta /2}$.

Para demostrar el lema de eliminación de triángulos, considere un${\displaystyle \epsilon /4}$-partición regular${\displaystyle V_{1}\cup \cdots \cup V_{M}}$del conjunto de vértices de${\displaystyle G}$Esto existe por el lema de regularidad de Szemerédi. La idea es eliminar todas las aristas entre pares irregulares, pares de baja densidad y partes pequeñas, y demostrar que si al menos un triángulo aún permanece, entonces quedan muchos triángulos. Específicamente, eliminar todas las aristas entre partes${\displaystyle V_{i}}$y${\displaystyle V_{j}}$si

Este procedimiento elimina como máximo${\displaystyle \épsilon n^{2}}$bordes. Si existe un triángulo con vértices en${\ Displaystyle V_ {i}, V_ {j}, V_ {k}}$Después de eliminar estos bordes, el lema de conteo de triángulos nos dice que hay al menos$${\displaystyle \left(1-{\frac {\epsilon }{2}}\right)\left({\frac {\epsilon }{4}}\right)^{3}\left({\frac {\epsilon }{4M}}\right)^{3}\cdot n^{3}}$$triples en${\displaystyle V_{i}\times V_{j}\times V_{k}}$que forman un triángulo. Por lo tanto, podemos tomar$${\displaystyle \delta <{\frac {1}{6}}\left(1-{\frac {\epsilon }{2}}\right)\left({\frac {\epsilon }{4}}\right)^{3}\left({\frac {\epsilon }{4M}}\right)^{3}.}$$

La prueba del caso general${\displaystyle H}$es análogo al caso del triángulo, y utiliza el lema de conteo de grafos en lugar del lema de conteo de triángulos.

Una versión del lema de eliminación de grafos para subgrafos inducidos fue demostrada por Alon , Fischer, Krivelevich y Szegedy en 2000. ^{[ 12 ]} Establece que para cualquier grafo${\displaystyle H}$con${\displaystyle h}$vértices y${\displaystyle \epsilon >0}$, existe una constante${\displaystyle \delta >0}$de tal manera que, si un${\displaystyle n}$-grafo de vértices${\displaystyle G}$tiene menos que${\displaystyle \delta n^{h}}$subgrafos inducidos isomorfos a${\displaystyle H}$, entonces es posible eliminar todas las copias inducidas de${\displaystyle H}$agregando o quitando menos de${\displaystyle \epsilon n^{2}}$bordes.

El problema se puede reformular de la siguiente manera: Dada una coloración rojo-azul${\displaystyle H'}$del gráfico completo${\displaystyle K_{h}}$(análogo al gráfico)${\displaystyle H}$en el mismo${\displaystyle h}$vértices donde los no bordes son azules y los bordes son rojos), y una constante${\displaystyle \epsilon >0}$, entonces existe una constante${\displaystyle \delta >0}$de tal manera que para cualquier coloración rojo-azul de${\displaystyle K_{n}}$tiene menos que${\displaystyle \delta n^{h}}$subgrafos isomorfos a${\displaystyle H'}$, entonces es posible eliminar todas las copias de${\displaystyle H}$cambiando los colores de menos de${\displaystyle \epsilon n^{2}}$bordes. Nótese que nuestro proceso de "limpieza" anterior, en el que eliminamos todos los bordes entre pares irregulares, pares de baja densidad y partes pequeñas, solo implica la eliminación de bordes. Eliminar bordes solo corresponde a cambiar los colores de los bordes de rojo a azul. Sin embargo, en el caso inducido, existen situaciones en las que la distancia de edición óptima también implica cambiar los colores de los bordes de azul a rojo. Por lo tanto, el lema de regularidad es insuficiente para demostrar el lema de eliminación de grafos inducido. La demostración del lema de eliminación de grafos inducido debe aprovechar el lema de regularidad fuerte . ^{[ 12 ]}