Hipótesis de Erdős-Hajnal

Problemas no resueltos en Matemáticas : ¿Es cierto que los gráficos con un subgrafo inducido prohibido fijo necesariamente tienen grandes camarillas o grandes conjuntos independientes?

La conjetura de Erdős-Hajnal establece que las familias de grafos definidos por subgrafos inducidos prohibidos tienen grandes camarillas o grandes conjuntos independientes . Más precisamente, para un gráfico no dirigido arbitrario, sea una familia de gráficos que no contengan como subgráfico generado . Entonces, de acuerdo con la hipótesis, existe una constante tal que los gráficos con vértices en tienen un grupo de tamaño clique o independiente . $H$ ${\mathcal {F}}_{H}$ $H$ ${\ estilo de visualización \ delta _ {H}> 0}$ $norte$ ${\mathcal {F}}_{H}$ $\Omega (n^{\delta _{H)))$

Una declaración equivalente de la conjetura original: para cualquier gráfico , los gráficos que no contienen contienen subgrafos generados perfectos arbitrariamente grandes . $H$ $H$

Gráficos sin grandes camarillas o conjuntos independientes

A modo de comparación, para gráficos aleatorios en el modelo Erdős-Rényi con probabilidad de borde 1/2, tanto la camarilla más grande como el conjunto independiente más grande son mucho más pequeños: su tamaño es proporcional al logaritmo de y no crece polinomialmente. El teorema de Ramsey demuestra que ningún gráfico tiene tanto el tamaño de la camarilla más grande como el tamaño del conjunto independiente más grande menos que logarítmico [1] [2] . El teorema de Ramsey también implica un caso especial de la hipótesis de Erdős-Hajnal, cuando el gráfico en sí es una camarilla o un conjunto independiente [1] . $norte$ $H$

Resultados parciales

La conjetura pertenece a Pal Erdős y András Hajnal , quienes la probaron para el caso cuando es un cografo . También mostraron para un gráfico arbitrario que el tamaño de la camarilla más grande o conjunto independiente crece superlogarítmicamente. Más precisamente, para cualquier gráfico hay una constante tal que los gráficos sin vértice tienen camarillas o conjuntos independientes que contienen al menos vértices [1] . Los gráficos para los cuales la conjetura es verdadera también incluyen un camino [1] [3] con cuatro vértices, una cabeza de toro [1] [4] con cinco vértices, y cualquier gráfico que se pueda obtener de estos gráficos y cografos usando un modular descomposición [1] [2] . Sin embargo, a partir de 2021, la hipótesis no se ha probado por completo y sigue siendo un problema abierto [5] . $H$ $H$ $H$ $C$ $H$ $norte$ $\exp c{\sqrt {\log n))$ $H$

Una formulación anterior de la conjetura, también debida a Erdős y Hajnal, se refiere al caso especial en el que el gráfico es un gráfico-ciclo de 5 vértices [3] . Según la preimpresión de 2021, la conjetura es cierta en este caso [5] . Los gráficos que no contienen incluyen gráficos perfectos , que necesariamente tienen una camarilla o un conjunto independiente con un tamaño proporcional a la raíz cuadrada de su número de vértices. Por el contrario, cualquier conjunto clique o independiente es en sí mismo un gráfico perfecto. Por esta razón, una formulación conveniente y simétrica de la conjetura de Erdős-Hajnal es la afirmación de que para cualquier gráfico , los gráficos que no contienen necesariamente contienen un subgráfico perfecto generado de tamaño polinomial [1] [6] . $H$ ${\ estilo de visualización C_ {5}}$ $H$ $H$

Notas

↑ 1 2 3 4 5 6 7 Erdős, Hajnal, 1989 , p. 37–52.
↑ 1 2 Alon, Pach, Solymosi, 2001 , pág. 155–170.
↑ 1 2 Gyárfás, 1997 , p. 93–98.
↑ Chudnovsky, Safra, 2008 , pág. 1301–1310.
↑ 12Steve Nadis . Nueva prueba revela que los gráficos sin pentágonos son fundamentalmente diferentes . Cuanta (26 de abril de 2021). Consultado el 26 de abril de 2021. Archivado desde el original el 26 de abril de 2021. (indefinido)
↑ Chudnovsky, 2014 , pág. 178–179.

Literatura

Erdős P. , Hajnal A. Teoremas de tipo Ramsey // Matemática aplicada discreta. - 1989. - T. 25 , núm. 1-2 . — págs. 37–52 . - doi : 10.1016/0166-218X(89)90045-0 .
Andras Gyarfas. Reflexiones sobre un problema de Erdős y Hajnal // Las matemáticas de Paul Erdős, II. - Springer, Berlín, 1997. - T. 14. - S. 93-98. - (Combinación de Algoritmos). -doi : 10.1007 / 978-3-642-60406-5_10 .
María Chudnovsky, Shmuel Safra. La conjetura de Erdős-Hajnal para gráficos sin toros // Journal of Combinatorial Theory. - 2008. - T. 98 , núm. 6 _ - S. 1301-1310 . -doi : 10.1016/ j.jctb.2008.02.005 .
Noga Alon, Janos Pach, Jozsef Solymosi. Teoremas tipo Ramsey con subgrafos prohibidos // Combinatorica . - 2001. - T. 21 , núm. 2 . — S. 155–170 . -doi : 10.1007/ s004930100016 .
María Chudnovsky. La conjetura de Erdös-Hajnal: una encuesta // Journal of Graph Theory. - 2014. - T. 75 , núm. 2 . — S. 178–190 . -doi : 10.1002/ jgt.21730 . -arXiv : 1606.08827 . _

Enlaces

La conjetura de Erdös-Hajnal | Jardín de problemas abiertos Archivado el 22 de diciembre de 2017 en Wayback Machine .