Twierdzenie Erdősa-Stone'a

W teorii grafów ekstremalnych twierdzenie Erdősa – Stone'a jest asymptotycznym wynikiem uogólniającym twierdzenie Turána w celu ograniczenia liczby krawędzi w grafie wolnym od H dla grafu niepełnego H . Zostało nazwane na cześć Paula Erdősa i Arthura Stone'a , którzy udowodnili to w 1946 roku i zostało opisane jako „fundamentalne twierdzenie ekstremalnej teorii grafów”.

Oświadczenie dotyczące wykresów Turana

Liczba ekstremalna ex( n ; H ) jest zdefiniowana jako maksymalna liczba krawędzi w grafie o n wierzchołkach niezawierającym podgrafu izomorficznego z H ; zobacz problem Forbidden subgraph, aby uzyskać więcej przykładów problemów związanych z liczbą ekstremalną. Twierdzenie Turána mówi, że ex( n ; Kr ₎ = t _{r − 1} ( n ), liczba krawędzi grafu Turana T(n, r − 1) i że wykres Turana jest jedynym takim grafem ekstremalnym. Twierdzenie Erdősa-Stone'a rozszerza ten wynik do H=K _r ( t ), pełnego r -częściowego wykresu z t wierzchołkami w każdej klasie, który jest grafem uzyskanym przez wzięcie Kr _: i zastąpienie każdego wierzchołka t niezależnymi wierzchołkami

${\ Displaystyle {\ mbox {ex}} (n; K_ {r} (t)) = \ lewo ({\ Frac {r-2} {r-1}} + o (1) \ prawo) {n \ wybierz 2}.}$

Stwierdzenie dla dowolnych grafów niedwudzielnych

Jeśli H jest arbitralnym grafem, którego liczba chromatyczna r > 2, to H jest zawarte w Kr ₍ t ), ilekroć t jest co najmniej tak duże jak największa klasa kolorów w r -kolorowaniu H , ale nie jest zawarte w wykres Turána T ( n , r − 1), ponieważ ten wykres, a zatem każdy z jego podwykresów, można pokolorować r − 1 kolorami. Wynika z tego, że liczba ekstremalna dla _H jest co najmniej tak duża, jak liczba krawędzi w T ( n , r - 1), a co najwyżej równa funkcji ekstremalnej dla Kr ( t ); to jest,

${\ Displaystyle {\ mbox {ex}} (n; H) = \ lewo ({\ Frac {r-2} {r-1}} + o (1) \ prawo) {n \ wybierz 2}.}$

w przypadku grafów dwudzielnych H twierdzenie to nie daje ścisłego ograniczenia funkcji ekstremalnej. Wiadomo, że gdy ^H jest dwudzielny, ex( n ; H ) = o ( n2 ), a dla ogólnych grafów dwudzielnych niewiele więcej wiadomo. Zobacz problem Zarankiewicza, aby uzyskać więcej informacji na temat funkcji ekstremalnych grafów dwudzielnych.

Gęstość Turana

$,$ -Stone'a jest użycie gęstości Turána wykresu który jest zdefiniowany przez ${\ Displaystyle \pi (H)=\lim _{n\to \infty}{\frac {{\text{ex}}(n;H)}{n \choose 2}}}$ . Określa to ekstremalną liczbę ${\ Displaystyle {\ tekst {ex (n; H)}}}$ aż do addytywnego terminu błędu ${\ Displaystyle o (n ^ {2})}$ . Można to również traktować w następujący sposób: biorąc pod uwagę sekwencję wykresów , z których każdy $}$ zawiera $, G_ {2}, \ kropki$ liczba wierzchołków dąży do nieskończoności, gęstość Turana jest maksymalną możliwą granicą gęstości ich krawędzi. Twierdzenie Erdősa-Stone'a określa gęstość Turana dla wszystkich wykresów, pokazując, że każdy wykres $}$ chromatyczną gęstość Turana wynoszącą $displaystyle H$

${\ Displaystyle \ pi (H) = {\ Frac {r-2} {r-1}}.}$

Dowód

Jeden dowód twierdzenia Erdősa – Stone'a wykorzystuje rozszerzenie twierdzenia Kővári – Sós – Turána na hipergrafy , a także twierdzenie o przesyceniu , poprzez utworzenie odpowiedniego hipergrafu dla każdego wykresu, który jest ${\ displaystyle K_ {r }(t)}$ -wolny i pokazujący, że hipergraf ma pewną ograniczoną liczbę krawędzi. Kővári – Sós – Turán mówi między innymi, że ekstremalna liczba pełnego wykresu dwudzielnego z $w$ każdej części $Kővári$ jest co najwyżej ${\ Displaystyle {\ tekst {ex}} (K_ {2} (t); n) \ równoważnik Cn ^ {2-1 / t}}$ dla stałej do $\ displaystyle C}$ . Można to rozszerzyć na hipergrafy: definiowanie $jako$$\ Displaystyle K_ {s, \ kropki, s} ^ {($ R { $displaystyle r}$$r$$z$ wierzchołkami w każdej części, a następnie ${\ Displaystyle {\ tekst {ex} } (K_ {s, \ kropki, s} ^ {(r)}, n) \ równoważnik Cn ^ {rs ^ {1-r}}} dla pewnej stałej do {\$ displaystyle $C$ .

Teraz dla danego wykresu z $r ( t ) {\ Displaystyle H = K_ {r} ($${\ Displaystyle r> 1, s \ geq 1}$ wykresu H $\ displaystyle G}$ { $z$ wierzchołkami $które$ nie zawierają podgrafu izomorficznego z $,$$.$ -graf samymi wierzchołkami jako i hiperkrawędź między wierzchołkami w $\ displaystyle G$ jeśli tworzą one klikę $w$$}$ . $}$ jeśli $zawiera$ kopię wykres $.$$}$$zawiera$ kopię , ponieważ każda para wierzchołków w różnych częściach musi mieć krawędź, ale żadne dwa wierzchołki w tej samej części nie zawierają krawędzi. Zatem. ${\ Displaystyle F}$ nie zawiera żadnych kopii ${\ Displaystyle K_ {s, \ kropki, s} ^ {r}}$ , więc ma $r}}}$${\ Displaystyle o (n ^$$}$$})$ że istnieją kopie r w $.$${\ Displaystyle {\ Frac {r-2} {r-1}}}$$,$$r$ że gęstość $-$ mieści gęstości czyli przez twierdzenie Turána ; zatem gęstość krawędzi jest ograniczona powyżej przez ${\ Displaystyle {\ Frac {r-2} {r-1}} + o (1)}$ .

Z drugiej strony możemy osiągnąć to ograniczenie, biorąc ${\ Displaystyle T ($ Turána , który nie zawiera żadnych kopii $}$ ale ma ${\ Displaystyle \ lewo ({\ Frac {r-2} {r-1}} -o (1 )\right){n \choose 2}}$ krawędzi, pokazując, że ta wartość jest maksymalna i kończąc dowód.

Wyniki ilościowe

Udowodniono kilka wersji twierdzenia, które dokładniej charakteryzują zależność n , r , t i wyrazu o (1) . Zdefiniuj notację s _{r ,ε} ( n ) (dla 0 < ε < 1/(2( r − 1))) jako największe t takie, że każdy wykres rzędu n i rozmiaru

${\ Displaystyle \ lewo ({\ Frac {r-2} {2 (r-1)}} + \ varepsilon \ prawej) n ^ {2}}$

zawiera Kr ₍ t ) .

Erdős i Stone to udowodnili

${\ Displaystyle s_ {r, \ varepsilon} (n) \ geq \ lewo (\ underbrace {\ log \ cdots \ log} _{r-1}n\prawo)^{1/2}}$

dla n wystarczająco dużych. Właściwą kolejność s _{r ,ε} ( n ) pod względem n odkryli Bollobás i Erdős: dla dowolnego r i ε istnieją stałe c ₁ ( r , ε) i c ₂ ( r , ε) takie, że c ₁ ( r , ε) log n < s _{r ,ε} ( n ) < do ₂ ( r , ε) log n . Chvátal i Szemerédi określili następnie charakter zależności od r i ε, aż do stałej:

${\ Displaystyle {\ Frac {1} {500 \ log (1 / \ varepsilon )}}\log n<s_{r,\varepsilon }(n)<{\frac {5}{\log(1/\varepsilon )}}\log n}$ dla wystarczająco dużego n .