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]

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]${\estilo de visualización H}$${\estilo de visualización h}$${\displaystyle \epsilon >0}$${\displaystyle \delta =\delta (\epsilon,H)>0}$${\estilo de visualización n}$${\estilo de visualización G}$${\displaystyle \delta n^{h}}$ ${\estilo de visualización H}$${\estilo de visualización H}$${\displaystyle \épsilon n^{2}}$${\estilo de visualización 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 .${\estilo de visualización n}$${\estilo de visualización G}$${\displaystyle o(n^{h})}$${\estilo de visualización H}$${\estilo de visualización H}$${\displaystyle o(n^{2})}$${\estilo de visualización G}$${\estilo de visualización o}$

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

La motivación original para el estudio del lema de eliminación de triángulos fue el problema de Ruzsa-Szemerédi . Su 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]${\estilo de visualización 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 declaració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]${\estilo de visualización r}$$Estilo de visualización H_{2}$$Estilo de visualización H_{2}$$Estilo de visualización H_{1}$${\estilo de visualización G}$${\estilo de visualización n}$$Estilo de visualización H_{2}$${\displaystyle o(n^{2})}$

La formulación moderna del lema de eliminación de grafos fue enunciada 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, que también utilizaron el lema de regularidad de Szemerédi .

Un componente clave de la demostración del lema de 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]

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 tales que, para todo , el par es - regular (en el sentido del lema de regularidad). Sea también la densidad entre los 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 tales que debería ser cercano al número esperado a partir del modelo Erdős–Rényi, donde y son el conjunto de aristas y el conjunto de vértices de .${\estilo de visualización H}$${\estilo de visualización h}$${\displaystyle V=\{1,2,\ldots ,h\}}$${\estilo de visualización E}$${\displaystyle X_{1},X_{2},\ldots ,X_{h}}$${\estilo de visualización G}$${\displaystyle ij\in E}$${\displaystyle (X_{i},X_{j})}$${\displaystyle \épsilon}$$estilo de visualización d_ {ij}}$$Estilo de visualización X_{i}}$$Estilo de visualización X_ {j}}$${\estilo de visualización (X,Y)}$${\estilo de visualización d}$${\displaystyle (x,y)\en (X\veces Y)}$${\estilo de visualización d}$${\estilo de visualización H}$${\displaystyle x_{1},x_{2},\ldots ,x_{h}}$${\displaystyle x_{i}\en 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}$

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 cuyo 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}|.}$$

Incluso se pueden encontrar subgrafos de grado acotado de explosiones de en un contexto 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 utiliza en numerosas pruebas basadas en regularidad. ^[10]${\displaystyle H}$

Sea un grafo arbitrario y sea . Construya reemplazando cada vértice de por un conjunto independiente de tamaño y reemplazando cada arista de por el grafo bipartito completo en . Sean números reales arbitrarios, sea un entero positivo y sea un subgrafo de con vértices y grado máximo . Defina . Finalmente, sea un grafo y sean conjuntos disjuntos de vértices de tales que, siempre que , entonces es un par -regular con densidad al menos . Entonces, si y , entonces 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 puede restringirse a contar solo aquellos homomorfismos tales que cualquier vértice de con se asigna a un vértice en .${\displaystyle k\in [h]}$${\displaystyle H_{2}}$${\displaystyle k\in V_{i}}$${\displaystyle X_{i}}$

Proporcionaremos una prueba del lema de conteo en el caso en que es 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 el total serían testigos de la -irregularidad del par . Repetir este argumento para muestra que debemos tener . Ahora tome un arbitrario y defina y como vecinos de en y , respectivamente. Por definición, y , entonces por la 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 )|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}|,}$$${\displaystyle \epsilon =\delta /2}$

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 al menos un triángulo todavía permanece, 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}}$

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}.}$$

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}$

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}$

Alon , Fischer, Krivelevich y Szegedy demostraron en 2000 una versión del lema de 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értice 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 y 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 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}}$

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}}}$

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 es -regular. Esto nos permite considerar aristas y no aristas cuando realizamos nuestro argumento de limpieza.${\displaystyle W_{i},W_{j}}$${\displaystyle \epsilon _{|{\mathcal {P}}|}}$

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 conecte 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}$

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

El uso del lema de regularidad en la prueba del lema de eliminación de grafos obliga a que sea extremadamente pequeño, acotado por una función de torre cuya altura es polinómica en ; es decir, (aquí está la torre de dos en dos de altura ). Una 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 utiliza 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, utiliza 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 utilizando el lema de regularidad débil de Frieze-Kannan como lo señalaron 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)}}$

Hay una gran brecha entre los límites superior e inferior disponibles 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 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 grandes conjuntos de Salem-Spencer. De hecho, como el lema de eliminación de triángulos implica el teorema de Roth , la existencia de grandes conjuntos de Salem-Spencer puede traducirse a un límite superior para en el lema de eliminación de triángulos. Este método se puede aprovechar para que cualquier no bipartito arbitrario dé 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}$

• Lema de conteo
• La conjetura de Tuza