¿Debe cada gráfica cúbica contener un ciclo simple de longitud una potencia de dos?
En teoría de grafos , la conjetura no probada de Erdős-Gyárfás , realizada en 1995 por el prolífico matemático Paul Erdős y su colaborador András Gyárfás , establece que todo grafo con grado mínimo 3 contiene un ciclo simple cuya longitud es una potencia de dos . Erdős ofreció un premio de $ 100 por probar la conjetura, o $ 50 por un contraejemplo; es una de las muchas conjeturas de Erdős .
Gráfico de Markström | |
---|---|
Vértices | 24 |
Bordes | 36 |
Radio | 5 |
Diámetro | 6 |
Circunferencia | 3 |
Automorfismos | 3 |
Tabla de gráficos y parámetros |
Si la conjetura es falsa, un contraejemplo tomaría la forma de un gráfico con un grado mínimo tres sin potencia de dos ciclos. Se sabe a través de búsquedas informáticas de Gordon Royle y Klas Markström que cualquier contraejemplo debe tener al menos 17 vértices, y cualquier contraejemplo cúbico debe tener al menos 30 vértices. Las búsquedas de Markström encontraron cuatro gráficos en 24 vértices en los que la única potencia de dos ciclos tiene 16 vértices. Uno de estos cuatro gráficos es plano ; sin embargo, ahora se sabe que la conjetura de Erdős-Gyárfás es cierta para el caso especial de grafos planos cúbicos de 3 conexiones ( Heckman y Krakovski 2013 )
Se conocen resultados más débiles que relacionan el grado de un gráfico con conjuntos inevitables de longitudes de ciclo: hay un conjunto S de longitudes, con | S | = O ( n 0,99 ), de modo que todo gráfico con grado medio diez o más contiene un ciclo con su longitud en S ( Verstraëte 2005 ), y cada gráfico cuyo grado medio es exponencial en el logaritmo iterado de n contiene necesariamente un ciclo cuya longitud es una potencia de dos ( Sudakov y Verstraëte 2008 ). También se sabe que la conjetura es cierta para los gráficos planos sin garras ( Daniel y Shauger 2001 ) y para los gráficos que evitan las grandes estrellas inducidas y satisfacen restricciones adicionales en sus grados ( Shauger 1998 ).
Referencias
- Daniel, Dale; Shauger, Stephen E. (2001), "Un resultado de la conjetura de Erdős-Gyárfás en gráficos planares", Proc. 32nd Southeastern Int. Conf. Combinatoria, teoría de grafos y computación , págs. 129-139.
- Heckman, Christopher Carl; Krakovski, Roi (2013), "Conjetura de Erdös-Gyárfás para grafos planos cúbicos" , Electronic Journal of Combinatorics , 20 (2), P7.
- Markström, Klas (2004), "Gráficos extremos para algunos problemas sobre ciclos en gráficos" (PDF) , Congr. Numerantium , 171 : 179–192.
- Shauger, Stephen E. (1998), "Resultados de la conjetura de Erdős-Gyárfás en gráficos libres de K 1, m ", Proc. 29 ° Southeastern Int. Conf. Combinatoria, teoría de grafos y computación , págs. 61–65
- Sudakov, Benny; Verstraëte, Jacques (2008), "Longitudes de ciclo en gráficos dispersos", Combinatorica , 28 (3): 357–372, arXiv : 0707.2117 , doi : 10.1007 / s00493-008-2300-6.
- Verstraëte, Jacques (2005), "Duraciones de ciclo inevitables en gráficos", Journal of Graph Theory , 49 (2): 151-167, doi : 10.1002 / jgt.20072.