Extrémní teorie grafů - Extremal graph theory

Extrémní teorie grafů je pobočkou matematika který studuje, jak globální vlastnosti grafu ovlivňují místní spodní konstrukci.^[1] Zahrnuje obrovské množství výsledků, které popisují, jak jsou určité vlastnosti grafu - počet vrcholy (velikost), počet hrany, hustota hran, chromatické číslo, a obvod například - zaručit existenci určitých místních substruktur.

The Turánův graf T(n,r) je příkladem extrémního grafu. Má maximální možný počet hran pro graf n vrcholy bez (r + 1)-kliky. Tohle je T(13,4).

Jedním z hlavních předmětů studia v této oblasti teorie grafů jsou extrémní grafy, které jsou maximální nebo minimální s ohledem na nějaký globální parametr a takové, které obsahují (nebo neobsahují) místní podstrukturu - například klika nebo zbarvení hran.

Příklady

Extrémní teorie grafů může být motivována otázkami, jako jsou následující:

Otázka 1. Jaký je maximální možný počet hran v grafu ${ displaystyle n}$ vrcholy tak, že neobsahuje cyklus?

Pokud je graf zapnutý ${ displaystyle n}$ vrcholy obsahují alespoň ${ displaystyle n}$ hrany, pak musí také obsahovat cyklus. Navíc jakékoli strom s ${ displaystyle n}$ vrcholy obsahuje ${ displaystyle n-1}$ hrany a neobsahuje cykly; stromy jsou jedinými grafy s ${ displaystyle n-1}$ hrany a žádné cykly. Odpověď na tuto otázku proto zní ${ displaystyle n-1}$ a stromy jsou extrémní grafy.^[2]

Otázka 2. Pokud je graf zapnutý ${ displaystyle n}$ vrcholy neobsahuje žádný trojúhelníkový podgraf, jaký maximální počet hran může mít?

Mantelova věta odpovídá na tuto otázku - maximální počet hran je ${ displaystyle lfloor n ^ {2} / 4 rfloor}$ . Odpovídající extremální graf je a kompletní bipartitní graf na ${ displaystyle ( lceil n / 2 rceil, lfloor n / 2 rfloor)}$ vrcholy, tj. dvě části se liší velikostí maximálně o 1.

Následuje zobecnění otázky 2:

Otázka 3. Nechat ${ displaystyle r}$ být kladné celé číslo. Kolik hran musí být v grafu ${ displaystyle G}$ na ${ displaystyle n}$ vrcholy, aby bylo zajištěno, že bez ohledu na uspořádání okrajů bude klika ${ displaystyle K_ {r}}$ lze najít jako podgraf?

Odpověď na tuto otázku je ${ displaystyle { frac {r-2} {r-1}} cdot { frac {n ^ {2}} {2}} + 1}$ a odpovídá na ni Turánova věta. Proto pokud graf ${ displaystyle G}$ na ${ displaystyle n}$ vrcholy je ${ displaystyle K_ {r}}$ - zdarma, může mít nanejvýš ${ displaystyle left lfloor { frac {(r-2) n ^ {2}} {2 (r-1)}} right rfloor = left lfloor left (1 - { frac {1 } {r-1}} right) { frac {n ^ {2}} {2}} right rfloor}$

mnoho hran; odpovídající extrémní graf s tolika hranami je Turánův graf, zobrazené na obrázku výše. To je dokončit připojení z ${ displaystyle r-1}$ nezávislé sady (s co nejmenšími velikostmi - takový oddíl se nazývá spravedlivý).

Následující otázka je zevšeobecněním otázky 3, kde je celý graf ${ displaystyle K_ {r}}$ je nahrazen libovolným grafem ${ displaystyle H}$ :

Otázka 4. Nechat ${ displaystyle r}$ být kladné celé číslo a ${ displaystyle H}$ jakýkoli graf na ${ displaystyle r}$ vrcholy. Kolik hran musí být v grafu ${ displaystyle G}$ na ${ displaystyle n}$ vrcholy, aby bylo zajištěno, že bez ohledu na to, jak jsou hrany uspořádány, ${ displaystyle H}$ je podgrafem ${ displaystyle G}$ ?

Na tuto otázku většinou odpovídá Erdős – kamenná věta. Hlavní výhrada je pro bipartitu ${ displaystyle H}$ věta neurčuje uspokojivě asymptotické chování počtu krajních hran. U mnoha konkrétních (tříd) bipartitních grafů zůstává stanovení asymptotického chování otevřeným problémem.

Několik základních výsledků v teorii extrémních grafů odpovídá na otázky, které se řídí touto obecnou formulací:

Otázka 5. Vzhledem k tomu, vlastnost grafu ${ displaystyle P}$ , parametr ${ displaystyle u = u (G)}$ popisující graf a sadu grafů ${ displaystyle { mathcal {S}}}$ , chceme najít minimální možnou hodnotu ${ displaystyle u_ {0}}$ tak, že každý graf ${ displaystyle G v { mathcal {S}}}$ s ${ displaystyle u (G) geq u_ {0}}$ má majetek ${ displaystyle P}$ . Možná bychom chtěli popsat grafy ${ displaystyle G}$ které jsou extrémní ve smyslu mít ${ displaystyle u (G)}$ blízko k ${ displaystyle u_ {0}}$ ale které nevyhovují majetku ${ displaystyle P}$ .

Například v otázce 1 ${ displaystyle { mathcal {S}}}$ je sada ${ displaystyle n}$ -vertexové grafy, ${ displaystyle P}$ je vlastnost obsahující cyklus, ${ displaystyle u}$ je počet hran a mezní hodnota je ${ displaystyle u_ {0} = n}$ . Extrémními příklady jsou stromy.

Dějiny

Extrémní teorie grafů, v nejpřísnějším smyslu, je odvětví teorie grafů vyvinuté a milované Maďary.

Bollobás (2004)

Mantelova věta (1907) a Turánova věta (1941) byly jedny z prvních milníků ve studiu teorie extrémních grafů.^[3] Zejména Turánova věta se později stala motivací pro hledání výsledků, jako je Erdős-Stone-Simonovitsova věta (1946).^[1] Tento výsledek je překvapivý, protože spojuje chromatické číslo s maximálním počtem hran v ${ displaystyle H}$ -bezplatný graf. Alternativní důkaz Erdős-Stone-Simonovits byl uveden v roce 1975 a využil Szemerédiho pravidelnost lemma, základní technika při řešení problémů teorie extrémních grafů.^[3]

Výsledky hustoty a nerovnosti

Globálním parametrem, který hraje důležitou roli v extremální teorii grafů, je hustota podgrafu; pro graf ${ displaystyle G = (V, E)}$ a graf ${ displaystyle H}$ , hustota jeho podgrafu je definována jako

${ displaystyle t (H, G) = ({ text {počet kopií}} H { text {in}} G) / { binom {n} {| V (H) |}}}$ .

Hustota hrany je zejména hustota podgrafu pro ${ displaystyle H = K_ {2}}$ :

${ displaystyle t (K_ {2}, G) = | E | / { binom {| V |} {2}}}$

Výše uvedené věty lze přeformulovat z hlediska hustoty hran. Například, Mantelova věta znamená, že okrajová hustota podgrafu bez trojúhelníků je maximálně ${ displaystyle 1/2}$ . Turánova věta naznačuje, že okrajová hustota ${ displaystyle K_ {r}}$ - bezplatný graf je maximálně ${ displaystyle (r-2 / r-1) + o (1)}$ .

Navíc to uvádí Erdős-Stone-Simonovitsova věta

${ displaystyle { mbox {ex}} (n; H) = left (1 - { frac {1} { chi (H) -1}} + o (1) right) {n zvolit 2 },}$

kde ${ displaystyle ex (n; H)}$ je maximální počet hran, které ${ displaystyle H}$ - graf zdarma ${ displaystyle n}$ vrcholy mohou mít, a ${ displaystyle chi (H)}$ je chromatické číslo z ${ displaystyle H}$ . Interpretace tohoto výsledku spočívá v tom, že okrajová hustota an ${ displaystyle H}$ -volný graf je asymptoticky ${ displaystyle 1- (1 / ( chi (H) -1))}$ .

Další výsledek od Erdős, Rényi a Sós (1966) ukazuje tento graf ${ displaystyle n}$ vrcholy neobsahující ${ displaystyle C_ {4}}$ jako podgraf má maximálně následující počet hran.

${ displaystyle left ({ frac {1} {2}} + o (1) right) n ^ {3/2}}$

Podmínky minimálního stupně

Výše uvedené věty dávají podmínky pro to, aby se malý objekt objevil v (možná) velmi velkém grafu. Další směr v teorii extrémních grafů hledá podmínky, které zaručují existenci struktury, která pokrývá každý vrchol. Všimněte si, že je to dokonce možné pro graf s ${ displaystyle n}$ vrcholy a ${ displaystyle { binom {n-1} {2}}}$ hrany mají izolovaný vrchol, přestože v grafu jsou téměř všechny možné hrany. Podmínky počítání hran neposkytují žádné informace o tom, jak jsou okraje v grafu rozloženy, což vede k výsledkům, které nacházejí ohraničené struktury pouze ve velmi velkých grafech. To poskytuje motivaci pro zvážení parametru minimálního stupně, který je definován jako

{ displaystyle delta (G) = min _ {v v G} d (v).}

Velký minimální stupeň vylučuje možnost mít nějaké „patologické“ vrcholy; pokud je minimální stupeň grafu G je například 1, pak nemohou existovat žádné izolované vrcholy (i když G může mít velmi málo hran).

Výsledek extrémní teorie grafů související s parametrem minimálního stupně je Diracova věta, který uvádí, že každý graf ${ displaystyle G}$ s ${ displaystyle n}$ vrcholy a alespoň minimální stupeň ${ displaystyle n / 2}$ obsahuje a Hamiltonův cyklus.

Další věta^[3] říká, že pokud je minimální stupeň grafu ${ displaystyle G}$ je ${ displaystyle delta geq 3}$ a obvod je ${ displaystyle g geq 3}$ , pak je počet vrcholů v grafu alespoň

${ displaystyle n_ {0} ( delta, g) = { start {případů} 1 + { frac { delta} { delta -2}} [( delta -1) ^ {(g-1) / 2} -1] & { text {if}} g { text {je zvláštní}} { frac {2} { delta -2}} [( delta -1) ^ {g / 2 } -1] & { text {if}} g { text {is even}} end {cases}}}$ .

Některé otevřené otázky

I když bylo v oblasti teorie extrémních grafů provedeno mnoho důležitých pozorování, několik otázek stále zůstává nezodpovězeno. Například, Zarankiewiczův problém zeptá se, jaký je maximální možný počet hran v a bipartitní graf na ${ displaystyle n}$ vrcholy, které nemají kompletní bipartita podgrafy velikosti ${ displaystyle m}$ .

Další důležitou domněnku v teorii extrémních grafů formuloval Sidorenko v roce 1993. Předpokládá se, že pokud ${ displaystyle H}$ je bipartitní graf, pak jeho grafon hustota (zobecněný pojem hustoty grafu) ${ displaystyle t (H, W)}$ je alespoň ${ displaystyle t (K_ {2}, W) ^ {| v (H) |}}$ .

Viz také

Poznámky

^ ^A ^b Diestel 2010
^ Bollobás 2004, str. 9
^ ^A ^b ^C Bollobás 1998, str. 104

Reference

Bollobás, Béla (2004), Extrémní teorie grafů, New York: Dover Publications, ISBN 978-0-486-43596-1.
Bollobás, Béla (1998), Teorie moderních grafů, Berlín, New York: Springer-Verlag, str. 103–144, ISBN 978-0-387-98491-9.
Diestel, Reinhard (2010), Teorie grafů (4. vyd.), Berlín, New York: Springer-Verlag, s. 169–198, ISBN 978-3-642-14278-9, archivovány z originál dne 2017-05-28, vyvoláno 2013-11-18.
M. Simonovits, Prezentace z přednášek letní školy Chorin, 2006. [1]

[:0-1] A ^b Diestel 2010

[2] Bollobás 2004, str. 9

[b104-3] A ^b ^C Bollobás 1998, str. 104

[1]

[2]

[3]