Conjetura de Sumner

¿Cada torneo -vertex contiene como subgrafo cada árbol orientado -vertex?${\ Displaystyle (2n-2)}$${\ Displaystyle n}$

La conjetura de Sumner (también llamada conjetura de torneo universal de Sumner ) establece que cada orientación de cada árbol -vertex es un subgrafo de cada torneo -vertex. ^[1] David Sumner , un teórico de grafos de la Universidad de Carolina del Sur , conjeturó en 1971 que los torneos son grafos universales para polytrees . La conjetura fue probada a grandes rasgos por Daniela Kühn , Richard Mycroft y Deryk Osthus . ^[2]${\ Displaystyle n}$${\ Displaystyle (2n-2)}$ ${\ Displaystyle n}$

Sea polytree una estrella , en la que todos los bordes están orientados hacia afuera desde el vértice central hacia las hojas. Entonces, no se puede incrustar en el torneo formado a partir de los vértices de un -gon regular dirigiendo cada borde en el sentido de las agujas del reloj alrededor del polígono. Porque, en este torneo, cada vértice tiene un grado de entrada y un grado de salida iguales a , mientras que el vértice central de entrada tiene un grado de salida más grande . ^[3] Por lo tanto, si es cierta, la conjetura de Sumner daría el mejor tamaño posible de un gráfico universal para polytrees.${\ Displaystyle P}$ ${\ Displaystyle K_ {1, n-1}}$${\ Displaystyle P}$${\displaystyle 2n-3}$${\displaystyle n-2}$${\displaystyle P}$${\displaystyle n-1}$

Sin embargo, en cada torneo de vértices, el grado de salida promedio es , y el grado de salida máximo es un número entero mayor o igual que el promedio. Por lo tanto, existe un vértice de grado externo , que se puede utilizar como vértice central para una copia de .${\displaystyle 2n-2}$${\displaystyle n-{\frac {3}{2}}}$${\displaystyle \left\lceil n-{\frac {3}{2}}\right\rceil =n-1}$${\displaystyle P}$

Rosenfeld (1972) conjeturó que cada orientación de un gráfico de trayectoria -vertex (con ) se puede incrustar como un subgrafo en cada torneo -vertex. ^[7] Después de los resultados parciales de Thomason (1986) , esto fue probado por Havet y Thomassé (2000a) .${\displaystyle n}$${\displaystyle n\geq 8}$${\displaystyle n}$

Havet y Thomassé ^[9] a su vez conjeturaron un fortalecimiento de la conjetura de Sumner, que cada torneo en vértices contiene como un subgrafo cada polytree con como máximo hojas. Esto ha sido confirmado para casi todos los árboles por Mycroft y Naia (2018) .${\displaystyle n+k-1}$${\displaystyle k}$

Un torneo de 6 vértices y copias de cada árbol orientado a 4 vértices dentro de él.