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:
Dong Yeap Kang, Tom Kelly, Daniela Kühn , Abhishek Methuku y Deryk Osthus demostraron la conjetura para todos los valores suficientemente grandes de k . [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 formado por k miembros del profesorado, y que todos los comités se reúnen en la misma sala, lo 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 las presidencias a los miembros de los comités de tal manera que cada miembro ocupe la misma presidencia 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 gráfico, los comités corresponden a los gráficos 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 todos 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 los hiperbordes de un n -hipergrafo lineal uniforme que tiene los mismos vértices que el gráfico subyacente. En este lenguaje, la conjetura de Erdős-Faber-Lovász establece que, dado cualquier n -hipergrafo lineal uniforme con n hiperfilos, se pueden n -colorear los vértices de modo que cada hiperfilo tenga un vértice de cada color. [3]
Un hipergrafo simple es un hipergrafo en el que como máximo un hipergrafo conecta cualquier par de vértices y no hay hipergrafos de tamaño como máximo uno. En la formulación de coloración de gráficos 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 hiperborde 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 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 los bordes) como máximo n . [4]
La gráfica de la conjetura de Erdős-Faber-Lovász se puede representar como una gráfica de intersección de conjuntos: a cada vértice del gráfico, corresponde el conjunto de 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 se puede reformular de la siguiente manera: si alguna familia de conjuntos tiene n elementos en total, y dos conjuntos cualesquiera se cruzan 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 gráfico G es el número mínimo de elementos en una familia de conjuntos cuyo gráfico de intersección es G , o equivalentemente el número mínimo de vértices en un hipergráfico cuyo gráfico lineal es G . Klein y Margraf (2003) definen el número de intersección lineal de un gráfico, de manera similar, como el número mínimo de vértices en un hipergráfico lineal cuyo gráfico 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 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 .
Paul Erdős , Vance Faber y László Lovász formularon la aparentemente inofensiva conjetura en una fiesta en Boulder Colorado en septiembre de 1972. Su dificultad se fue comprendiendo lentamente. [1] Paul Erdős ofreció originalmente 50 dólares estadounidenses por demostrar la conjetura afirmativamente, y luego aumentó la recompensa a 500 dólares estadounidenses. [1] [6] De hecho, Paul Erdős consideró que este era uno de sus tres problemas combinatorios favoritos. [1] [7]
Chiang y Lawler (1988) demostraron que el número cromático de las gráficas en la conjetura es como máximo , y Kahn (1992) lo mejoró a k + o ( k ) .
Casi 50 años después de que se formulara 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 de interés 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 algunas gráficas formadas de esta manera requieren tantos colores. [9]
Se sabe que es cierta una versión de la conjetura que utiliza el número cromático fraccionario en lugar del número cromático. Es decir, si un gráfico G se forma como la unión de k k -camarillas que se cruzan por pares en como máximo un vértice, entonces G puede ser k -coloreado. [10]
En el marco de la coloración de bordes 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 un hipergrafo 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. Con base en esta idea, muestra que la conjetura es cierta para todos los hipergrafos simples con L ≤ 10 . En la formulación de gráficos de coloración formados por uniones de camarillas, el resultado de Hindman muestra que la conjetura es verdadera siempre que como máximo diez de las camarillas contengan un vértice que pertenezca a tres o más camarillas. En particular, es cierto para n ≤ 10 .
