En teoría de grafos , la conjetura de Erdős-Faber-Lovász es un problema no resuelto sobre la coloración de grafos , llamado así por Paul Erdős , Vance Faber y László Lovász , quien lo formuló en 1972. [1] Dice:
- Si k gráficas completas , cada una con exactamente k vértices, tienen la propiedad de que cada par de gráficas completas tiene como máximo un vértice compartido, entonces la unión de las gráficas se puede colorear correctamente con k colores.
Una prueba de la conjetura para todos los valores suficientemente grandes de k fue anunciada en 2021 por Dong Yeap Kang, Tom Kelly, Daniela Kühn , Abhishek Methuku y Deryk Osthus . [2] [3]
Formulaciones equivalentes
Haddad y Tardif (2004) introdujeron el problema con una historia sobre la asignación de asientos en los comités: supongamos que, en un departamento universitario, hay k comités, cada uno de los cuales consta de k profesores, y que todos los comités se reúnen en la misma sala, que k sillas. Suponga también que como máximo una persona pertenece a la intersección de dos comités cualesquiera. ¿Es posible asignar presidentes a los miembros del comité de tal manera que cada miembro se sienta en la misma silla para todos los diferentes comités a los que pertenece? En este modelo del problema, los miembros de la facultad corresponden a los vértices de los gráficos, los comités corresponden a los gráficos completos y las sillas corresponden a los colores de los vértices.
Un hipergrama lineal (también conocido como espacio lineal parcial ) es un hipergrama con la propiedad de que cada dos hipergrafos tienen como máximo un vértice en común. Se dice que un hipergráfico es uniforme si todos sus hipergrafos tienen el mismo número de vértices entre sí. Las n camarillas de tamaño n en la conjetura de Erdős-Faber-Lovász pueden interpretarse como las hipergrafias de un hipergrafo lineal n -uniforme que tiene los mismos vértices que el grafo subyacente. En este lenguaje, la conjetura de estados Erdős-Faber-Lovász que, dado cualquier n Uniform lineal hypergraph con n hyperedges, uno puede n -color los vértices de tal manera que cada hyperedge tiene un vértice de cada color. [4]
Un hipergrafo simple es un hipergrafo en el que, como mucho, un hipergrafo conecta cualquier par de vrtices y no hay hipergrafos de tamao como mucho uno. En la formulación de coloración de grafos de la conjetura de Erdős-Faber-Lovász, es seguro eliminar los vértices que pertenecen a una sola camarilla, ya que su coloración no presenta dificultad; Una vez hecho esto, el hipergrafo que tiene un vértice para cada camarilla y un hipergrafo para cada vértice del gráfico, forma un hipergrafo simple. Y, el hipergráfico dual de la coloración de vértices es la coloración de bordes . Por lo tanto, la conjetura de Erdős-Faber-Lovász es equivalente a la afirmación de que cualquier hipergráfico simple con n vértices tiene un índice cromático (número de color de borde) como máximo n . [5]
El gráfico de la conjetura de Erdős-Faber-Lovász puede representarse como un gráfico de intersección de conjuntos: a cada vértice del gráfico, corresponde el conjunto de las camarillas que contienen ese vértice y conecta dos vértices cualesquiera por una arista siempre que sus conjuntos correspondientes tengan una intersección no vacía. Usando esta descripción del gráfico, la conjetura puede reformularse de la siguiente manera: si alguna familia de conjuntos tiene n elementos en total, y dos conjuntos cualesquiera se cruzan en un elemento como máximo, entonces el gráfico de intersección de los conjuntos puede tener n colores. [6]
El número de intersección de un gráfico G es el número mínimo de elementos de una familia de conjuntos cuya intersección gráfica es G , o de forma equivalente el número mínimo de vértices en un hypergraph cuyo gráfico de líneas es G . Klein & Margraf (2003) definen el número de intersección lineal de un gráfico, de manera similar, para ser el número mínimo de vértices en un hypergraph lineal cuya gráfico de líneas es G . Como observan, la conjetura de Erdős-Faber-Lovász es equivalente a la afirmación de que el número cromático de cualquier gráfico es como máximo igual a su número de intersección lineal.
Haddad y Tardif (2004) presentan otra formulación aún equivalente, en términos de la teoría de los clones .
Historial, resultados parciales y eventual prueba
Paul Erdős , Vance Faber y László Lovász formularon la conjetura de apariencia inofensiva en una fiesta en Boulder Colorado en septiembre de 1972. Su dificultad se comprendió lentamente. [1] Paul Erdős originalmente ofreció US $ 50 por probar la conjetura afirmativamente, y luego aumentó la recompensa a US $ 500. [1] [7] De hecho, Paul Erdős consideró que este era uno de sus tres problemas combinatorios favoritos. [1] [8]
Chiang y Lawler (1988) demostraron que el número cromático de los gráficos en la conjetura es como máximo 3 k / 2 - 2 , y Kahn (1992) lo mejoró a k + o ( k ) .
En 2021, 49 años después de que se estableciera la conjetura original, [1] [9] se afirmó que estaba resuelta para todos los n suficientemente grandes .
Problemas relacionados
También es de interés considerar el número cromático de gráficas formadas como la unión de k camarillas de k vértices cada una, sin restringir cuán grandes pueden ser las intersecciones de pares de camarillas. En este caso, el número cromático de su unión es como máximo 1 + k √ k - 1 , y algunos gráficos formados de esta manera requieren esta cantidad de colores. [10]
Se sabe que una versión de la conjetura que usa el número cromático fraccionario en lugar del número cromático es cierta. Es decir, si una gráfica G se forma como la unión de k k -cliques que se cruzan por pares en como máximo un vértice, entonces G puede tener k- color. [11]
En el marco de los hipergráficos simples de coloración de bordes, Hindman (1981) define un número L a partir de un hipergráfico simple como el número de vértices del hipergráfico que pertenecen a una hipergrafia de tres o más vértices. El autor muestra que, para cualquier valor fijo de L , un cálculo finito es suficiente para verificar que la conjetura es cierta para todos los hipergrafos simples con que el valor de L . Basado en esta idea, muestra que la conjetura es verdadera para todos los hipergráficos simples con L ≤ 10 . En la formulación de gráficos de colores formados por uniones de camarillas, el resultado de Hindman muestra que la conjetura es cierta siempre que como máximo diez de las camarillas contienen un vértice que pertenece a tres o más camarillas. En particular, es cierto para n ≤ 10 .
Ver también
Notas
- ↑ a b c d e Erdős (1981) .
- ↑ Kalai (2021) ; Kang y col. (2021)
- ^ Houston-Edwards, Kelsey. "Los matemáticos resuelven la conjetura de coloración de Erdős" . Revista Quanta . Consultado el 5 de abril de 2021 .
- ^ Romero y Sánchez Arroyo (2007) .
- ^ Chiang y Lawler (1988) . Hindman (1981) describe un problema equivalente en el lenguaje de sistemas de conjuntos en lugar de hipergráficos.
- ^ Hindman (1981) .
- ^ Chung y Graham (1998) .
- ^ Kahn (1997) .
- ^ Kang y col. (2021) .
- ↑ Erdős (1991) ; Horák y Tuza (1990) .
- ^ Kahn y Seymour (1992) .
{{citación
| last1 = Bretto | first1 = Alain | authorlink1 = Alain Bretto| last2 = Faisant | first2 = Alain | authorlink2 = Alain Faisant| last3 = Hennecart | first2 = François | authorlink2 = François Hennecart| title = Sobre la coloración hipergrande de hipergráficos débilmente triangulares e hipergráficos bien ordenados| journal = Matemáticas discretas| volumen = 343 | problema = 11 | año = 2020 | páginas = 112059
Matemáticas discretas |
{{citación
| last1 = Bretto | first1 = Alain | authorlink1 = Alain Bretto| last2 = Faisant | first2 = Alain | authorlink2 = Alain Faisant| last3 = Hennecart | first2 = François | authorlink2 = François Hennecart| title = Sobre la coloración hipergrande de hipergráficos débilmente triangulares e hipergráficos bien ordenados| journal = Matemáticas discretas| volumen = 343 | problema = 11 | año = 2020 | páginas = 112059
Matemáticas discretas |
Referencias
- Chiang, WI; Lawler, EL (1988), "Coloración de bordes de hipergráficos y una conjetura de Erdős, Faber, Lovász", Combinatorica , 8 (3): 293-295, doi : 10.1007 / BF02126801 , MR 0963120.
- Chung, Fan ; Graham, Ron (1998), Erdős on Graphs: His Legacy of Unsolved Problems , AK Peters, págs. 97–99.
- Erdős, Paul (1981), "Sobre los problemas combinatorios que más me gustaría ver resueltos", Combinatorica , 1 : 25–42, CiteSeerX 10.1.1.294.9566 , doi : 10.1007 / BF02579174 , MR 0602413.
- Erdős, Paul (1991), "Problema avanzado 6664", American Mathematical Monthly , Asociación Matemática de América, 98 (7): 655, doi : 10.2307 / 2324942 , JSTOR 2324942. Soluciones de Ilias Kastanas, Charles Vanden Eynden y Richard Holzsager , American Mathematical Monthly 100 (7): 692–693, 1992.
- Haddad, L .; Tardif, C. (2004), "Una formulación teórica de clones de la conjetura de Erdős-Faber-Lovasz", Discussiones Mathematicae Graph Theory , 24 (3): 545–549, doi : 10.7151 / dmgt.1252 , MR 2120637.
- Hindman, Neil (1981), "Sobre una conjetura de Erdős, Faber y Lovász acerca de los n- colores", Can. J. Math. , 33 (3): 563–570, doi : 10.4153 / CJM-1981-046-9 , MR 0627643.
- Horák, P .; Tuza, Z. (1990), "Un problema de coloración relacionado con la conjetura de Erdős-Faber-Lovász", Journal of Combinatorial Theory, Serie B , 50 (2): 321–322, doi : 10.1016 / 0095-8956 (90) 90087-G. Corregido en JCTB 51 (2): 329, 1991 , para agregar el nombre de Tuza como coautor.
- Kahn, Jeff (1992), "Colorear hipergráficos casi disjuntos con n + o ( n ) colores", Journal of Combinatorial Theory, Serie A , 59 : 31–39, doi : 10.1016 / 0097-3165 (92) 90096-D , Señor 1141320.
- Kahn, Jeff ; Seymour, Paul D. (1992), "Una versión fraccionada de la conjetura de Erdős-Faber-Lovász", Combinatorica , 12 (2): 155-160, doi : 10.1007 / BF01204719 , MR 1179253.
- Kahn, Jeff (1997), Sobre algunos problemas hipergráficos de Paul Erdős y las asintóticas de emparejamientos, portadas y coloraciones , Springer Berlin Heidelber, págs. 345–371, ISBN 978-3-642-60408-9
- Kalai, Gil (14 de enero de 2021), "Para animarte en tiempos difíciles 17: ¡Increíble! La conjetura de Erdős-Faber-Lovász (para n grande) fue probada por Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, y Deryk Osthus! " , Combinatoria y más
- Kang, Dong Yeap; Kelly, Tom; Kühn, Daniela; Methuku, Abhishek; Osthus, Deryk (2021), Una prueba de la conjetura de Erdős-Faber-Lovász , arXiv : 2101.04698
- Klein, Hauke; Margraf, Marian (2003), Sobre el número de gráficas de intersección lineal , arXiv : math.CO/0305073.
- Romero, David; Sánchez Arroyo, Abdón (2007), "Avances en la conjetura de Erdős-Faber-Lovász", en Grimmet, Geoffrey; McDiarmid, Colin (eds.), Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh , Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, págs. 285-298, doi : 10.1093 / acprof: oso / 9780198571278.003. 0017 , ISBN 9780198571278.