Erdős – kamenná věta - Erdős–Stone theorem - Wikipedia

v teorie extrémních grafů, Erdős – kamenná věta je asymptotické zobecnění výsledku Turánova věta omezit počet hran v H-bezplatný graf pro neúplný graf H. Je pojmenován po Paul Erdős a Arthur Stone, který to dokázal v roce 1946,^[1] a byla popsána jako „základní věta teorie extrémních grafů“.^[2]

Extrémní funkce Turánových grafů

Extrémní funkce ex (n; H) je definován jako maximální počet hran v grafu pořadí n neobsahující podgraf izomorfní s H. Turánova věta říká, že ex (n; K._r) = t_r − 1(n), pořadí Turánův graf, a že Turánův graf je jedinečný extremální graf. Věta Erdős – Stone to rozšiřuje na grafy, které neobsahují K._r(t), kompletní r-částový graf s t vrcholy v každé třídě (ekvivalentně) Turánův graf T(rt,r)):

${ displaystyle { mbox {ex}} (n; K_ {r} (t)) = left ({ frac {r-2} {r-1}} + o (1) right) {n vyberte 2}.}$

Extrémní funkce libovolných nebipartitních grafů

Li H je libovolný graf, jehož chromatické číslo je r > 2 tedy H je obsažen v K._r(t) kdykoli t je alespoň tak velká jako největší barevná třída v souboru r-barvení H, ale není obsažen v grafu Turán T(n,r - 1) (protože každý podgraf tohoto Turánova grafu může být obarven r - 1 barvy). Z toho vyplývá, že extremální funkce pro H je přinejmenším stejně velký jako počet hran v T(n,r - 1) a nejvýše se rovná extremální funkci pro K._r(t); to je

${ displaystyle { mbox {ex}} (n; H) = left ({ frac {r-2} {r-1}} + o (1) right) {n zvolte 2}.}$

Pro bipartitní grafy H, nicméně, věta nedává pevnou vazbu na extremální funkci. Je známo, že když H je bipartitní, ex (n; H) = Ó(n²) a u obecných bipartitních grafů je známo ještě málo. Vidět Zarankiewiczův problém pro více informací o extremálních funkcích bipartitních grafů.

Kvantitativní výsledky

Bylo prokázáno několik verzí věty, které přesněji charakterizují vztah n, r, t a Ó(1) období. Definujte notaci^[3] s_{r, ε}(n) (pro 0 <ε <1 / (2 (r - 1))) být největší t takový, že každý graf objednávky n a velikost

${ displaystyle left ({ frac {r-2} {2 (r-1)}} + varepsilon right) n ^ {2}}$

obsahuje a K._r(t).

Erdős a Stone to dokázali

${ displaystyle s_ {r, varepsilon} (n) geq left ( underbrace { log cdots log} _ {r-1} n right) ^ {1/2}}$

pro n dostatečně velký. Správné pořadí s_{r, ε}(n) ve smyslu n byl nalezen Bollobásem a Erdősem:^[4] pro všechny dané r a ε existují konstanty C₁(r, ε) a C₂(r, ε) takové, že C₁(r, ε) logn < s_{r, ε}(n) < C₂(r, ε) logn. Chvátal a Szemerédi^[5] poté určil povahu závislosti na r a ε, až do konstanty:

${ displaystyle { frac {1} {500 log (1 / varepsilon)}} log n$ pro dostatečně velké n.

Poznámky