Sumners gissning

Olöst problem i matematik :

Innehåller varje $(2n-2)$ -vertexturnering som en subgraf varje $n$ -vertexorienterat träd?

En turnering med 6 vertex och kopior av varje träd med 4 vertex i den.

Sumners gissning ( även kallad Sumners universella turneringsförmodan ) säger att varje orientering av varje $n$ -vertexträd är en subgraf av varje $(2n-2)$ -vertexturnering. David Sumner , en grafteoretiker vid University of South Carolina , antog 1971 att turneringar är universella grafer för polyträd . Gissningen bevisades för alla stora $n$ av Daniela Kühn , Richard Mycroft och Deryk Osthus .

Exempel

Låt polyträdet $P$ vara en stjärna ${\displaystyle K_{1,n-1}} ,$ där alla kanter är orienterade utåt från mittpunkten till bladen. Då $P$ inte bäddas in i turneringen som bildas av hörnen på en vanlig $2n-3$ -gon genom att rikta varje kant medurs runt polygonen. För i den här turneringen har varje vertex indegree och outdegree lika med $n-2$ , medan den centrala vertexen i $P$ har större outdegree $n-1$ . Således, om det är sant, skulle Sumners gissning ge den bästa möjliga storleken på en universell graf för polyträd.

Men i varje turnering med $2n-2$ hörn är den genomsnittliga utgraden ${\displaystyle n-{\frac {3}{2}}} ,$ och den maximala utgraden är en heltal större än eller lika med genomsnittet. Därför finns det en vertex av utgrad ${\displaystyle \left\lceil n-{\frac {3}{2}}\right\rceil =n-1} ,$ som kan vara används som det centrala hörnet för en kopia av $P$ .

Delvis resultat

Följande delresultat på gissningarna har bevisats.

Det finns en funktion $f(n)$ med asymptotisk tillväxthastighet $f(n)=2n+o(n)$ med egenskapen att varje $n$ -vertex polyträd kan bäddas in som en subgraf för varje $f(n)$ -vertexturnering. Dessutom och mer explicit, $f(n)\leq 3n-3$ .
Det finns en funktion $g(k)$ så att turneringar på $n+g(k)$ hörn är universella för polyträd med $k$ blad.
Det finns en funktion $h(n,\Delta )$ så att varje $n$ -vertex polyträd med maximal grad $\Delta$ bildar en subgraf av varje turnering med $h(n,\Delta )$ hörn. När ${\displaystyle \Delta } är en fast$ $n+o(n) )$ är den asymptotiska tillväxthastigheten för $h(n,\Delta )$ .
Varje "nära-vanlig" turnering på $2n-2$ hörn innehåller varje $n$ -vertex polyträd.
Varje orientering av ett $n$ -vertex larvträd med diameter som högst fyra kan bäddas in som en subgraf för varje ( $\displaystyle (2n-2)}$ -vertexturnering.
Varje $(2n-2)$ -vertexturnering innehåller som en subgraf var $n$ -vertex arborescence .

Relaterade gissningar

Rosenfeld (1972) antog att varje orientering av en $n$ -vertex -banagraf (med $n\geq 8$ ) kan bäddas in som en subgraf i varje $n$ -vertex turnering. Efter partiella resultat av Thomason (1986) bevisades detta av Havet & Thomassé (2000a) .

Havet och Thomassé antog i sin tur en förstärkning av Sumners gissning, att varje turnering på $n+k-1$ hörn innehåller som en subgraf varje polyträd med högst $k$ blad. Detta har bekräftats för nästan varje träd av Mycroft och Naia (2018) .

Burr (1980) förmodade att närhelst en graf $G$ kräver $2n-2$ eller fler färger i en färgning av $G$ , då varje orientering av $G$ innehåller varje orientering av ett $n$ -vertexträd. Eftersom kompletta grafer kräver en annan färg för varje vertex, skulle Sumners gissning följa direkt från Burrs gissning. Som Burr visade är orienteringar av grafer vars kromatiska tal växer kvadratiskt som en funktion av $n$ universella för polyträd.

Anteckningar

Burr, Stefan A. (1980), "Subtrees of directed graphs and hypergraphs", Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1980), Vol. I , Congressus Numerantium, vol. 28, s. 227–239, MR 0608430 .
Chung, FRK (1981), A not on subtrees in tournaments , Internal Memorandum, Bell Laboratories . Som citeras av Wormald (1983) .
El Sahili, A. (2004), "Trees in tournaments", Journal of Combinatorial Theory , Series B, 92 (1): 183–187, doi : 10.1016/j.jctb.2004.04.002 , MR 2078502 .
Häggkvist, Roland; Thomason, Andrew (1991), "Trees in tournaments", Combinatorica , 11 (2): 123–130, doi : 10.1007/BF01206356 , MR 1136161 .
Havet, Frédéric (2002), "Träd i turneringar", Diskret matematik , 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 , Series B, 78 ( 2): 243–273, doi : 10.1006/jctb.1999.1945 0.19457 .
Havet, Frédéric; Thomassé, Stéphan (2000b), "Median orders of tournaments: a tool for the second neighborhood problem and Sumners conjecture", 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), "An approximate version of Sumners universal tournament conjecture", Journal of Combinatorial Theory , Series B, 101 (6): 415–447, arXiv : 1010.4429 , doi : 10.101ctb.j.201ctb.1.201ctb.1.20106. , MR 2832810 , Zbl 1234,05115 .
Kühn, Daniela ; Mycroft, Richard; Osthus, Deryk (2011b), "A proof of Sumner's universal tournament conjecture for large tournaments", Proceedings of the London Mathematical Society , Third Series, 102 (4): 731–766, arXiv : 1010.4430 , doi : 103plms/1031/51/1031/1031 , MR 2793448 , Zbl 1218.05034 .
Naia, Tássio (2018), Stora strukturer i täta riktade grafer , Doktorsavhandling, University of Birmingham .
Reid, KB; Wormald, NC (1983), "Inbäddning av orienterade n -träd i turneringar", Studia Scientiarum Mathematicarum Hungarica , 18 (2–4): 377–387, MR 0787942 .
Rosenfeld, M. (1972), "Antidirected Hamiltonian paths in tournaments", Journal of Combinatorial Theory , Series B, 12 : 93–99, doi : 10.1016/0095-8956(72)90035-4 , MR 0285452 .
Thomason, Andrew (1986), "Paths and cycles in tournaments", Transactions of the American Mathematical Society , 296 (1): 167–180, doi : 10.2307/2000567 , MR 0837805 .
Wormald, Nicholas C. (1983), "Subtrees of large tournaments", Combinatorial mathematics, X (Adelaide, 1982) , Lecture Notes in Math., vol. 1036, Berlin: Springer, s. 417–419, doi : 10.1007/BFb0071535 , MR 0731598 .

externa länkar

Sumner's Universal Tournament Conjecture (1971) , DB West, uppdaterad juli 2008.