La conjetura de Sumner

Problema no resuelto en matemáticas :

¿Cada torneo de vértices contiene como subgrafo cada árbol orientado a vértices? ${\displaystyle (2n-2)}$ ${\displaystyle n}$

(más problemas sin resolver en matemáticas)

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

La conjetura de Sumner (también llamada conjetura del torneo universal de Sumner ) establece que cada orientación de cada árbol de vértice es un subgrafo de cada torneo de vértice. ^[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 poliárboles . La conjetura fue probada con creces por Daniela Kühn , Richard Mycroft y Deryk Osthus . ^[2] ${\displaystyle n}$ ${\displaystyle (2n-2)}$ ${\displaystyle n}$

Ejemplos

Sea poliárbol una estrella , en la que todos los bordes están orientados hacia afuera desde el vértice central hasta las hojas. Entonces, no se puede incrustar en el torneo formado a partir de los vértices de un -gón 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 igual a , mientras que el vértice central tiene un grado de salida mayor . ^[3] Por lo tanto, si es cierta, la conjetura de Sumner daría el mejor tamaño posible de un gráfico universal para poliárboles. ${\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 puede usarse 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}$

Resultados parciales

Se han demostrado los siguientes resultados parciales sobre la conjetura.

• Existe una función con tasa de crecimiento asintótica con la propiedad de que cada poliárbol de vértice se puede incrustar como un subgrafo de cada torneo de vértice. Además y más explícitamente, . ^[4] ${\displaystyle f(n)}$ ${\displaystyle f(n)=2n+o(n)}$ ${\displaystyle n}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)\leq 3n-3}$
• Existe una función tal que los torneos en los vértices son universales para poliárboles con hojas. ^[5] ${\displaystyle g(k)}$ ${\displaystyle n+g(k)}$ ${\displaystyle k}$
• Existe una función tal que cada poliárbol de vértices con grado máximo forma como máximo un subgrafo de cada torneo con vértices. Cuando es una constante fija, la tasa de crecimiento asintótica de es . ^[6] ${\displaystyle h(n,\Delta )}$ ${\displaystyle n}$ ${\displaystyle \Delta }$ ${\displaystyle h(n,\Delta )}$ ${\displaystyle \Delta }$ ${\displaystyle h(n,\Delta )}$ ${\displaystyle n+o(n)}$
• Cada torneo "casi regular" en los vértices contiene cada poliárbol de vértices. ^[7] ${\displaystyle 2n-2}$ ${\displaystyle n}$
• Cada orientación de un árbol de oruga de vértice con un diámetro máximo de cuatro se puede incrustar como un subgrafo de cada torneo de vértice. ^[7] ${\displaystyle n}$ ${\displaystyle (2n-2)}$
• Cada torneo de vértice contiene como subgrafo cada arborescencia de vértice . ^[8] ${\displaystyle (2n-2)}$ ${\displaystyle n}$

Conjeturas relacionadas

Rosenfeld (1972) conjeturó que cada orientación de un gráfico de ruta de vértice (con ) puede incrustarse como un subgrafo en cada torneo de vértice. ^[7] Después de resultados parciales de Thomason (1986), esto fue demostrado 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, de que cada torneo en los vértices contiene como subgrafo cada poliárbol con como máximo hojas. Mycroft y Naia (2018) han confirmado esto para casi todos los árboles. ${\displaystyle n+k-1}$ ${\displaystyle k}$

Burr (1980) conjeturó que, siempre que un gráfico requiere o más colores en una coloración de , entonces cada orientación de contiene todas las orientaciones de un árbol de vértices. Debido a que los gráficos completos requieren un color diferente para cada vértice, la conjetura de Sumner se derivaría inmediatamente de la conjetura de Burr. ^[10] Como demostró Burr, las orientaciones de los gráficos cuyo número cromático crece cuadráticamente en función de son universales para los poliárboles. ${\displaystyle G}$ ${\displaystyle 2n-2}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle n}$

Notas

1. Kühn, Mycroft y Osthus (2011a). Sin embargo, las primeras citas publicadas dadas por Kühn et al. son de Reid y Wormald (1983) y Wormald (1983). Wormald (1983) cita la conjetura como una comunicación privada sin fecha de Sumner.
2. Kühn, Mycroft y Osthus (2011b).
3. Este ejemplo es de Kühn, Mycroft & Osthus (2011a).
4. Kühn, Mycroft y Osthus (2011a) y El Sahili (2004). Para límites anteriores más débiles de , véanse Chung (1981), Wormald (1983), Häggkvist & Thomason (1991), Havet & Thomassé (2000b) y Havet (2002). ${\displaystyle f(n)}$
5. Häggkvist y Thomason (1991); Havet y Thomassé (2000a); Havet (2002).
6. Kühn, Mycroft y Osthus (2011a).
7. Reid y Wormald (1983).
8. Havet y Thomassé (2000b).
9. En Havet (2002), pero acreditado conjuntamente a Thomassé en ese artículo.
10. Ésta es una versión corregida de la conjetura de Burr de Wormald (1983).

Referencias

• Burr, Stefan A. (1980), "Subárboles de gráficos dirigidos e hipergráficos", Actas de la Undécima Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Florida Atlantic Univ., Boca Raton, Florida, 1980), vol. I , Congreso Numerantium, vol. 28, págs. 227–239, SEÑOR  0608430.
• Chung, FRK (1981), Una nota sobre los subárboles en los torneos , Memorando interno, Bell Laboratories. Como lo cita Wormald (1983).
• El Sahili, A. (2004), "Árboles en torneos", Journal of Combinatorial Theory , Serie B, 92 (1): 183–187, doi : 10.1016/j.jctb.2004.04.002 , MR  2078502.
• Häggkvist, Roland; Thomason, Andrew (1991), "Árboles en torneos", Combinatorica , 11 (2): 123–130, doi :10.1007/BF01206356, MR  1136161.
• Havet, Frédéric (2002), "Árboles en torneos", Matemáticas discretas , 243 (1–3): 121–134, doi :10.1016/S0012-365X(00)00463-5, MR  1874730.
• Havet, Federico; Thomassé, Stéphan (2000a), "Rutas hamiltonianas orientadas en torneos: una prueba de la conjetura de Rosenfeld", Journal of Combinatorial Theory , Serie B, 78 (2): 243–273, doi : 10.1006/jctb.1999.1945 , MR  1750898.
• Havet, Federico; Thomassé, Stéphan (2000b), "Órdenes medianos de torneos: una herramienta para el segundo problema de vecindad y la conjetura de Sumner", Journal of Graph Theory , 35 (4): 244–256, doi :10.1002/1097-0118(200012)35 :4<244::AID-JGT2>3.0.CO;2-H, SEÑOR  1791347.
• Kuhn, Daniela ; Mycroft, Richard; Osthus, Deryk (2011a), "Una versión aproximada de la conjetura del torneo universal de Sumner", Journal of Combinatorial Theory , Serie B, 101 (6): 415–447, arXiv : 1010.4429 , doi :10.1016/j.jctb.2010.12.006 , SEÑOR  2832810, Zbl  1234.05115.
• Kuhn, Daniela ; Mycroft, Richard; Osthus, Deryk (2011b), "Una prueba de la conjetura del torneo universal de Sumner para torneos grandes", Actas de la Sociedad Matemática de Londres , Tercera Serie, 102 (4): 731–766, arXiv : 1010.4430 , doi :10.1112/plms/pdq035 , SEÑOR  2793448, Zbl  1218.05034.
• Naia, Tássio (2018), Grandes estructuras en grafos densos dirigidos (tesis doctoral), Universidad de Birmingham.
• Reid, KB; Wormald, NC (1983), "Incrustación de n árboles orientados en torneos", Studia Scientiarum Mathematicarum Hungarica , 18 (2–4): 377–387, MR  0787942.
• Rosenfeld, M. (1972), "Caminos hamiltonianos antidirigidos en torneos", Journal of Combinatorial Theory , Serie B, 12 : 93–99, doi :10.1016/0095-8956(72)90035-4, MR  0285452.
• Thomason, Andrew (1986), "Rutas y ciclos en torneos", Transactions of the American Mathematical Society , 296 (1): 167–180, doi : 10.2307/2000567 , JSTOR  2000567, MR  0837805.
• Wormald, Nicholas C. (1983), "Subárboles de grandes torneos", Matemáticas combinatorias, X (Adelaide, 1982) , Lecture Notes in Math., vol. 1036, Berlín: Springer, págs. 417–419, doi :10.1007/BFb0071535, ISBN 978-3-540-12708-6, señor  0731598.

enlaces externos

• Conjetura del torneo universal de Sumner (1971), DB West, actualizado en julio de 2008.