La hipótesis de Sumner

Problemas sin resolver en Matemáticas : ¿Algún torneo de vértices contiene algún árbol de vértices dirigido como un subgrafo ?

David Sumner (un teórico de grafos de la Universidad de Carolina del Sur ) conjeturó en 1971 que los torneos son grafos universales para poliárboles (árboles dirigidos). Más precisamente, la conjetura de Sumner (o la conjetura del torneo universal de Sumner ) establece que cualquier orientación de cualquier árbol de vértices es un subgrafo de cualquier torneo de vértices [1] . La hipótesis sigue sin probarse. Kuhn, Mycroft y Ostus [2] hablan de la conjetura como "uno de los problemas de torneos más conocidos".

Ejemplos

Sea un árbol orientado una estrella en la que todos los bordes están orientados desde el centro hacia las hojas. Entonces es imposible encajar en un torneo formado por los vértices de un -gon regular dirigiendo todos los bordes en el sentido de las agujas del reloj alrededor del polígono. Para este torneo, cualquier medio grado de entrada y cualquier medio grado de salida son , mientras que el vértice central tiene un medio grado de salida más grande, . [3] . Por tanto, si la conjetura de Sumner es correcta, da el mejor tamaño posible de un gráfico universal para árboles dirigidos.

Sin embargo, en cualquier torneo con picos, el semigrado de salida promedio es , y el semigrado de salida máximo es un número entero mayor o igual que el valor promedio. Por lo tanto, hay un vértice con salida de semigrado , que se puede utilizar como vértice central para la copia .

Resultados parciales

Se conocen los siguientes resultados parciales.

Hipótesis relacionadas

Rosenfeld [11] conjeturó que cualquier camino dirigido con vértices (para ) puede incrustarse como un subgrafo en cualquier torneo con vértices [9] . Después de los resultados parciales obtenidos por Thomason [12] , Ave y Tomassi [7] demostraron la conjetura .

Ave y Tomassi [13] , a su vez, propusieron la conjetura reforzada de Sumner de que cualquier torneo con vértices contiene como subgrafo cualquier árbol dirigido con un máximo de hojas.

Burr [14] conjeturó que si un gráfico requiere más de un color para colorear el gráfico , entonces cualquier orientación del gráfico contiene cualquier orientación del árbol de vértices. Debido a que los gráficos completos requieren un color diferente para cada vértice, la conjetura de Sumner se sigue inmediatamente de la conjetura de Burr [15] . Como mostró Burr, las orientaciones de gráficos cuyo número cromático crece cuadráticamente son universales para árboles dirigidos.

Notas

  1. ↑ ( Kühn, Mycroft, Osthus 2011a ). La primera cita publicada es de Daniela Kühn et al., de Reid y Wormald (( Reid, Wormald 1983 ), ( Wormald 1983 )). Wormald cita que la hipótesis se escuchó en una conversación privada con Sumner.
  2. ↑ 1 2 Kühn, Mycroft, Osthus, 2011a .
  3. ↑ Este ejemplo está tomado de un artículo de Kühn, Mycroft y Osthus (( Kühn, Mycroft, Osthus 2011a )).
  4. ↑ Kühn, Mycroft, Osthus, 2011b .
  5. ↑ Kühn, Mycroft, Osthus, 2011a ; El Sahilí, 2004 . Se pueden encontrar límites más débiles y anteriores para la función en Chung, 1981 , Wormald, 1983 , Häggkvist, Thomason, 1991 , Havet, Thomassé, 2000b , Havet, 2002 .
  6. ↑ Haggkvist, Thomason, 1991 .
  7. ↑ 1 2 Havet, Thomasse, 2000a .
  8. ↑ Havet, 2002 .
  9. ↑ 1 2 3 Reid, Wormald, 1983 .
  10. ↑ Havet, Thomasse, 2000b .
  11. ↑ Rosenfeld, 1972 .
  12. ↑ Thomason, 1986 .
  13. ↑ En el artículo de Ave (( Havet 2002 )), pero Ave lo atribuye en este artículo a Tomassi.
  14. ↑ Rebabas, 1980 .
  15. ↑ Esta es una versión editada de la conjetura de Burr del artículo de Wormald (( Wormald 1983 )).

Literatura

Enlaces