Lema de eliminación de hipergrafo

---

En la teoría de grafos, el lema de eliminación de hipergráficos establece que cuando un hipergráfico contiene pocas copias de un sub-hipergráfico dado, todas las copias se pueden eliminar eliminando una pequeña cantidad de hipergráficos. Es una generalización del lema de eliminación de grafos . El caso especial en el que el gráfico es un tetraedro se conoce como el lema de eliminación de tetraedros . Primero fue probado por Gowers ^[1] e, independientemente, por Nagle, Rödl, Schacht y Skokan. ^[2]

El lema de eliminación de hipergrafía se puede utilizar para demostrar resultados como el teorema de Szemerédi ^[2] y el teorema multidimensional de Szemerédi. ^[2]

El lema de eliminación de hipergrafía establece que para cualquier , existe tal que para cualquier hipergrafía uniforme con vértices se cumple lo siguiente: si hay alguna hipergrafía uniforme de vértice con como máximo subgrafos isomorfos a , entonces es posible eliminar todas las copias de de eliminando como máximo los hiperbordes de .${\displaystyle\varepsilon,r,m>0}$${\displaystyle \delta =\delta (\varepsilon,r,m)>0}$${\ estilo de visualización r}$${\ estilo de visualización H}$${\ estilo de visualización m}$${\ estilo de visualización G}$${\ estilo de visualización n}$${\ estilo de visualización r}$${\ estilo de visualización \ delta n ^ {v (H)}}$${\ estilo de visualización H}$${\ estilo de visualización H}$${\ estilo de visualización G}$${\ estilo de visualización \ varepsilon n^ {r}}$${\ estilo de visualización G}$

Una formulación equivalente es que, para cualquier gráfico con copias de , podemos eliminar todas las copias de quitando los hiperbordes.${\ estilo de visualización G}$${\ estilo de visualización o (n ^ {v (H)})}$${\ estilo de visualización H}$${\ estilo de visualización H}$${\ estilo de visualización G}$${\ estilo de visualización o (n ^ {r})}$

La idea de alto nivel de la prueba es similar a la del lema de eliminación de gráficos . Probamos una versión de hipergrafía del lema de regularidad de Szemerédi (partición de hipergrafías en bloques pseudoaleatorios) y un lema de conteo (estimación del número de hipergrafías en un bloque pseudoaleatorio apropiado). La dificultad clave en la demostración es definir la noción correcta de regularidad hipergráfica. Hubo múltiples intentos ^{[3] [4] [5] [6] [7] [8] [9] [10] [11] [12]}para definir "partición" y "bloques pseudoaleatorios (regulares)" en una hipergrafía, pero ninguno de ellos puede dar un lema de conteo fuerte. La primera definición correcta del lema de regularidad de Szemerédi para hipergrafías generales está dada por Rödl et al. ^[2]

---