Zakazany problem podgrafu

W teorii grafów ekstremalnych problem zabronionego podgrafu to $następujący$ problem: biorąc pod uwagę wykres znajdź maksymalną liczbę krawędzi ${\ Displaystyle \ operatorname {ex} (n, G) }$ an $-vertex graph$ może mieć taki, że nie ma podgrafu z ${\ displaystyle G}$ . W tym kontekście ${\ Displaystyle G}$ nazywamy podgrafem zabronionym .

$z$ to, ile krawędzi w $-wierzchołków$ gwarantuje, że ma on podgraf izomorficzny ?

Definicje

Ekstremalna liczba $G}$ $wierzchołków$ krawędzi w $}$ nie zawierającym podgrafu izomorficznego $displaystyle$ . ${r}}$ $wierzchołkach$ to kompletny wykres na . ${\ Displaystyle T (n, r)}$ jest wykresem Turána : kompletnym wykresem $częściowym$ . na $to$ , z wierzchołkami rozłożonymi między częściami tak równo, jak Liczba chromatyczna z to minimalna liczba kolorów potrzebnych do pokolorowania wierzchołków w $G$ sposób, że żadne dwa sąsiednie wierzchołki nie mają tego samego χ $}$ $Displaystyle \$ kolor.

Górne granice

Twierdzenie Turana

Twierdzenie Turána stwierdza, że dla dodatnich liczb całkowitych $\ Displaystyle$ n $r \ geq 3}$ ${\textstyle \operatorname {ex} (n, K_ {r}) = \ lewo (1- {\ frac {1} {r-1}} \ prawo) {\ frac {n ^ {2}} {2} }.}$ -

To rozwiązuje problem zabronionego podgrafu dla ${\ displaystyle G = K_ {r}}$ . Przypadki równości dla twierdzenia Turána pochodzą z wykresu Turána . ${\ Displaystyle T (n, r-1)}$ .

$\$ można uogólnić na dowolne wykresy $G$ biorąc pod uwagę $displaystyle$ sol { } Zauważ, że $}$ pokolorować kolorami $r$ a zatem nie ma podwykresów o liczbie niż $displaystyle$ W szczególności ${\ Displaystyle T (n, \ chi (G) -1)}$ nie ma podgrafów izomorficznych z ${\ Displaystyle G}$ . Sugeruje to $.$ powiązane z przypadkami równości dla Ta $intuicja$ okazuje się poprawna

Twierdzenie Erdősa-Stone'a

Twierdzenie Erdősa-Stone'a stwierdza, że dla wszystkich dodatnich ${\textstyle \operatorname {ex} (n,G)=\left(1-{\frac {1}{\chi (G)-1}}+o(1)\right){\frac {n^{ 2}}{2}}.}$ $całkowitych$ wszystkich $sol$

Kiedy nie jest $dwudzielny$ , daje nam to przybliżenie pierwszego rzędu ${\ Displaystyle \ operatorname {ex} (n, G)$ .

Grafy dwudzielne

W przypadku $wykresów$ dwudzielnych twierdzenie -Stone'a mówi nam tylko, że ${\ Displaystyle \ operatorname {ex} (n, G) = o (n ^ {2})}$ . Zakazany problem podgrafów dla grafów dwudzielnych jest znany jako problem Zarankiewicza i generalnie jest nierozwiązany.

Postęp w problemie Zarankiewicza obejmuje następujące twierdzenie:

Twierdzenie Kővári – Sós – Turán.

\

każdej pary dodatnich liczb całkowitych z

Displaystyle t \ geq s \ geq 1}

istnieje pewna stała (niezależna od

} styl wyświetlania n}

displaystyle C} t {\ displaystyle s

) taki, że

{\ textstyle \ nazwa operatora {ex} (n, K_ {s, t}) \ równoważnik Cn ^ {2- {\ frac {1} {s}}}} dla każdej dodatniej liczby całkowitej

n

\ displaystyle n}

.

Innym wynikiem dla wykresów dwudzielnych jest przypadek cykli parzystych, ${\ Displaystyle G = C_ {2k}, k \ geq 2}$ . Nawet cykle są obsługiwane przez uwzględnienie wierzchołka korzenia i ścieżek rozgałęziających się z tego wierzchołka. $mają$ tej samej długości ten sam punkt końcowy i nie nakładają się, tworzą cykl o długości ${\ displaystyle 2k}$ . Daje to następujące twierdzenie.

Twierdzenie ( Bondy i Simonovits , 1974). Istnieje pewna stała

taka

, że

+ {\ Frac {1} {k}}}}

{\ textstyle \ operatorname {ex} (n, C_ {2k}) \ równoważnik Cn ^ {

dla każdej dodatniej liczby

całkowitej

dodatniej liczby całkowitej

{\ Displaystyle k \ geq 2}

.

Potężnym lematem w teorii grafów ekstremalnych jest zależny wybór losowy. Ten lemat pozwala nam operować grafami dwudzielnymi o ograniczonym stopniu w jednej części:

Twierdzenie ( Alon , Krivelevich i Sudakov , 2003). Niech

,

wykresem

dwudzielnym

.

częściami wierzchołków

i

b że wierzchołek w ma co najwyżej

Wtedy

istnieje stała

że

zależna tylko od taka,

{\ textstyle \ operatorname {ex} (n, G) \ równoważnik Cn ^ {2- {\ Frac {1} {r}}}}

dla każdej dodatniej liczby całkowitej

{\ displaystyle n}

.

Ogólnie rzecz biorąc, mamy następujące przypuszczenie.:

Hipoteza racjonalnych wykładników (Erdős i Simonovits).

Dla

dowolnej skończonej rodziny

grafów

{\ Displaystyle \ alfa \ w [0,1)}

dwudzielny to istnieje wymierny takie, że

{\ Displaystyle \ operatorname {ex} (n, {\ mathcal {L}}) = \ Theta (n ^ {1+ \ alfa})}

.

Ankieta przeprowadzona przez Fürediego i Simonovitsa bardziej szczegółowo opisuje postęp w rozwiązaniu problemu z zakazanym podgrafem.

Dolne granice

Istnieją różne techniki uzyskiwania dolnych granic.

Metoda probabilistyczna

Chociaż ta metoda w większości daje słabe granice, teoria grafów losowych jest szybko rozwijającym się tematem. Opiera się na $, że jeśli weźmiemy losowo wykres o wystarczająco małej gęstości, wykres zawierałby$ w sobie tylko niewielką liczbę podwykresów . Te $kopie można usunąć$ usuwając jedną krawędź z każdej kopii $swobodny$ wykresie, dając nam wykres.

Metodę probabilistyczną można zastosować do udowodnienia $(G) -1}}}}$ ${\ Displaystyle \ operatorname {ex} (n, G) \ geq cn ^ { 2- {\ Frac {v (G)$ $-2 } {$ $jest$ gdzie stałą tylko zależną od . Do konstrukcji możemy przyjąć losowy wykres Erdősa-Rényiego ${\ Displaystyle G (n, p)}$ $,$ $czyli$ wykres z i krawędzią były dowolnymi dwoma wierzchołkami narysowanymi z prawdopodobieństwem . Po obliczeniu oczekiwanej liczby kopii w $($ ${\ Displaystyle G (n, p)}$ liniowość , usuwamy jedną krawędź z każdej takiej kopii ${\ displaystyle G} i$ na końcu pozostaje nam wykres wolny od ${\ displaystyle G} .$ Oczekiwaną liczbę pozostałych krawędzi można znaleźć jako ${\ Displaystyle \ operatorname {ex} (n, G) \ geq cn ^ {2- {\ Frac {v (G) -2} {e (G) -1}}}}$ dla stałej do $\ displaystyle c}$ w zależności od ${\ displaystyle G}$ . Dlatego istnieje co najmniej jeden $wierzchołkowy$ z co najmniej tyloma krawędziami, ile oczekiwano.

Tej metody można również użyć do znalezienia konstrukcji wykresu dla granic obwodu wykresu. Obwód oznaczony przez $,$ cyklu wykresu Zauważ, że dla wykres musi zakazać wszystkich cykli o długości mniejszej niż równej $(G)>$ $\ Displaystyle g$ . Zgodnie z liniowością oczekiwaną oczekiwana liczba $\$ $styl wyświetlania i=3,...,n-1,n}$ cykli jest równa sumie oczekiwanej liczby $cykli$ ( .). Ponownie usuwamy krawędzie z każdej kopii zabronionego wykresu i otrzymujemy wykres wolny od mniejszych cykli i ${\ Displaystyle g (G)> 2k}$ do ${\ Displaystyle c_ {0} n ^ {1 + {\ Frac {1} {2k-1}}}} krawędzie$ po lewej stronie.

Konstrukcje algebraiczne

W określonych przypadkach dokonano ulepszeń, znajdując konstrukcje algebraiczne. Wspólną cechą takich konstrukcji jest to, że polegają one na wykorzystaniu geometrii do skonstruowania grafu, w którym wierzchołki reprezentują obiekty geometryczne, a krawędzie zgodnie z relacjami algebraicznymi między wierzchołkami. Kończymy bez podwykresu $.$ wyłącznie z powodów czysto geometrycznych, podczas gdy wykres ma dużą liczbę krawędzi, aby być silnym ograniczeniem ze względu na sposób zdefiniowania częstości występowania Następujący dowód Erdősa, Rényi i Sősa ustalający dolną granicę na ${\ Displaystyle \ operatorname {ex} (n, K_ {2,2})}$ jak ${\ Displaystyle \ lewo ({\ Frac {1} {2}} -o (1) \ prawo) n ^ {3/2}.}$ , demonstruje moc tej metody.

Załóżmy najpierw, że dla jakiejś liczby pierwszej $}$ $\ displaystyle n = p ^ {2} -1$ . Rozważ wykres polaryzacji $}$ elementami wierzchołków i krawędziami między wierzchołkami ${\ Displaystyle \ mathbb {F} _ {p} ^ {2} - \ {0,0 \}$ ${\ Displaystyle (x, y)}$ i ${\ Displaystyle (a, b)}$ wtedy i tylko wtedy, gdy ${\ Displaystyle ax + przez = 1}$ w ${\ Displaystyle \ mathbb {F} _ {p}}$ . Ten wykres jest $ponieważ$ $,$ układ dwóch równań liniowych w mieć więcej niż Wierzchołek ${\ Displaystyle (a, b)}$ (załóżmy, że ${\ Displaystyle b \ neq 0}$ ) jest połączone z ${\ Displaystyle \ lewo (x, {\ Frac {1-ax} {b}}\ prawej)}$ dla dowolnych $}$ w sumie co najmniej (odjętych) $\ in \ mathbb {F} _ {p}$ 1 w przypadku ${\ Displaystyle (a, b) = \ lewo (x, {\ Frac {1-ax} {b}} \ prawej)})$ . Więc jest co najmniej ${\ Displaystyle {\ Frac {1} {2}} (p ^ {2} -1) (p-1) = \ lewo ({\ Frac {1} {2}} -o (1) \ prawo) p^{3}=\left({\frac {1}{2}}-o(1)\right)n^{3/2}}$ krawędzie, zgodnie z życzeniem. Dla ogólnego możemy wziąć $\$ $Displaystyle p = (1-o (1)) {\ sqrt {n}}}$ z ${\ Displaystyle p \ leq {\ sqrt {n + 1}}}$ (co jest możliwe, ponieważ istnieje liczba pierwsza ${\ displaystyle p}$ w przedziale ${\ Displaystyle [kk ^ {0,525}, k]}$ dla wystarczająco dużego ${\ displaystyle k}$ ) i skonstruuj wykres polaryzacji za pomocą takiego , a następnie dodając ${\ displaystyle p}$ ${\ displaystyle np ^ {2} + 1}$ izolowane wierzchołki, które nie wpływają na wartość asymptotyczną.

Następujące twierdzenie jest podobnym wynikiem dla ${\ Displaystyle K_ {3,3}}$ .

Twierdzenie (Brown, 1966).

{\ Displaystyle \ nazwa operatora {ex} (n, K_ {3,3}) \ geq \ lewo ({\ Frac {1} {2}} -o (1) \ prawej) n ^ {5/3}.}

Zarys dowodu. Podobnie jak w poprzednim twierdzeniu, możemy przyjąć

{\ displaystyle n = p ^ {3}}

za liczbę pierwszą

{\ displaystyle p}

i niech wierzchołki naszego wykresu będą elementami .

{\ displaystyle \ mathbb {f} _ {p} ^ {3}

} Tym razem wierzchołki i

{\

y, z)}

wtedy i tylko wtedy

{\ Displaystyle (xa) ^ {2} + (yb) ^ {2} + (zc) ^ {2} = u}

w fa

\ Displaystyle \ mathbb {F} _ {p }}

dla niektórych specjalnie wybranych

{\ displaystyle u}

. Wtedy jest to

, ponieważ

najwyżej dwa punkty leżą na przecięciu trzech Wtedy od wartości

{\ Displaystyle (xa) ^ {2} + (yb) ^ {2} + (zc) ^ {2}}

jest prawie jednolite na całej

{\ Displaystyle \ mathbb {F} _ {p}} , każdy punkt

mieć około

2

całkowita liczba krawędzi wynosi

{\ Displaystyle \ lewo ({\ Frac {1} {2}} -o (1) \ prawo) p ^ {2} \ cdot p ^ {3} = \ lewo ({\ frac {1}{2}}-o(1)\right)n^{5/3}}

.

Jednak pozostaje otwartą kwestią, aby zaostrzyć dolną granicę dla ${\ Displaystyle \ operatorname {ex} (n, K_ {t, t})}$ dla ${\ displaystyle t \geq 4}$ .

Twierdzenie (Alon i in., 1999) Dla ${\ Displaystyle t \ geq (s-1)! + 1}$ , ${\ Displaystyle \ nazwa operatora {ex} (n, K_ {s, t}) = \ Theta (n ^ {2- {\ Frac {1} {s}}}).}$

Randomizowane konstrukcje algebraiczne

Ta technika łączy w sobie dwie powyższe idee. Wykorzystuje losowe relacje typu wielomianowego podczas definiowania częstości występowania między wierzchołkami, które znajdują się w pewnym zbiorze algebraicznym. Wykorzystanie tej techniki do udowodnienia następującego twierdzenia.

Twierdzenie ${\ Displaystyle \ nazwa operatora {ex} (n, K_ {s, t}) \ geq \ lewo ({\ Frac {1} {2}} -o (1) \ prawej) n ^ {1- {\ ułamek {1}{s}}}}$ dla $≥$ istnieje $,$ że .

Zarys dowodu: $displaystyle$ $q ^ {s} \ leq n}$ bierzemy największą potęgę pierwszą . Ze względu na główne luki mamy ${\ Displaystyle q = (1-o (1)} n ^ {\ Frac {1} {s}}}$ . Niech ${\ Displaystyle f \ w \ mathbb {F} _ {q} [x_ {1}, x_ {2}, \ cdots, x_ {s}, y_ {1}, y_ {2}, \ cdots, y_ {s}] _ {\ równoważnik d}} będzie$ losowym wielomianem w stopniu co najwyżej ${\ Displaystyle d = s ^ {2}}$ ${\ displaystyle \ mathbb {f} _ {q}}$ w $(X_ {1}, X_ {2}, ..., X_ {s})}$ $\ Displaystyle Y = (Y_ {1}, Y_ {2}, ..., Y_ {s})}$ Y i satysfakcjonujące ${\ Displaystyle f (X, Y) = f ( Y, X)}$ . Niech wykres $x$ $\ Displaystyle G}$ $jeśli$ wierzchołków ${\ displaystyle f (x, y) = 0}$ dwa wierzchołki sąsiadują, .

Naprawiamy $_$ i $_$ _ ${\ Displaystyle \ mathbb {F} _ {q} ^ {s}}$ nie w ${\ Displaystyle U}$ satysfakcjonujące ${\ Displaystyle f (x, u) = 0}$ dla wszystkich elementów ${\ displaystyle u \ w U}$ . Na podstawie granicy Langa – Weila otrzymujemy, że dla $wystarczająco dużych$ mamy ${\ Displaystyle | Z_ {U} | \ równoważnik C}$ lub ${\ Displaystyle | Z_ {U}|> {\ Frac {q} {2}}}$ dla pewnej stałej $displaystyle$ Teraz obliczamy oczekiwaną liczbę taką, że $U}$ ${\ Displaystyle Z_ {U}}$ $ma$ rozmiar większy niż $usuń$ wierzchołek z każdego . Wynikowy $wykres$ okazuje się być tego wynikowego

Przesycenie

Przesycenie odnosi się do wariantu problemu zabronionego podgrafu, w którym rozważamy, kiedy jakiś $-jednolity$ $wykres$ $wiele$ kopii jakiegoś zabronionego $Intuicyjnie$ można by się $że$ zawierał więcej Wprowadzamy gęstość Turana, aby sformalizować to pojęcie.

Gęstość Turana

Gęstość Turana -jednolitego wykresu jest zdefiniowana jako $displaystyle$ $h}$

{\ Displaystyle \ pi (G) = \ lim _ {n \ do \ infty} {\ Frac {\ operatorname {ex} (n, G)} {\ binom {n} {h}}}.}

Prawdą jest, że ${\ Displaystyle {\ Frac {\ operatorname {ex} (n, G)} {\ binom {n} {h}}}}$ maleje monotonicznie, więc granica musi istnieć.

Jako przykład Twierdzenie Turána podaje, że ${\ Displaystyle \ pi (K_ {r + 1}) = 1- {\ Frac {1} {r}}$ } Twierdzenie Erdősa-Stone'a daje, że ${\ Displaystyle \ pi (G) = 1 - {\ Frac {1} {\ chi (H) -1}}}$ . W szczególności dla dwudzielnego ${\ displaystyle G$ } ${\ Displaystyle \ pi (G) = 0}$ . Określenie gęstości Turana ${\ displaystyle o (n ^ {2})}$ równoznaczne z określeniem $\ pi$ an $( H )$ błąd.

Twierdzenie o przesyceniu

Rozważmy $-jednolity$ z $wierzchołkami$ _ $_$ _ Twierdzenie o przesyceniu stwierdza, że dla każdego $displaystyle n$ $jeśli$ , $wykresem$ jest na $}$ wierzchołków i co najmniej $_$ _ $_$ _ ${\ Displaystyle \ delta n ^ {v (H)}}$ kopie ${\ Displaystyle H}$ .

Równoważnie możemy przekształcić to twierdzenie w następujący sposób: Jeśli wykres $)} )}$ ) { ${$ $($ kopii ${\ Displaystyle H}$ , to jest co najwyżej ${\ Displaystyle \ pi (H) {\ binom {n} {2}} + o (n^{2})}$ krawędzie w ${\ Displaystyle G}$ .

Aplikacje

Rozważając problemy typu przesycenia, możemy rozwiązywać różne problemy podgrafów zabronionych. Poniżej przedstawiamy ponownie i przedstawiamy szkic dowodowy twierdzenia Kővári – Sós – Turán:

Twierdzenie Kővári – Sós – Turán.

\

każdej pary dodatnich liczb całkowitych z

Displaystyle t \ geq s \ geq 1}

istnieje pewna stała (niezależna od

displaystyle C} t {\ displaystyle s

} styl wyświetlania n}

) taki, że

{\ textstyle \ operatorname {ex} (n, K_ {s, t}) \ równoważnik Cn ^ {2- {\ frac {1} {s}}}} dla każdej dodatniej liczby całkowitej n {\

displaystyle

}

.

Dowód. Niech

będzie

wykresem na

Displaystyle

i rozważ liczbę kopii

K_ {1, s}}

1

\

w sol

\displaystyle G}

. Biorąc

pod

uwagę wierzchołek stopnia otrzymujemy dokładnie

{\ Displaystyle {\ binom {d} {s}}}

kopie

{\ Displaystyle K_ {1, s}}

zakorzenione w tym wierzchołku, w sumie

{\ Displaystyle \ suma _ {v \ w V (G)} {\ binom {\ nazwa operatora {stopni} (v)} {s}}}

kopii. Tutaj

{\ Displaystyle {\ binom {k} {s}} = 0}

kiedy

{\ Displaystyle 0 \ równoważnik k <s}

. Dzięki wypukłości jest w sumie co najmniej

{\ Displaystyle n {\ binom {2e (G) / n} {s}}}

kopii

{\ Displaystyle K_{1,s}}

. Co więcej, istnieją wyraźnie podzbiory

{\

Displaystyle {\ binom {n} {

wierzchołki, więc jeśli jest ich więcej niż kopie

}

}}

Displaystyle (t

, to zgodnie z zasadą przegródek musi istnieć podzbiór

\

, które tworzą zbiór liści co najmniej

}

kopii,

displaystyle

.

\

istnieje występowanie

)

jak mamy . Innymi słowy, mamy zdarzenie, jeśli

{\ Displaystyle {\ Frac {e (G) ^ {s}} {n ^ {s-1}}} \ geq O (n ^ {s})} , co upraszcza się

do

{\ Displaystyle e (G) \ geq O (n ^ {2- {\ Frac {1} {s}}})}

, co jest stwierdzeniem twierdzenia.

W tym dowodzie używamy metody przesycenia, biorąc pod uwagę liczbę wystąpień mniejszego podwykresu. Zazwyczaj zastosowania metody przesycenia nie wykorzystują twierdzenia o przesyceniu. Zamiast tego struktura często polega na znalezieniu podgrafu jakiegoś zabronionego podgrafu $i$ $pokazaniu$ , że jeśli pojawia się on zbyt wiele razy w $}$ H. $}$ $H$ musi pojawić się w ${\ displaystyle G}$ również. Inne twierdzenia dotyczące problemu podgrafu zabronionego, które można rozwiązać za pomocą przesycenia, obejmują:

${\ Displaystyle \ operatorname {ex} (n, C_ {2t}) \ równoważnik O (n ^ {1 + 1 / t})}$ .
dla każdego ${\ Displaystyle t}$ i ${\ Displaystyle k \ geq 2}$ , ${ \ displaystyle \ nazwa operatora {ex} (n, C_ {2k}, C_ {2k-1}) \ równoważnik O \ lewo (\ lewo ({\ frac {n}{2}} \ prawo) ^ {1 + 1 / t}\prawo)}$ .
Jeśli $oznacza wykres określony przez wierzchołki i$ sześcianu, a $oznacza$ uzyskany przez połączenie dwóch przeciwległych wierzchołków sześcianu, ${\ Displaystyle \ nazwa operatora {ex} (n, Q) \ równoważnik \ nazwa operatora {ex} (n, Q ^ {*}) = O(n^{8/5})}$ .

Uogólnienia

Problem można uogólnić dla zestawu zabronionych podgrafów $:$ znajdź maksymalną liczbę krawędzi na grafie $}$ , który nie ma podgrafu izomorficznego z żadnym wykresem z $S}$ $displaystyle S$ .

Istnieją również wersje hipergrafów zabronionych problemów podgrafów, które są znacznie trudniejsze. Na przykład problem Turána można uogólnić, prosząc o największą liczbę krawędzi w - $3$ -jednolitym hipergrafie, który nie zawiera czworościanów. Analogiem $konstrukcji$ Turana byłoby i ${\ Displaystyle x, y, z}$ o 3 krawędzie, jeśli wszystkie są w różnych $Displaystyle V_ {i$ lub jeśli dwa z nich są w $}$ i trzeci $($ gdzie $_$ _ To jest wolne od czworościanu, a gęstość krawędzi wynosi ${\ Displaystyle 5/9}$ . Jednak najbardziej znaną górną granicą jest 0,562, przy użyciu techniki algebr flagowych.

Zobacz też