Lema de eliminación de gráficos

El lema de eliminación de gráficos establece que si un gráfico contiene múltiples copias de un subgráfico dado , todas sus copias pueden eliminarse eliminando una pequeña cantidad de bordes [1] . El lema a veces se denomina lema de eliminación de triángulos cuando el subgrafo es un triángulo [2] .

Redacción

Sea un grafo con vértices. Luego, para cualquier gráfico con vértices que tenga subgráficos isomorfos , uno puede eliminar todos estos subgráficos eliminando los bordes de . Aquí significa "o pequeño" [1] . $H$ $h$ $GRAMO$ $norte$ ${\ estilo de visualización o (n ^ {h})}$ $H$ ${\ estilo de visualización o (n ^ {2})}$ $GRAMO$ $o$

Pruebas y generalizaciones

El Lema de Eliminación de Gráficos fue probado originalmente para el caso donde el subgráfico es un triángulo en 1978 por Imre Z. Rouge y Endre Szemeredy usando el Lema de Regularidad de Szemeredy [3] . Posteriormente, el lema se extendió a otros tipos de subgrafos [4] —grafos dirigidos [5] e hipergrafos [6] . Jacob Fox publicó en 2011 [1] una prueba alternativa que proporciona límites más fuertes en la cantidad de bordes que se eliminarán en función de la cantidad de copias de subgráficos .

Aplicaciones

Rouge y Szemerédy formularon el lema de eliminación de triángulos para proporcionar límites superiores subcuadráticos para el problema de Rouge-Szemerédy sobre el tamaño de los gráficos en los que cualquier borde pertenece a un solo triángulo . El lema de eliminación de gráficos tiene aplicaciones en las pruebas de propiedades , porque implica que en cualquier gráfico, el gráfico está casi libre de gráficos o las muestras aleatorias pueden encontrar fácilmente una copia en el gráfico [5] . El lema de eliminación de hipergrafías se puede utilizar para probar el teorema de Szemerédy sobre la existencia de progresiones aritméticas largas en subconjuntos densos de números enteros [6] . $H$ $H$

Notas

↑ 1 2 3 Jacob Fox. Una nueva prueba del lema de eliminación de gráficos // Annals of Mathematics . - 2011. - T. 174 , núm. 1 . — S. 561–579 . -doi : 10.4007 / annals.2011.174.1.17 .
↑ Luca Trevisan. El lema de remoción de triángulos . - 2009. - Mayo.
↑ Imre Z. Ruzsa, Endre Szemerédi. Combinatoria (Proc. Quinto coloquio húngaro, Keszthely, 1976), vol. II. - Holanda Septentrional, 1978. - T. 18 . — S. 939–945 .
↑ Paul Erdős, Peter Frankl, Vojtěch Rödl. El número asintótico de gráficos que no contienen un subgráfico fijo y un problema para hipergráficos que no tienen exponente // Gráficos y combinatoria. - 1986. - Vol. 2 , número. 2 . — S. 113–121 . -doi : 10.1007/ BF01788085 .
↑ 1 2 Noga Alon, Asaf Shapira. Prueba de subgrafos en grafos dirigidos // Journal of Computer and System Sciences. - 2004. - T. 69 , núm. 3 . — S. 353–382 . -doi : 10.1016/ j.jcss.2004.04.008 .
↑ 1 2 Terence Tao. Una variante del lema de eliminación de hipergrafías // Journal of Combinatorial Theory. - 2006. - T. 113 , núm. 7 . - S. 1257-1280 . -doi : 10.1016/ j.jcta.2005.11.006 .