La conjetura de Sumner

Problema sin resolver en matemáticas

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

Más problemas sin resolver en matemáticas

La conjetura de Sumner (también llamada conjetura del torneo universal de Sumner ) es una conjetura en la teoría extremal de grafos sobre árboles orientados en torneos . Afirma que cada orientación de cada${\displaystyle n}$-El árbol de vértices es un subgrafo de cada${\displaystyle (2n-2)}$Torneo de vértices. ^{[ 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 demostrada para todos los grandes${\displaystyle n}$por Daniela Kühn , Richard Mycroft y Deryk Osthus . ^{[ 2 ]}

Dejemos el árbol poligonal${\displaystyle P}$Sé una estrella${\displaystyle K_{1,n-1}}$, en la que todos los bordes están orientados hacia afuera desde el vértice central hacia las hojas. Entonces,${\displaystyle P}$no puede estar incrustado en el torneo formado a partir de los vértices de un regular${\displaystyle 2n-3}$-gon dirigiendo cada arista en el sentido de las agujas del reloj alrededor del polígono. Porque, en este torneo, cada vértice tiene grado de entrada y grado de salida igual a${\displaystyle n-2}$, mientras que el vértice central en${\displaystyle P}$tiene mayor grado de salida${\displaystyle n-1}$. ^{[ 3 ]} Por lo tanto, si es cierta, la conjetura de Sumner daría el mejor tamaño posible de un grafo universal para poliárboles.

Sin embargo, en cada torneo de${\displaystyle 2n-2}$vértices, el grado de salida promedio es${\displaystyle n-{\frac {3}{2}}}$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 de salida.${\displaystyle \left\lceil n-{\frac {3}{2}}\right\rceil =n-1}$, que puede utilizarse como vértice central para una copia de${\displaystyle P}$.

Se han demostrado los siguientes resultados parciales sobre la conjetura.

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

Rosenfeld (1972) conjeturó que cada orientación de un${\displaystyle n}$-grafo de caminos de vértices (con${\displaystyle n\geq 8}$) puede incrustarse como un subgrafo en cada${\displaystyle n}$-torneo de vértices. ^{[ 7 ]} Después de los resultados parciales de Thomason (1986) , esto fue demostrado por Havet y Thomassé (2000a) .

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

Burr (1980) conjeturó que, siempre que un gráfico${\displaystyle G}$requiere${\displaystyle 2n-2}$o más colores en una coloración de${\displaystyle G}$, entonces cada orientación de${\displaystyle G}$contiene todas las orientaciones de un${\displaystyle n}$-árbol de vértices. Debido a que los grafos 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 grafos cuyo número cromático crece cuadráticamente en función de${\displaystyle n}$son universales para poliárboles.

• Burr, Stefan A. (1980), "Subárboles de grafos dirigidos e hipergrafos", Actas de la Undécima Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Universidad Atlántica de Florida, Boca Ratón, Florida, 1980), Vol. I , Congressus Numerantium, vol.  28, pp. 227–239 , MR 0608430  .
• Chung, FRK (1981), Una nota sobre subárboles en torneos , Memorando interno, Laboratorios Bell. Según lo citado por 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, Frédéric; Thomassé, Stéphan (2000a), "Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture", Journal of Combinatorial Theory , Serie B, 78 (2): 243– 273, doi : 10.1006/jctb.1999.1945 , MR 1750898 .
• Havet, Frédéric; Thomassé, Stéphan (2000b), "Órdenes medianas de torneos: una herramienta para el problema del segundo vecindario 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 , MR 1791347 .
• Kühn, 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 , MR 2832810 , Zbl 1234.05115  .
• Kühn, Daniela ; Mycroft, Richard; Osthus, Deryk (2011b), "Una demostración de la conjetura del torneo universal de Sumner para grandes torneos", Actas de la Sociedad Matemática de Londres , Tercera Serie, 102 (4): 731–766 , arXiv : 1010.4430 , doi : 10.1112/plms/pdq035 , MR 2793448 , Zbl 1218.05034  .
• Naia, Tássio (2018), Estructuras grandes en grafos dirigidos densos (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 antidireccionales en torneos", Journal of Combinatorial Theory , Serie B, 12 : 93–99 , doi : 10.1016/0095-8956(72)90035-4 , MR 0285452 .
• Thomason, Andrew (1986), "Caminos 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 (Adelaida, 1982) , Notas de clase en matemáticas, vol.  1036, Berlín: Springer, pp. 417–419 , doi : 10.1007/BFb0071535 , ISBN  978-3-540-12708-6, MR 0731598 .

• La conjetura del torneo universal de Sumner (1971) , DB West, actualizada en julio de 2008.