Sumners dohad - Sumners conjecture - Wikipedia

Nevyřešený problém v matematice: Má každý ${ displaystyle (2n-2)}$-vertex turnaj obsahuje jako podgraf každý ${ displaystyle n}$-vertexově orientovaný strom? (více nevyřešených úloh z matematiky)

Turnaj o 6 vrcholech a kopie všech stromů orientovaných na 4 vrcholy.

Sumnerova domněnka (také zvaný Sumnerova univerzální domněnka o turnaji) uvádí, že každý orientace ze všech ${ displaystyle n}$-vrchol strom je podgraf ze všech ${ displaystyle (2n-2)}$-vrcholový turnaj.^[1] David Sumner, a teoretik grafů na University of South Carolina, domnělý v roce 1971 to turnaje jsou univerzální grafy pro polytrees. Domněnka byla prokázána pro všechny velké ${ displaystyle n}$ podle Daniela Kühn, Richard Mycroft a Deryk Osthus.^[2]

Příklady

Nechte polytree ${ displaystyle P}$ být hvězda ${ displaystyle K_ {1, n-1}}$, ve kterém jsou všechny hrany orientovány ven z centrálního vrcholu na listy. Pak, ${ displaystyle P}$ nelze vložit do turnaje vytvořeného z vrcholů obyčejného hráče ${ displaystyle 2n-3}$-gon nasměrováním každé hrany ve směru hodinových ručiček kolem mnohoúhelníku. Protože na tomto turnaji má každý vrchol shodný indegree a outdegree ${ displaystyle n-2}$, zatímco centrální vrchol v ${ displaystyle P}$ má větší zastoupení ${ displaystyle n-1}$.^[3] Pokud by to tedy byla pravda, Sumnerova domněnka by poskytla nejlepší možnou velikost univerzálního grafu pro polytromy.

Na každém turnaji v ${ displaystyle 2n-2}$ vrcholy, průměrný outgree je ${ displaystyle n - { frac {3} {2}}}$, a maximální počet stupňů je celé číslo větší nebo rovno průměru. Proto existuje vrchol outgree ${ displaystyle left lceil n - { frac {3} {2}} right rceil = n-1}$, který lze použít jako centrální vrchol pro kopii ${ displaystyle P}$.

Částečné výsledky

Následující dílčí výsledky dohadu byly prokázány.

• Existuje funkce ${ displaystyle f (n)}$ s asymptotickým růstem ${ displaystyle f (n) = 2n + o (n)}$ s majetkem, který každý ${ displaystyle n}$-vrcholový polystrom může být vložen jako podgraf každého ${ displaystyle f (n)}$-vrcholový turnaj. Navíc a přesněji ${ displaystyle f (n) leq 3n-3}$.^[4]
• Existuje funkce ${ displaystyle g (k)}$ takové turnaje ${ displaystyle n + g (k)}$ vrcholy jsou univerzální pro polytromy s ${ displaystyle k}$ listy.^[5]
• Existuje funkce ${ displaystyle h (n, Delta)}$ takové, že každý ${ displaystyle n}$-vrcholový polystrom s maximálním stupněm ${ displaystyle Delta}$ tvoří podgraf každého turnaje s ${ displaystyle h (n, Delta)}$ vrcholy. Když ${ displaystyle Delta}$ je pevná konstanta, rychlost asymptotického růstu ${ displaystyle h (n, Delta)}$ je ${ displaystyle n + o (n)}$.^[6]
• Každý „téměř pravidelný“ turnaj ${ displaystyle 2n-2}$ vrcholy obsahuje všechny ${ displaystyle n}$-vrcholový polystrom.^[7]
• Každá orientace ${ displaystyle n}$-vrchol housenka s průměr maximálně čtyři lze vložit jako podgraf každého ${ displaystyle (2n-2)}$-vrcholový turnaj.^[7]
• Každý ${ displaystyle (2n-2)}$-vertexový turnaj obsahuje jako podgraf každý ${ displaystyle n}$-vrchol stromovost.^[8]

Související dohady

Rosenfeld (1972) domníval se, že každá orientace ${ displaystyle n}$-vrchol graf cesty (s ${ displaystyle n geq 8}$) lze vložit jako podgraf do každého ${ displaystyle n}$-vrcholový turnaj.^[7] Po dílčích výsledcích do Thomason (1986), to bylo prokázáno Havet & Thomassé (2000a).

Havet a Thomassé^[9] zase předpokládal posílení Sumnerova domněnky, že každý turnaj dál ${ displaystyle n + k-1}$ vertices obsahuje jako podgraf maximálně každý polytree ${ displaystyle k}$ listy. To téměř u každého stromu potvrdily společnosti Mycroft a Naia (2018).

Burr (1980) domníval se, že kdykoli graf ${ displaystyle G}$ vyžaduje ${ displaystyle 2n-2}$ nebo více barev v a zbarvení z ${ displaystyle G}$, pak každá orientace ${ displaystyle G}$ obsahuje každou orientaci souboru ${ displaystyle n}$-vrcholový strom. Protože úplné grafy vyžadují pro každý vrchol jinou barvu, Sumnerova domněnka by okamžitě následovala od Burrovy domněnky.^[10] Jak ukázal Burr, orientace grafů, jejichž chromatický počet roste kvadraticky jako funkce ${ displaystyle n}$ jsou univerzální pro mnohostromy.

Poznámky

Reference

• Burr, Stefan A. (1980), „podstromy řízených grafů a hypergrafů“, Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1980), sv. Já, Congressus Numerantium, 28, str. 227–239, PAN  0608430.
• Chung, FRK (1981), Poznámka k podstromům na turnajích, Interní memorandum, Bell Laboratories. Jak uvádí Wormald (1983).
• El Sahili, A. (2004), „Stromy na turnajích“, Journal of Combinatorial Theory, Řada B, 92 (1): 183–187, doi:10.1016 / j.jctb.2004.04.002, PAN  2078502.
• Häggkvist, Roland; Thomason, Andrew (1991), „Stromy na turnajích“, Combinatorica, 11 (2): 123–130, doi:10.1007 / BF01206356, PAN  1136161.
• Havet, Frédéric (2002), „Stromy na turnajích“, Diskrétní matematika, 243 (1–3): 121–134, doi:10.1016 / S0012-365X (00) 00463-5, PAN  1874730.
• Havet, Frédéric; Thomassé, Stéphan (2000a), „Orientované hamiltonovské cesty v turnajích: důkaz Rosenfeldovy domněnky“, Journal of Combinatorial Theory, Řada B, 78 (2): 243–273, doi:10.1006 / jctb.1999.1945, PAN  1750898.
• Havet, Frédéric; Thomassé, Stéphan (2000b), „Střední pořadí turnajů: nástroj pro druhý problém sousedství a Sumnerova domněnka“, Journal of Graph Theory, 35 (4): 244–256, doi:10.1002 / 1097-0118 (200012) 35: 4 <244 :: AID-JGT2> 3.0.CO; 2-H, PAN  1791347.
• Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011a), „Přibližná verze Sumnerovy univerzální turnajové domněnky“, Journal of Combinatorial Theory, Řada B, 101 (6): 415–447, arXiv:1010.4429, doi:10.1016 / j.jctb.2010.12.006, PAN  2832810, Zbl  1234.05115.
• Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011b), „Důkaz o Sumnerově univerzální domněnce o turnaji pro velké turnaje“, Proceedings of the London Mathematical SocietyTřetí série, 102 (4): 731–766, arXiv:1010.4430, doi:10.1112 / plms / pdq035, PAN  2793448, Zbl  1218.05034.
• Naia, Tássio (2018), Velké struktury v hustých orientovaných grafech „Disertační práce, University of Birmingham.
• Reid, K. B .; Wormald, N. C. (1983), „Vkládání orientováno n-stromy na turnajích ", Studia Scientiarum Mathematicarum Hungarica, 18 (2–4): 377–387, PAN  0787942.
• Rosenfeld, M. (1972), „Antidirected Hamiltonian cesty v turnajích“, Journal of Combinatorial Theory, Řada B, 12: 93–99, doi:10.1016/0095-8956(72)90035-4, PAN  0285452.
• Thomason, Andrew (1986), „Cesty a cykly v turnajích“, Transakce Americké matematické společnosti, 296 (1): 167–180, doi:10.2307/2000567, PAN  0837805.
• Wormald, Nicholas C. (1983), „podstromy velkých turnajů“, Kombinatorická matematika, X (Adelaide, 1982), Poznámky k přednášce v matematice., 1036, Berlín: Springer, s. 417–419, doi:10.1007 / BFb0071535, PAN  0731598.

externí odkazy

• Sumner's Universal Tournament Conjecture (1971), D. B. West, aktualizováno v červenci 2008.