En teoría de grafos , la conjetura de Erdős-Faber-Lovász es un problema sobre la coloración de grafos , que lleva el nombre de Paul Erdős , Vance Faber y László Lovász , quienes la formularon en 1972. [1] Dice:
La conjetura para todos los valores suficientemente grandes de k fue demostrada por Dong Yeap Kang, Tom Kelly, Daniela Kühn , Abhishek Methuku y Deryk Osthus . [2]
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 ellos formado por k miembros de la facultad, y que todos los comités se reúnen en la misma sala, que tiene k sillas. Supongamos también que, como máximo, una persona pertenece a la intersección de dos comités cualesquiera. ¿Es posible asignar a los miembros del comité a las sillas de tal manera que cada miembro se siente 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 del grafo, los comités corresponden a los grafos completos y las sillas corresponden a los colores de los vértices.
Un hipergrafo lineal (también conocido como espacio lineal parcial ) es un hipergrafo con la propiedad de que cada dos hiperaristas tienen como máximo un vértice en común. Se dice que un hipergrafo es uniforme si todas sus hiperaristas 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 hiperaristas de un hipergrafo lineal n -uniforme que tiene los mismos vértices que el grafo subyacente. En este lenguaje, la conjetura de Erdős–Faber–Lovász establece que, dado cualquier hipergrafo lineal n -uniforme con n hiperaristas, se pueden n -colorear los vértices de modo que cada hiperarista tenga un vértice de cada color. [3]
Un hipergrafo simple es un hipergrafo en el que como máximo una hiperarista conecta cualquier par de vértices y no hay hiperaristas de tamaño como máximo 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 una hiperarista para cada vértice de grafo, forma un hipergrafo simple. Y, el hipergrafo dual de coloración de vértices es coloración de aristas . Por lo tanto, la conjetura de Erdős–Faber–Lovász es equivalente a la afirmación de que cualquier hipergrafo simple con n vértices tiene un índice cromático (número de coloración de aristas) como máximo n . [4]
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 se conectan dos vértices cualesquiera mediante una arista siempre que sus conjuntos correspondientes tengan una intersección no vacía . Utilizando 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 intersecan en, como máximo, un elemento, entonces el gráfico de intersección de los conjuntos puede tener n colores. [5]
El número de intersección de un grafo G es el número mínimo de elementos en una familia de conjuntos cuyo grafo de intersección es G , o equivalentemente el número mínimo de vértices en un hipergrafo cuyo grafo lineal es G . Klein y Margraf (2003) definen el número de intersección lineal de un grafo, de manera similar, como el número mínimo de vértices en un hipergrafo lineal cuyo grafo lineal 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 grafo 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 .
Paul Erdős, Vance Faber y László Lovász formularon esta conjetura aparentemente inofensiva en una fiesta en Boulder, Colorado, en septiembre de 1972. Su dificultad se comprendió lentamente. [1] Paul Erdős ofreció originalmente 50 dólares por demostrar la conjetura de manera afirmativa, y más tarde aumentó la recompensa a 500 dólares. [1] [6] De hecho, Paul Erdős consideraba que este era uno de sus tres problemas combinatorios favoritos . [1] [7]
Chiang y Lawler (1988) demostraron que el número cromático de los grafos en la conjetura es como máximo , y Kahn (1992) lo mejoró a k + o ( k ) .
En 2023, casi 50 años después de que se estableciera la conjetura original, [1] Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku y Deryk Osthus la resolvieron para todos los n suficientemente grandes. [8]
También es interesante considerar el número cromático de grafos formados 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 grafos formados de esta manera requieren esta cantidad de colores. [9]
Se sabe que una versión de la conjetura que utiliza el número cromático fraccionario en lugar del número cromático es verdadera. Es decir, si un grafo G se forma como la unión de k k -cliques que se intersecan de a pares en, como máximo, un vértice, entonces G puede ser k -coloreado. [10]
En el marco de la coloración de aristas de hipergrafos simples, Hindman (1981) define un número L de un hipergrafo simple como el número de vértices del hipergrafo que pertenecen a una hiperarista de tres o más vértices. Muestra que, para cualquier valor fijo de L , un cálculo finito es suficiente para verificar que la conjetura es verdadera para todos los hipergrafos simples con ese valor de L . Basándose en esta idea, muestra que la conjetura es de hecho verdadera para todos los hipergrafos simples con L ≤ 10 . En la formulación de la coloración de grafos formados por uniones de cliques, el resultado de Hindman muestra que la conjetura es verdadera siempre que como máximo diez de los cliques contengan un vértice que pertenezca a tres o más cliques. En particular, es verdadera para n ≤ 10 .
