Conjetura de Erdős-Hajnal

Conjetura en la teoría de grafos

Problema sin resolver en matemáticas :

¿Los gráficos con un subgráfico inducido prohibido fijo tienen necesariamente camarillas grandes o conjuntos independientes grandes?

(más problemas sin resolver en matemáticas)

En la teoría de grafos , una rama de las matemáticas, la conjetura de Erdős-Hajnal establece que las familias de grafos definidas por subgrafos inducidos prohibidos tienen grandes camarillas o grandes conjuntos independientes . Recibe su nombre de Paul Erdős y András Hajnal , quienes la plantearon por primera vez como un problema abierto en un artículo de 1977. ^[1]

Más precisamente, para un grafo no dirigido arbitrario , sea la familia de grafos que no tienen como subgrafo inducido . Entonces, según la conjetura, existe una constante tal que los grafos de -vértice en tienen una camarilla o un conjunto independiente de tamaño . En otras palabras, para cualquier familia hereditaria de grafos que no sea la familia de todos los grafos, existe una constante tal que los grafos de -vértice en tienen una camarilla o un conjunto independiente de tamaño . ${\displaystyle H}$ ${\displaystyle {\mathcal {F}}_{H}}$ ${\displaystyle H}$ ${\displaystyle \delta _{H}>0}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {F}}_{H}}$ ${\displaystyle \Omega (n^{\delta _{H}})}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \delta _{\mathcal {F}}>0}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \Omega (n^{\delta _{\mathcal {F}}})}$

Una reformulación conveniente y simétrica de la conjetura de Erdős–Hajnal es que para cada grafo , los grafos libres de α necesariamente contienen un subgrafo inducido perfecto de tamaño polinomial. Esto se debe a que cada grafo perfecto necesariamente tiene un grupo o conjunto independiente de tamaño proporcional a la raíz cuadrada de su número de vértices y, a la inversa, cada grupo o conjunto independiente es en sí mismo perfecto. ${\displaystyle H}$ ${\displaystyle H}$

Los antecedentes de esta conjetura se pueden encontrar en dos estudios, uno de András Gyárfás y el otro de Maria Chudnovsky . ^{[2] [3]}

Gráficos sin grandes camarillas ni conjuntos independientes

En cambio, para los grafos aleatorios en el modelo de Erdős–Rényi con probabilidad de arista 1/2, tanto el grupo máximo como el conjunto independiente máximo son mucho más pequeños: su tamaño es proporcional al logaritmo de , en lugar de crecer polinomialmente. El teorema de Ramsey demuestra que ningún grafo tiene tanto su tamaño máximo de grupo como su tamaño máximo de conjunto independiente menores que logarítmicos. El teorema de Ramsey también implica el caso especial de la conjetura de Erdős–Hajnal cuando ella misma es un grupo o un conjunto independiente. ${\displaystyle n}$ ${\displaystyle H}$

Resultados parciales

Esta conjetura se debe a Paul Erdős y András Hajnal , quienes demostraron que es cierta cuando es un cografo . ^[4] También demostraron, para arbitrario , que el tamaño de la camarilla o conjunto independiente más grande crece superlogarítmicamente. Más precisamente, para cada hay una constante tal que los grafos -libres de vértices tienen camarillas o conjuntos independientes que contienen al menos vértices. ^{[1] [4]} Los grafos para los que la conjetura es verdadera también incluyen aquellos con cuatro vértices o menos, todos los grafos de cinco vértices, ^{[5] [6] [7] [8]} y cualquier grafo que pueda obtenerse de estos y los cografos por descomposición modular . ^[9] Sin embargo, a partir de 2024, la conjetura completa no ha sido probada y sigue siendo un problema abierto. ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle H}$ ${\displaystyle \exp c{\sqrt {\log n}}}$ ${\displaystyle H}$

Una formulación anterior de la conjetura, también de Erdős y Hajnal, se refiere al caso especial cuando es un gráfico de ciclo de 5 vértices . ^[2] Este caso ha sido resuelto por Maria Chudnovsky , Alex Scott, Paul Seymour y Sophie Spirkl. ^[7] ${\displaystyle H}$

Relación con el número cromático de torneos

Alon et al. ^[9] demostraron que la siguiente afirmación sobre los torneos es equivalente a la conjetura de Erdős-Hajnal.

Conjetura. Para cada torneo , existe y tal que para cada torneo -libre con vértices . ${\displaystyle T}$ ${\displaystyle \varepsilon (T)>0}$ ${\displaystyle c>0}$ ${\displaystyle T}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \chi (G)\leq c\cdot n^{1-\varepsilon }}$

Aquí se denota el número cromático de , que es el más pequeño tal que existe una coloración para . Una coloración de un torneo es una aplicación tal que las clases de color son transitivas para todos los . ${\displaystyle \chi (G)}$ ${\displaystyle G}$ ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \phi :V(G)\rightarrow \{1,\ldots ,k\}}$ ${\displaystyle \{v\in V(T):\phi (v)=i\}}$ ${\displaystyle i=1,\ldots ,k}$

La clase de torneos con la propiedad de que todo torneo libre de - tiene para alguna constante satisface esta conjetura equivalente de Erdős–Hajnal (con ). Dichos torneos , llamados héroes, fueron considerados por Berger et al. ^[10] Allí se demuestra que un héroe tiene una estructura especial que es la siguiente: ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle \chi (G)\leq c(H)}$ ${\displaystyle c(H)}$ ${\displaystyle \varepsilon =1}$ ${\displaystyle H}$

Teorema. Un torneo es heroico si y solo si todos sus componentes fuertes son héroes. Un torneo fuerte con más de un vértice es heroico si y solo si es igual a o para algún héroe y algún entero . ${\displaystyle \Delta (H,k,1)}$ ${\displaystyle \Delta (H,1,k)}$ ${\displaystyle H}$ ${\displaystyle k\geq 0}$

Aquí se denota el torneo con los tres componentes , el torneo transitivo de tamaño y un solo nodo . Los arcos entre los tres componentes se definen de la siguiente manera: . El torneo se define de forma análoga. ${\displaystyle \Delta (H,k,1)}$ ${\displaystyle H}$ ${\displaystyle k}$ ${\displaystyle q}$ ${\displaystyle A=\{(v,w):(v\in H\wedge w\in T_{k})\vee (v\in T_{k}\wedge w=q)\vee (v=q\wedge w\in H)\}}$ ${\displaystyle \Delta (H,1,k)}$

Referencias

1. Erdős, P. ; Hajnal, A. (1977), "Sobre subgrafos generados de grafos" (PDF) , Contribuciones a la teoría de grafos y sus aplicaciones (Internat. Colloq., Oberhof, 1977) (alemán) , Tech. Hochschule Ilmenau, Ilmenau, pp. 80–96, MR  0599767.
2. Gyárfás, András (1997), "Reflexiones sobre un problema de Erdős y Hajnal", Las matemáticas de Paul Erdős, II , Algoritmos combinados, vol. 14, Springer, Berlín, págs. 93–98, doi :10.1007/978-3-642-60406-5_10, ISBN 978-3-642-64393-4, Sr.  1425208.
3. Chudnovsky, Maria (2014), "La conjetura de Erdös-Hajnal: una encuesta" (PDF) , Journal of Graph Theory , 75 (2): 178–190, arXiv : 1606.08827 , doi :10.1002/jgt.21730, MR  3150572 , S2CID  985458, Zbl  1280.05086.
4. Erdős, P .; Hajnal, A. (1989), "Teoremas de tipo Ramsey", Matemáticas aplicadas discretas , 25 (1–2): 37–52, doi : 10.1016/0166-218X(89)90045-0 , MR  1031262, Zbl  0715.05052.
5. Nguyen, T., Scott, A. y Seymour, P., 2023. Densidad de subgrafos inducida. VII. El camino de cinco vértices. Preimpresión de arXiv arXiv:2312.15333.
6. Nadis, Steve (26 de abril de 2021). «Nueva prueba revela que los gráficos sin pentágonos son fundamentalmente diferentes». Quanta Magazine . Consultado el 26 de abril de 2021 .
7. Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie (31 de enero de 2023). "Erdős–Hajnal para gráficos sin 5 agujeros". Actas de la London Mathematical Society . 126 (3). Wiley: 997–1014. arXiv : 2102.04994 . doi : 10.1112/plms.12504 . ISSN  0024-6115.
8. Chudnovsky, Maria ; Safra, Shmuel (2008), "La conjetura de Erdős–Hajnal para grafos sin toros", Journal of Combinatorial Theory , Serie B, 98 (6): 1301–1310, doi : 10.1016/j.jctb.2008.02.005 , MR  2462320.
9. Alon, Noga ; Pach, János ; Solymosi, József (2001), "Teoremas de tipo Ramsey con subgrafos prohibidos", Combinatorica , 21 (2): 155–170, doi :10.1007/s004930100016, MR  1832443, S2CID  7590638, Zbl  0989.05124.
10. Berger, E.; Choromanski, K.; Chudnovsky, M .; Fox, J .; Loebl, M.; Scott, A.; Seymour, P .; Thomasse, S. (2013), "Torneos y coloración", Journal of Combinatorial Theory, Serie B , 103 (1): 1–20, doi : 10.1016/j.jctb.2012.08.003 , hdl : 1721.1/99446.

Enlaces externos

• La conjetura de Erdös-Hajnal, el jardín de problemas abiertos