Lema de eliminación de grafos

En teoría de grafos , el lema de eliminación de grafos establece que cuando un grafo contiene pocas copias de un subgrafo dado , entonces todas las copias pueden eliminarse eliminando una pequeña cantidad de aristas. ^[1] El caso especial en el que el subgrafo es un triángulo se conoce como el lema de eliminación de triángulos . ^[2]

El lema de eliminación de grafos se puede utilizar para demostrar el teorema de Roth en progresiones aritméticas de 3 términos, ^[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] También tiene aplicaciones para pruebas de propiedades . ^[5]

Formulación

Sea un grafo con vértices. El lema de eliminación de grafos establece que para cualquier , existe una constante tal que para cualquier grafo de -vértices con menos de subgrafos isomorfos a , es posible eliminar todas las copias de eliminando como máximo las aristas de . ^[1] ${\displaystyle H}$ ${\displaystyle h}$ ${\displaystyle \epsilon >0}$ ${\displaystyle \delta =\delta (\epsilon ,H)>0}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle \delta n^{h}}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle \epsilon n^{2}}$ ${\displaystyle G}$

Una forma alternativa de expresar esto es decir que para cualquier gráfico de vértice con subgrafos isomorfos a , es posible eliminar todas las copias de quitando las aristas de . Aquí, el indica el uso de la notación o minúscula . ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle o(n^{h})}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle o(n^{2})}$ ${\displaystyle G}$ ${\displaystyle o}$

En el caso cuando es un triángulo, el lema resultante se llama lema de eliminación de triángulos . ${\displaystyle H}$

Historia

La motivación original para el estudio del lema de eliminación de triángulos fue el problema de Ruzsa-Szemerédi . La formulación inicial debida a Imre Z. Ruzsa y Szemerédi de 1978 era ligeramente más débil que el lema de eliminación de triángulos utilizado actualmente y se puede expresar de forma aproximada de la siguiente manera: todo grafo localmente lineal en vértices contiene aristas. ^[6] Esta afirmación se puede deducir rápidamente de un lema de eliminación de triángulos moderno. Ruzsa y Szemerédi proporcionaron también una prueba alternativa del teorema de Roth sobre progresiones aritméticas como un corolario simple. ^[6] ${\displaystyle n}$ ${\displaystyle o(n^{2})}$

En 1986, durante su trabajo sobre generalizaciones del problema de Ruzsa–Szemerédi a grafos arbitrarios -uniformes, Erdős , Frankl y Rödl proporcionaron una formulación para grafos generales muy cercana al lema moderno de eliminación de grafos: si el grafo es una imagen homomórfica de , entonces cualquier grafo - libre en vértices puede hacerse -libre eliminando aristas. ^[7] ${\displaystyle r}$ ${\displaystyle H_{2}}$ ${\displaystyle H_{2}}$ ${\displaystyle H_{1}}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle H_{2}}$ ${\displaystyle o(n^{2})}$

La formulación moderna del lema de eliminación de grafos fue establecida por primera vez por Füredi en 1994. ^[8] La prueba generalizó enfoques anteriores de Ruzsa y Szemerédi y Erdős, Frankl y Rödl, utilizando también el lema de regularidad de Szemerédi .

Lema de conteo de gráficos

Un componente clave del lema de demostración de la eliminación de grafos es el lema de conteo de grafos, que trata sobre el conteo de subgrafos en sistemas de pares regulares . El lema de conteo de grafos también es muy útil por sí solo. Según Füredi, se utiliza "en la mayoría de las aplicaciones del lema de regularidad". ^[8]

Argumento heurístico

Sea un grafo sobre vértices, cuyo conjunto de vértices es y conjunto de aristas es . Sean conjuntos de vértices de algún grafo tal que para todo par es - regular (en el sentido del lema de regularidad). Sea también la densidad entre conjuntos y . Intuitivamente, un par regular con densidad debería comportarse como un grafo aleatorio tipo Erdős–Rényi , donde cada par de vértices se selecciona para ser una arista de forma independiente con probabilidad . Esto sugiere que el número de copias de sobre vértices tal que debería ser cercano al número esperado del modelo de Erdős–Rényi: donde y son el conjunto de aristas y el conjunto de vértices de . ${\displaystyle H}$ ${\displaystyle h}$ ${\displaystyle V=\{1,2,\ldots ,h\}}$ ${\displaystyle E}$ ${\displaystyle X_{1},X_{2},\ldots ,X_{h}}$ ${\displaystyle G}$ ${\displaystyle ij\in E}$ ${\displaystyle (X_{i},X_{j})}$ ${\displaystyle \epsilon }$ ${\displaystyle d_{ij}}$ ${\displaystyle X_{i}}$ ${\displaystyle X_{j}}$ ${\displaystyle (X,Y)}$ ${\displaystyle d}$ ${\displaystyle (x,y)\in (X\times Y)}$ ${\displaystyle d}$ ${\displaystyle H}$ ${\displaystyle x_{1},x_{2},\ldots ,x_{h}}$ ${\displaystyle x_{i}\in X_{i}}$ $${\displaystyle \prod _{ij\in E(H)}d_{ij}\prod _{i\in V(H)}|X_{i}|}$$ ${\displaystyle E(H)}$ ${\displaystyle V(H)}$ ${\displaystyle H}$

Declaración precisa

La formalización directa de la afirmación heurística anterior es la siguiente. Sea un grafo sobre vértices, cuyo conjunto de vértices es y conjunto de aristas es . Sea arbitrario. Entonces existe tal que para cualquier como el anterior, que satisface para todos , el número de homomorfismos de grafos de a tales que ese vértice se mapea a no es menor que ${\displaystyle H}$ ${\displaystyle h}$ ${\displaystyle V=\{1,2,\ldots ,h\}}$ ${\displaystyle E}$ ${\displaystyle \delta >0}$ ${\displaystyle \epsilon >0}$ ${\displaystyle X_{1},X_{2},\ldots ,X_{h}}$ ${\displaystyle d_{ij}>\delta }$ ${\displaystyle ij\in E}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle i\in V(H)}$ ${\displaystyle X_{i}}$ $${\displaystyle (1-\delta )\prod _{ij\in E}(d_{ij}-\delta )\prod _{i\in V}|X_{i}|}$$

Lema de la explosión

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

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

De hecho, uno sólo puede restringirse a contar homomorfismos tales que cualquier vértice de tal que se mapee a un vértice en . ${\displaystyle k\in [h]}$ ${\displaystyle H_{2}}$ ${\displaystyle k\in V_{i}}$ ${\displaystyle X_{i}}$

Prueba

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

Tome . Sea el conjunto de aquellos vértices en los que tienen al menos vecinos en y al menos vecinos en . Nótese que si hubiera más de vértices en con menos de vecinos en , entonces estos vértices junto con todo serían testigos de la -irregularidad del par . Repetir este argumento para muestra que debemos tener . Ahora tome arbitrario y defina y como vecinos de en y respectivamente. Por definición y por lo tanto por regularidad de obtenemos la existencia de al menos triángulos que contienen . Como fue elegido arbitrariamente del conjunto de tamaño al menos , obtenemos un total de al menos que termina la prueba como . ${\displaystyle \epsilon =\delta /2}$ ${\displaystyle X_{1}'\subset X_{1}}$ ${\displaystyle X_{1}}$ ${\displaystyle (d_{12}-\epsilon )|X_{2}|}$ ${\displaystyle X_{2}}$ ${\displaystyle (d_{13}-\epsilon )|X_{3}|}$ ${\displaystyle X_{3}}$ ${\displaystyle \epsilon |X_{1}|}$ ${\displaystyle X_{1}}$ ${\displaystyle (d_{12}-\epsilon )|X_{2}|}$ ${\displaystyle X_{2}}$ ${\displaystyle X_{2}}$ ${\displaystyle \epsilon }$ ${\displaystyle (X_{1},X_{2})}$ ${\displaystyle X_{3}}$ ${\displaystyle |X_{1}'|>(1-2\epsilon )|X_{1}|}$ ${\displaystyle x\in X_{1}'}$ ${\displaystyle X_{2}'}$ ${\displaystyle X_{3}'}$ ${\displaystyle x}$ ${\displaystyle X_{2}}$ ${\displaystyle X_{3}}$ ${\displaystyle |X_{2}'|\geq (d_{12}-\epsilon )|X_{2}|\geq \epsilon |X_{2}|}$ ${\displaystyle |X_{3}'|\geq \epsilon |X_{3}|}$ ${\displaystyle (X_{2},X_{3})}$ $${\displaystyle (d_{23}-\epsilon )|X_{2}'||X_{3}'|\geq (d_{12}-\epsilon )(d_{23}-\epsilon )(d_{13}-\epsilon )|X_{2}||X_{3}|}$$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle X_{1}'}$ ${\displaystyle (1-2\epsilon )|X_{1}|}$ $${\displaystyle (1-2\epsilon )(d_{23}-\epsilon )|X_{2}'||X_{3}'|\geq (d_{12}-\epsilon )(d_{23}-\epsilon )(d_{13}-\epsilon )|X_{1}||X_{2}||X_{3}|}$$ ${\displaystyle \epsilon =\delta /2}$

Prueba

Prueba del lema de eliminación de triángulos

Para demostrar el lema de eliminación de triángulos, considere una partición -regular del conjunto de vértices de . 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 todavía queda al menos un triángulo, entonces quedan muchos triángulos. Específicamente, elimine todas las aristas entre las partes y si ${\displaystyle \epsilon /4}$ ${\displaystyle V_{1}\cup \cdots \cup V_{M}}$ ${\displaystyle G}$ ${\displaystyle V_{i}}$ ${\displaystyle V_{j}}$

• ${\displaystyle (V_{i},V_{j})}$no es -regular ${\displaystyle \epsilon /4}$
• la densidad es menor que , o ${\displaystyle d(V_{i},V_{j})}$ ${\displaystyle \epsilon /2}$
• o bien tiene como máximo vértices. ${\displaystyle V_{i}}$ ${\displaystyle V_{j}}$ ${\displaystyle (\epsilon /4M)n}$

Este procedimiento elimina la mayoría de las aristas. Si existe un triángulo con vértices en después de eliminar estas aristas, entonces el lema de conteo de triángulos nos dice que hay al menos ternas en las que se forma un triángulo. Por lo tanto, podemos tomar ${\displaystyle \epsilon n^{2}}$ ${\displaystyle V_{i},V_{j},V_{k}}$ $${\displaystyle \left(1-{\frac {\epsilon }{2}}\right)\left({\frac {\epsilon }{4}}\right)^{3}\left({\frac {\epsilon }{4M}}\right)^{3}\cdot n^{3}}$$ ${\displaystyle V_{i}\times V_{j}\times V_{k}}$ $${\displaystyle \delta <{\frac {1}{6}}\left(1-{\frac {\epsilon }{2}}\right)\left({\frac {\epsilon }{4}}\right)^{3}\left({\frac {\epsilon }{4M}}\right)^{3}.}$$

Prueba del lema de eliminación de grafos

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

Lema de eliminación de grafos inducidos

Una generalización natural del Lema de Eliminación de Grafos es considerar subgrafos inducidos . En las pruebas de propiedades, a menudo es útil considerar qué tan lejos está un grafo de ser inducido libre de H. ^[11] Se considera que un grafo contiene un subgrafo inducido si hay una función inyectiva tal que es una arista de si y solo si es una arista de . Nótese que también se consideran los no-aristas. es inducido -libre si no hay ningún subgrafo inducido . Definimos como -lejos de ser inducido -libre si no podemos agregar o eliminar aristas para hacer inducido -libre. ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle f:V(H)\rightarrow V(G)}$ ${\displaystyle (f(u),f(v))}$ ${\displaystyle G}$ ${\displaystyle (u,v)}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \epsilon }$ ${\displaystyle H}$ ${\displaystyle \epsilon n^{2}}$ ${\displaystyle G}$ ${\displaystyle H}$

Formulación

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

El problema puede reformularse de la siguiente manera: dada una coloración rojo-azul del grafo completo (análoga al grafo en los mismos vértices donde los no bordes son azules, los bordes son rojos), y una constante , entonces existe una constante tal que para cualquier coloración rojo-azul de tiene menos de subgrafos isomorfos a , entonces es posible eliminar todas las copias de cambiando los colores de menos de bordes. Observe que nuestro proceso de "limpieza" anterior, donde eliminamos todos los bordes entre pares irregulares, pares de baja densidad y partes pequeñas, solo implica eliminar bordes. Eliminar bordes solo corresponde a cambiar los colores de los bordes de rojo a azul. Sin embargo, hay situaciones en el caso inducido donde 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 la regularidad es insuficiente para probar el Lema de eliminación de grafos inducidos. La prueba del Lema de eliminación de grafos inducidos debe aprovechar el lema de regularidad fuerte . ^[12] ${\displaystyle H'}$ ${\displaystyle K_{h}}$ ${\displaystyle H}$ ${\displaystyle h}$ ${\displaystyle \epsilon >0}$ ${\displaystyle \delta >0}$ ${\displaystyle K_{n}}$ ${\displaystyle \delta n^{h}}$ ${\displaystyle H'}$ ${\displaystyle H}$ ${\displaystyle \epsilon n^{2}}$

Prueba

Lema de regularidad fuerte

El lema de regularidad fuerte ^[12] es una versión reforzada del lema de regularidad de Szemerédi. 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}$

La función se define como la función de energía definida en el lema de regularidad de Szemerédi . Básicamente, podemos encontrar un par de particiones donde es extremadamente regular en comparación con , y al mismo tiempo están cerca una de la otra. (Esta propiedad se captura en la tercera condición) ${\displaystyle q}$ ${\displaystyle {\mathcal {P}},{\mathcal {Q}}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {P}},{\mathcal {Q}}}$

Corolario del lema de la regularidad fuerte

El siguiente corolario del lema de regularidad fuerte se utiliza en la prueba del lema de eliminación de grafos inducidos. ^[12] 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 i,j}$
• ${\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 i,j}$

La idea principal de la prueba de este corolario es comenzar con dos particiones y que satisfacen el Lema de Regularidad Fuerte donde . Luego, para cada parte , elegimos de manera aleatoria y uniforme alguna parte que sea una parte en . El número esperado de pares irregulares es menor que 1. Por lo tanto, existe una colección de tal que cada par es -regular! ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle q({\mathcal {Q}})<q({\mathcal {P}})+\epsilon _{0}^{3}/8}$ ${\displaystyle V_{i}\in {\mathcal {P}}}$ ${\displaystyle W_{i}\subset V_{i}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle (W_{i},W_{j})}$ ${\displaystyle W_{i}}$ ${\displaystyle \epsilon _{|{\mathcal {P}}|}}$

El aspecto importante de este corolario es que cada par de son -regulares. Esto nos permite considerar aristas y no aristas cuando realizamos nuestro argumento de limpieza. ${\displaystyle W_{i},W_{j}}$ ${\displaystyle \epsilon _{|{\mathcal {P}}|}}$

Demostración del esquema del lema de eliminación de grafos inducidos

Con estos resultados, podemos demostrar el Lema de Eliminación de Grafos Inducidos. Tomemos cualquier grafo con vértices que tenga menos de copias de . La idea es comenzar con una colección de conjuntos de vértices que satisfagan las condiciones del Corolario del Lema de Regularidad Fuerte . ^[12] Luego podemos realizar un proceso de "limpieza" donde eliminamos todos los bordes entre pares de partes con baja densidad, y podemos agregar todos los bordes entre pares de partes con alta densidad. Elegimos los requisitos de densidad de modo que agreguemos/eliminemos como máximo los bordes. ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \delta n^{v(H)}}$ ${\displaystyle H}$ ${\displaystyle W_{i}}$ ${\displaystyle (W_{i},W_{j})}$ ${\displaystyle (W_{i},W_{j})}$ ${\displaystyle \epsilon n^{2}}$

Si el nuevo gráfico no tiene copias de , entonces hemos terminado. Supongamos que el nuevo gráfico tiene una copia de . Supongamos que el vértice está incrustado en . Entonces, si hay una arista que conecta en , entonces no tiene baja densidad. (Las aristas entre no se eliminaron en el proceso de limpieza). De manera similar, si no hay una arista que conecta en , entonces no tiene alta densidad. (Las aristas entre no se agregaron en el proceso de limpieza) ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle v_{i}\in v(H)}$ ${\displaystyle W_{f(i)}}$ ${\displaystyle v_{i},v_{j}}$ ${\displaystyle H}$ ${\displaystyle W_{i},W_{j}}$ ${\displaystyle W_{i},W_{j}}$ ${\displaystyle v_{i},v_{j}}$ ${\displaystyle H}$ ${\displaystyle W_{i},W_{j}}$ ${\displaystyle W_{i},W_{j}}$

Así, mediante un argumento de conteo similar a la prueba del lema de conteo de triángulos, es decir, el lema de conteo de grafos , podemos demostrar que tiene más de copias de . ${\displaystyle G}$ ${\displaystyle \delta n^{v(H)}}$ ${\displaystyle H}$

Generalizaciones

El lema de eliminación de grafos se extendió posteriormente a los grafos dirigidos ^[5] y a los hipergrafos . ^[4]

Límites cuantitativos

Uso del lema de regularidad en la prueba del lema de eliminación de grafos Las fuerzas del lema de regularidad deben ser extremadamente pequeñas, limitadas por la función de torre del polinomio de altura en que es (aquí está la torre de dos en dos de altura ). La función de torre de altura es necesaria en todas las pruebas de regularidad como lo implican los resultados de Gowers sobre los límites inferiores en el lema de regularidad. ^[13] Sin embargo, en 2011 Fox proporcionó una nueva prueba del lema de eliminación de grafos que no usa el lema de regularidad, mejorando el límite a (aquí está el número de vértices del grafo eliminado ). ^[1] Su prueba, sin embargo, usa ideas relacionadas con la regularidad como el incremento de energía , pero con una noción diferente de energía, relacionada con la entropía . Esta prueba también se puede reformular usando el lema de regularidad débil de Frieze-Kannan como lo notaron Conlon y Fox. ^[11] En el caso especial de bipartito se demostró que es suficiente. ${\displaystyle \delta }$ ${\displaystyle \epsilon ^{-1}}$ ${\displaystyle \delta =1/{\text{tower}}(\epsilon ^{-O(1)})}$ ${\displaystyle {\text{tower}}(k)}$ ${\displaystyle k}$ ${\displaystyle \epsilon ^{-O(1)}}$ ${\displaystyle \delta =1/{\text{tower}}(5h^{2}\log \epsilon ^{-1})}$ ${\displaystyle h}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle \delta =\epsilon ^{O(1)}}$

Existe una gran brecha entre los límites superior e inferior para en el caso general. El mejor resultado actual verdadero para todos los grafos se debe a Alon y establece que para cada no bipartito existe una constante tal que es necesaria para que se cumpla el lema de eliminación de grafos, mientras que para el bipartito el óptimo tiene dependencia polinómica de , que coincide con el límite inferior. La construcción para el caso no bipartito es una consecuencia de la construcción de Behrend de un gran conjunto de Salem-Spencer. De hecho, como el lema de eliminación de triángulos implica el teorema de Roth, la existencia de un gran conjunto de Salem-Spencer puede traducirse en un límite superior para en el lema de eliminación de triángulos. Este método se puede aprovechar para cualquier no bipartito arbitrario para dar el límite mencionado anteriormente. ${\displaystyle \delta }$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle c>0}$ ${\displaystyle \delta <(\epsilon /c)^{c\log(c/\epsilon )}}$ ${\displaystyle H}$ ${\displaystyle \delta }$ ${\displaystyle \epsilon }$ ${\displaystyle \delta }$ ${\displaystyle H}$

Aplicaciones

Combinatoria aditiva

• Ruzsa y Szemerédi formularon el lema de eliminación de triángulos para proporcionar límites superiores subcuadráticos al problema de Ruzsa-Szemerédi sobre el tamaño de los grafos en los que cada arista pertenece a un único triángulo . Esto conduce a una prueba del teorema de Roth. ^[3]
• El lema de eliminación de triángulos también se puede utilizar para demostrar el teorema de los vértices , que establece que cualquier subconjunto de que no contenga ningún triángulo rectángulo isósceles alineado al eje tiene tamaño . ^[14] ${\displaystyle [n]^{2}}$ ${\displaystyle o(n^{2})}$
• El lema de eliminación de hipergrafos se puede utilizar para demostrar el teorema de Szemerédi sobre la existencia de progresiones aritméticas largas en subconjuntos densos de números enteros. ^[4]

Teoría de grafos

• El lema de conteo/eliminación de grafos se puede utilizar para proporcionar una prueba rápida y transparente del teorema de Erdős-Stone a partir del teorema de Turán y extender el resultado a la estabilidad de Simonovit : para cualquier grafo y cualquier existe tal que cualquier grafo -libre en vértices con al menos aristas se puede transformar en un grafo de Turán -partito completo añadiendo y/o eliminando como máximo aristas (aquí está el número cromático de ). ^[15] Aunque ambos resultados se habían demostrado antes utilizando técnicas más elementales (el teorema de Erdős-Stone fue demostrado en 1966 ^[16] por Erdős y Stone mientras que la estabilidad de Simonovit fue demostrada en el mismo año por varios autores ^{[16] [17] [18] [19]} ), la prueba de regularidad proporciona un punto de vista diferente y aclara la conexión con otras pruebas modernas. ${\displaystyle H}$ ${\displaystyle \epsilon >0}$ ${\displaystyle \delta }$ ${\displaystyle H}$ ${\displaystyle n}$ ${\displaystyle \left(1-{\frac {1}{\chi (H)-1}}\right){\binom {n}{2}}-\delta n^{2}}$ ${\displaystyle (\chi (H)-1)}$ ${\displaystyle T_{n,\chi (H)-1}}$ ${\displaystyle \epsilon n^{2}}$ ${\displaystyle \chi (H)}$ ${\displaystyle H}$
• El lema de eliminación de grafos junto con el teorema de Erdős-Stone se puede utilizar para demostrar que el número de grafos libres no isomorfos en los vértices es igual a ${\displaystyle H}$ ${\displaystyle n}$

  $${\displaystyle 2^{(\pi (H)+o(1)){\binom {n}{2}}}}$$

  donde es la densidad de Turán de . ^[7] ${\displaystyle \pi (H)=1-{\frac {1}{\chi (H)-1}}}$ ${\displaystyle H}$

Prueba de propiedad

• El lema de eliminación de grafos tiene aplicaciones para la prueba de propiedades , porque implica que para cada grafo, o bien el grafo está cerca de un grafo -libre, o bien un muestreo aleatorio encontrará fácilmente una copia de en el grafo. ^[5] Un resultado es que para cualquier , hay un algoritmo de tiempo constante que retorna con alta probabilidad si un grafo -vértice dado está -lejos de ser -libre o no. ^[20] Aquí, -lejos de ser -libre significa que al menos se deben eliminar los bordes para eliminar todas las copias de en . ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle \epsilon >0}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle \epsilon }$ ${\displaystyle H}$ ${\displaystyle \epsilon }$ ${\displaystyle H}$ ${\displaystyle \epsilon n^{2}}$ ${\displaystyle H}$ ${\displaystyle G}$
• El lema de eliminación de gráficos inducidos fue formulado por Alon, Fischer, Krivelevich y Szegedy para caracterizar las propiedades de gráficos comprobables. ^[12]

Véase también

• Lema de conteo
• La conjetura de Tuza

Referencias

1. Fox, Jacob (2011), "Una nueva prueba del lema de eliminación de grafos", Anales de Matemáticas , Segunda serie, 174 (1): 561–579, arXiv : 1006.1300 , doi :10.4007/annals.2011.174.1.17, MR  2811609, S2CID  8250133
2. Trevisan, Luca (13 de mayo de 2009), "El lema de la eliminación del triángulo", en teoría
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 ; Shapira, Asaf (2004), "Prueba de subgrafos en grafos dirigidos", Journal of Computer and System Sciences , 69 (3): 353–382, doi : 10.1016/j.jcss.2004.04.008 , MR  2087940
6. Ruzsa, IZ ; Szemerédi, E. (1978), "Sistemas triples sin seis puntos que lleven tres triángulos", Combinatoria (Proc. Quinto coloquio húngaro, Keszthely, 1976), vol. II , coloq. Matemáticas. Soc. János Bolyai, vol. 18, Amsterdam y Nueva York: Holanda Septentrional, págs. 939–945, MR  0519318
7. Erdős, P. ; Frankl, P. ; Rödl, V. (1986), "El número asintótico de grafos que no contienen un subgrafo fijo y un problema para hipergrafos que no tienen exponente", Graphs and Combinatorics , 2 (2): 113–121, doi :10.1007/BF01788085, MR  0932119, S2CID  16839886
8. Füredi, Zoltán (1995). "Hipergrafos extremos y geometría combinatoria". En Chatterji, SD (ed.). Actas del Congreso Internacional de Matemáticos . Basilea: Birkhäuser. págs. 1343–1352. doi :10.1007/978-3-0348-9078-6_129. ISBN 978-3-0348-9078-6.
9. Komlós, János; Sarközy, Gábor N.; Szemerédi, Endre (1 de marzo de 1997). "Lema ampliado". Combinatoria . 17 (1): 109–123. doi :10.1007/BF01196135. ISSN  1439-6912. S2CID  6720143.
10. Komlós, János (1999). "El lema de la explosión". Combinatoria, Probabilidad y Computación . 8 (1–2): 161–176. doi :10.1017/S0963548398003502. ISSN  1469-2163. S2CID  6720143.
11. Conlon, David ; Fox, Jacob (2013), "Graph removal lemmas", en Blackburn, Simon R.; Gerke, Stefanie; Wildon, Mark (eds.), Surveys in Combinatorics 2013 , London Mathematical Society Lecture Note Series, vol. 409, Cambridge, Reino Unido: Cambridge University Press, págs. 1–49, arXiv : 1211.3487 , doi :10.1017/CBO9781139506748.002, MR  3156927, S2CID  2658118
12. 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
13. 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. S2CID  115242956.
14. Solymosi, J. (2003), "Nota sobre una generalización del teorema de Roth", Geometría discreta y computacional , Algoritmos y combinatoria, 25 : 825–827, doi : 10.1007/978-3-642-55566-4_39, ISBN 978-3-642-62442-1, MR  2038505, S2CID  53973423
15. Alon, N. (14 de octubre de 2001). "Prueba de subgrafos en grafos grandes". Actas del 42.º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación . FOCS '01. EE. UU.: IEEE Computer Society. págs. 434–441. doi :10.1109/SFCS.2001.959918. ISBN . 978-0-7695-1390-4.S2CID12484006  .​
16. Erdős, P. ; Simonovits, M. (1966). "Un teorema límite en teoría de grafos". Studia Sci. Math. Hung . 1 : 51–57.
17. Erdős, P. (1966). "Algunos resultados recientes sobre problemas extremos en teoría de grafos". Teoría de grafos, Simposio Internacional de Teoría de grafos, Roma : 118–123.
18. Erdős, P. (1966). "Sobre algunas nuevas desigualdades relativas a las propiedades extremales de los grafos". Teoría de grafos, Proc. Coll. Tihany, Hungría : 77–81.
19. Erdős, P. ; Katona, G. (1966). "Un método para resolver problemas extremos en teoría de grafos". Teoría de grafos, Proc. Coll. Tihany : 279–319.
20. Alon, Noga ; Shapira, Asaf (2008), "Una caracterización de las propiedades de gráficos (naturales) comprobables con error unilateral", SIAM Journal on Computing , 37 (6): 1703–1727, doi :10.1137/06064888X, MR  2386211