Hipótesis de Erdős-Faber-Lovas

La conjetura de Erdős-Faber-Lovas es un problema de coloración de gráficos que lleva el nombre de Pal Erdős , Vance Faber y Laszlo Lovas , quienes lo formularon en 1972 [1] . La hipótesis dice:

Si k grafos completos , cada uno con exactamente k vértices, tienen la propiedad de que cualquier par de grafos completos tienen como máximo un vértice común, entonces la unión de los gráficos puede colorearse con k  colores.

En 2021, se publicó una preimpresión con una prueba de la conjetura para k grande [2] .

Formulaciones equivalentes

Addad y Tardif [3] presentaron un problema con la historia de la creación de un comité: imaginemos que la facultad de una universidad tiene k comités, cada uno con k miembros, y todos los comités comparten la misma sala con k asientos. Suponga que hay como máximo una persona en cualquiera de los dos comités. ¿Es posible asignar un presidente a cada miembro del comité de tal manera que cada miembro se siente en el mismo presidente en todos los comités? En este modelo de tarea, los miembros del comité 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.

Una hipergrafía lineal (también conocida como espacio parcialmente lineal ) es una hipergrafía que tiene la propiedad de que dos hiperaristas cualesquiera tienen como máximo un vértice. Se dice que una hipergrafía es homogénea si todas sus hiperaristas tienen el mismo número de vértices constituyentes. En la conjetura de Erdős-Faber-Lovas, n camarillas de tamaño n se pueden interpretar como hiperbordes de una hipergrafía de n líneas homogéneas que tiene los mismos vértices que el gráfico subyacente. En este lenguaje, la conjetura de Erdős-Faber-Lovas establece que si cualquier línea n -homogénea hipergrafía con n hiperaristas, es posible colorear los vértices en n colores de tal manera que cada hiperarista tenga un vértice de cada color [4] .

Una hipergrafía simple es una hipergrafía en la que como máximo una arista conecta cualquier par de vértices y no hay hiperaristas de tamaño uno. En la formulación de la conjetura de Erdős-Faber-Lovas en el lenguaje de la coloración de gráficos, uno puede eliminar fácilmente los vértices que pertenecen a una sola camarilla, ya que su coloración no causa dificultades. Una vez hecho esto, una hipergrafía que tiene cliques como vértices y vértices de gráficos como hiperaristas es una hipergrafía simple. La coloración de hipergrafía dual a vértice es una coloración de borde . Así, la conjetura de Erdős-Faber-Lovas es equivalente a la afirmación de que cualquier hipergrafía simple con n vértices tiene un índice cromático (número de colores colorantes) que no excede n [5] .

El gráfico de la conjetura de Erdős-Faber-Lovas se puede representar como un gráfico de intersecciones de conjuntos: cada vértice del gráfico corresponde a un conjunto de camarillas que contienen un vértice, y dos vértices cualesquiera están conectados por una arista si sus conjuntos correspondientes tienen una intersección no vacía. Usando esta descripción del gráfico, la hipótesis se puede establecer de la siguiente manera: si una determinada familia tiene un total de n elementos y dos conjuntos cualesquiera en la intersección tienen como máximo un elemento, el gráfico de intersección de estos conjuntos se puede colorear en n colores [6] .

El número de intersección del grafo G es igual al número mínimo de elementos de la familia de conjuntos cuyo grafo de intersección coincide con G , o, de manera equivalente, el número mínimo de vértices de hipergrafía cuyo grafo lineal coincide con G . Klein y Margraf [7] definen de manera similar el número de intersección lineal de un gráfico como el número mínimo de vértices en un hipergráfico lineal cuyo gráfico lineal coincide con G . Como señalan, la conjetura de Erodes-Faber Lovas equivale a decir que el número cromático de cualquier gráfico no excede su número de intersección lineal.

Haddad y Tardif [3] dan una formulación diferente, pero aún equivalente, en términos de la teoría del clon .

Historial y resultados parciales

Pal Erdős , Vance Faber y Laszlo Lovas formularon la conjetura en 1972 [1] . Pal Erdős inicialmente ofreció $50 para probar la hipótesis y luego aumentó la recompensa a $500 [1] [8] .

Chiang y Lawler [9] probaron que el número cromático del gráfico en la conjetura no excede 3 k / 2 − 2 , y Kahn [10] mejoró este valor a k + o ( k ) .

Tareas relacionadas

También es interesante considerar el número cromático de grafos formados por la unión de k cliques con k vértices en cada uno sin limitar el tamaño de la intersección de pares de cliques. En este caso, el número cromático de su unión no excede y algunas gráficas así formadas requieren exactamente este número de colores [11] [12] .

Se sabe que la versión de la conjetura que usa el número cromático fraccionario en lugar del número cromático es correcta. Es decir, si el grafo G está formado por la unión de k k -camarillas que se cortan por pares en no más de dos vértices, el grafo G puede colorearse en k -colores [13] .

En el caso de la coloración de los bordes de hipergrafías simples, Hindman [6] define el número L para una hipergrafía simple como el número de vértices de hipergrafía que pertenecen a un hiperarista con tres o más vértices. Demostró que para cualquier valor fijo de L , verificar que una conjetura es verdadera para todos los gráficos simples con , requiere una cantidad finita de cálculos. Basado en esta idea, demostró que la conjetura es verdadera para todas las hipergrafías simples con . En la formulación de la coloración de grafos formados por la unión de cliques, el resultado de Hindman muestra que la conjetura es verdadera si no más de diez cliques contienen vértices pertenecientes a tres o más cliques. En particular, esto es cierto para .

Véase también

Notas

  1. ↑ 1 2 3 Erdős, 1981 .
  2. ↑ Kelsey Houston-Edwards. Los matemáticos resuelven la conjetura  de coloración de Erdő . Cuanta (5 de abril de 2021). Consultado el 5 de abril de 2021. Archivado desde el original el 5 de abril de 2021.
  3. ↑ 1 2 Haddad, Tardif, 2004 .
  4. ↑ Romero, Sánchez Arroyo, 2007 .
  5. ↑ Chiang, Lawler, 1988 . Hindman (( Hindman 1981 )) describe el problema equivalente en términos de un sistema de conjuntos en lugar de hipergrafías.
  6. ↑ 12 Hindman , 1981 .
  7. ↑ Klein, Margraf, 2003 .
  8. ↑ Chung, Graham, 1998 .
  9. ↑ Chiang, Lawler, 1988 .
  10. ↑ Khan, 1992 .
  11. ↑ Erdős, 1991 .
  12. ↑ Horak, Tuza, 1990 .
  13. ↑ Kahn, Seymour, 1992 .

Literatura