Lemat nadmuchowy

Lemat o rozszerzeniu , udowodniony przez Jánosa Komlósa , Gábora N. Sárközy'ego i Endre Szemerédiego w 1997 roku, jest ważnym wynikiem w teorii grafów ekstremalnych , szczególnie w kontekście metody regularności . Stwierdza, że ​​regularne pary w stwierdzeniu lematu Szemerédiego o regularności zachowują się jak kompletne grafy dwudzielne w kontekście osadzania grafów rozpinających o ograniczonym stopniu .

Definicje i oświadczenie

Aby formalnie sformułować lemat o powiększaniu, musimy najpierw zdefiniować pojęcie pary superregularnej .

Superregularne pary

Para ${\ Displaystyle (A, B)}$ podzbiorów zbioru wierzchołków nazywa się ${\ Displaystyle (\ varepsilon, \ delta)}$ -super-regularna, jeśli dla każdego ${\ Displaystyle X \ podzbiór A}$ i ${\ Displaystyle Y \ podzbiór B}$ satystyczny

${\ Displaystyle | X |> \ varepsilon | A |}$ i ${\ Displaystyle | Y|> \ varepsilon | B |}$

mamy

${\ Displaystyle e (X, Y)> \ delta | X || Y |}$

a ponadto,

${\ Displaystyle \ deg (a)> \ delta | B |}$ dla wszystkich ${\ Displaystyle a \ in A}$ i ${\ Displaystyle \ deg (b)> \ delta | A |}$ dla wszystkich ${\ Displaystyle b \ w B}$ .

Tutaj mi $\ Displaystyle e (X, Y)}$ oznacza liczbę par ${\ Displaystyle (x, y)}$ z ${\ Displaystyle x \ w X}$ i $\ in Y}$$krawędzią$ że .

Stwierdzenie lematu powiększającego

Biorąc pod uwagę wykres rzędu ${\ Displaystyle R}$$i$ dodatnie parametry ${\ Displaystyle \ delta, \ Delta}$ istnieje dodatni ${\ Displaystyle \varepsilon =\varepsilon (\delta ,\Delta ,r)}$ takie, że spełniony jest następujący warunek. Niech ${\ displaystyle n_ {1}, n_ {2}, \ kropki, n_ {r}}$ będą dowolnymi dodatnimi liczbami całkowitymi i zastąpmy wierzchołki ${\ displaystyle v_ {1}, v_ {2}, \ kropki, v_ {r}}$ R $\ displaystyle R}$ z zestawami rozłącznymi parami ${\ Displaystyle V_ {1 }, V_ {2}, \ kropki, V_ {r}}$ rozmiarów ${\ Displaystyle n_ {1}, n_ {2}, \ kropki, n_ {r}}$ (dmuchanie w górę). Konstruujemy dwa wykresy na tym samym zbiorze wierzchołków ${\ Displaystyle V = \ bigcup V_ {i}}$ . R ${\ displaystyle \ mathbf {R}}$ uzyskuje się przez zastąpienie każdej krawędzi z R ${\ Displaystyle \ {v_ {i}, v_ {j} \}}$$\ displaystyle R}$ z pełnym wykresem dwudzielnym między odpowiednimi zestawami wierzchołków $j}}$ jot $displaystyle V_$ . Rzadszy wykres G jest konstruowany przez zastąpienie każdej krawędzi $)}$$Displaystyle \ {v_ {i}, v_ {j} \}}$ δ $\ varepsilon, \$ -super-regularna para między ${\ displaystyle V_ {i}}$ i ${\ displaystyle V_ {j}}$ . Jeśli wykres można osadzić w ${\ Displaystyle \ Delta (H) \ leq \ Delta},$$H$$to$ już osadzić w

Szkic dowodowy

$\ displaystyle H} . Argument następnie przebiega przez ograniczenie wskaźnika awaryjności$ nadmuchowego opiera się na użyciu losowego algorytmu zachłanności (RGA) do sekwencyjnego osadzania wierzchołków ${$$, aby był mniejszy$ (i faktycznie) odpowiedniego doboru parametrów. Oznacza to, że istnieje niezerowa szansa na powodzenie algorytmu, więc musi istnieć osadzenie.

Próba bezpośredniego osadzenia wszystkich wierzchołków w ten sposób nie działa $.$ ponieważ algorytm może utknąć, gdy pozostanie tylko niewielka liczba wierzchołków Zamiast tego odkładamy na bok niewielką część zbioru wierzchołków, zwaną wierzchołkami buforowymi i próbujemy osadzić pozostałe wierzchołki. Wierzchołki bufora są następnie osadzane przy użyciu twierdzenia o małżeństwie Halla , aby znaleźć idealne dopasowanie między wierzchołkami bufora a pozostałymi wierzchołkami ${\ displaystyle G}$ .

Notacja

Pożyczamy wszystkie oznaczenia wprowadzone w poprzednich rozdziałach. Niech ${\ Displaystyle n = | V (G) | = \ suma n_ {i}}$ . Ponieważ można osadzić w ${\ Displaystyle$$\ mathbf {R}}$ , możemy napisać $\ Displaystyle V (H) = X = \ bigcup _{i\leq r}X_{i}}$ z ${\ Displaystyle | X_ {i} | = | V_ {i} |}$ dla wszystkich ${\ Displaystyle i}$ . Dla wierzchołka niech oznacza $Displaystyle x$$\ w X_ {$$}$ . dla ${\ Displaystyle x \ w X_ {i}, y \ w X_ {j}}$ ,

${\ Displaystyle d_ {xy} = {\ Frac {e (V_ {i}, V_ {j})} {| V_ {i}|| V_ {j}|}}}$

oznacza gęstość krawędzi między odpowiednimi zestawami wierzchołków sol $\ displaystyle G}$ . ${\ Displaystyle \ phi: V (G) \ do V (H)}$ to osadzenie, które chcemy zbudować. ${\ displaystyle T}$ to ostatni czas, po którym algorytm się kończy.

Zarys algorytmu

Faza 0: Inicjalizacja

1. $wybierz$ zestaw wierzchołków buforowych $jako$ wierzchołków maksymalny zestaw wierzchołków oddalonych od siebie o ${\ displaystyle 4}$
2. $te$ pozostałe wierzchołki ( $w$$na$ , umieszczając najpierw
3. Zadeklaruj kolejkę $priorytetami$ , która początkowo jest pusta.
4. $zbiór$ tablicę zestawów indeksowanych $przez$ wierzchołki , reprezentujących wszystkich „wolnych $,$ zbiór niezajęte wierzchołki w wierzchołku $z$ zmapować bez naruszania jakichkolwiek warunków przylegania od już osadzonych sąsiadów w ${$$}$$displaystyle$ . ${\ displaystyle F_ {z}}$ jest inicjowany na ${\ displaystyle V_ {z}}$ .

Faza 1: Randomizowane chciwe osadzanie

1. Wybierz wierzchołek ze zbioru pozostałych wierzchołków w następujący sposób: ${\ displaystyle x}$
   1. Jeśli kolejka $priorytetami$ nie jest pusta, wybierz wierzchołek z ${\ displaystyle q}$
   2. W przeciwnym razie wybierz wierzchołek z $pozostałych$ wierzchołków
2. $wierzchołka$ obraz dla ze zbioru „dobrych” wyborów, gdzie $jest$$dobry$ żaden nowe zestawy swobodne $.$ różnią się
3. Zaktualizuj wolne zbiory i $wierzchołki, których wolne zbiory stały się zbyt małe w stosunku do ich rozmiaru w ostatniej aktualizacji,$ priorytetami ${\ displaystyle Q}$
4. Przerwij, jeśli kolejka zawiera wystarczająco duży ułamek któregokolwiek ze zbiorów. $X$$i}}$
5. $wierzchołki$ niebuforowane do osadzenia w lub $,$$zaktualizuj$ i wróć kroku 1 w przeciwnym razie przejdź do fazy 2.

Faza 2: dopasowanie Kőniga-Halla dla pozostałych wierzchołków

Rozważ zestaw wierzchołków pozostawionych do osadzenia, czyli dokładnie $w B} F_ {b }(T)}$ oraz zbiór wolnych miejsc $\$ . $i$ wykres między tymi dwoma zestawami, łącząc każdy z $dopasowanie$ na dwudzielnym Osadź zgodnie z tym dopasowaniem.

Dowód poprawności

Dowód poprawności jest techniczny i dość skomplikowany, więc pomijamy szczegóły. Główny argument przebiega następująco:

Krok 1: większość wierzchołków jest dobra, a wystarczająca liczba wierzchołków jest wolna

Udowodnij jednocześnie przez indukcję na $to$ jeśli jest $wierzchołkiem$ osadzonym w czasie , $displaystyle t$ }

1. tylko niewielka część wyborów w ${\ Displaystyle F_ {x} (t)}$ jest zła
2. wszystkie wolne zbiory są dość duże dla nieosadzonych wierzchołków $}$$\ Displaystyle F_ {z} (t + 1)$

Krok 2: „główny lemat”

Rozważmy $\ równoważnik r, Y \ subseteq X_ {i}}$${\ Displaystyle A \ subseteq V_ {i}}$ i ZA tak, że ${\ Displaystyle | A |}$ nie jest za mały. Rozważmy zdarzenie $\ Displaystyle E_ {A, Y}}$ mi za

1. $fazie$ wierzchołki nie są osadzone w pierwszej
2. y ${\ Displaystyle y \ w Y}$$jest$ taki czas ułamek wolnych wierzchołków w czasie $Y}$$Displaystyle y \$$był$ .

$udowadniamy,$ prawdopodobieństwo .

Krok 3: faza 1 powiedzie się z dużym prawdopodobieństwem

Jedynym sposobem, w jaki pierwsza faza może się nie powieść, jest jej przerwanie, ponieważ na pierwszym etapie wiemy, że zawsze istnieje wystarczający wybór dobrych wierzchołków. Program przerywa działanie tylko wtedy, gdy kolejka jest zbyt długa. Argument następnie przebiega przez ograniczenie związkowe we wszystkich trybach awarii, zauważając, że dla każdego konkretnego wyboru ${\ Displaystyle 1 \ równoważnik i \ równoważnik r}$ , ${\ Displaystyle Y \ subseteq X_ {i}, | Y | \ geq \ delta _ {Q} | X_ {i} |} i ZA = V ja {\ Displaystyle A = V_ {$ i ${$ \ $Y }$ reprezentujący podzbiór kolejki, która się nie powiodła, potrójna $„$ ”, a zatem ma niskie

Krok 4: brak kolejki w początkowej fazie

Przypomnijmy, że lista została ustawiona w taki sposób, że sąsiedzi wierzchołków w buforze są osadzeni jako pierwsi. Czas, w którym wszystkie te wierzchołki zostaną osadzone, nazywany jest fazą początkową . Udowodnij przez indukcję $wierzchołki$ nie są dodawane do kolejki w początkowej fazie. Wynika z tego, że wszyscy sąsiedzi wierzchołków bufora są dodawani przed resztą wierzchołków.

Krok 5: wierzchołki bufora mają wystarczającą liczbę wolnych miejsc

Dla $($ i $}$$x$ prawdopodobieństwa $)$ , uwarunkowane założeniem, że był wolny przed dowolnym wierzchołkiem w ${\ Displaystyle N_ {H} (x)}$ zostały osadzone.

Krok 6: faza 2 powiedzie się z dużym prawdopodobieństwem

Zgodnie z twierdzeniem Halla o małżeństwie faza 2 kończy się niepowodzeniem wtedy i tylko wtedy, gdy warunek Halla zostanie naruszony. Aby tak się stało, muszą istnieć pewne i takie, że S $S \ subseteq X_ {i}} r {\ Displaystyle 1 \ równoważnik$$r$${\ Displaystyle | \ bigcup _ {z \ w S} F_ {z} (T) | <| S |}$ . ${\ displaystyle | S|}$ nie może być zbyt mały ze względu na wielkość wolnych zestawów (krok 1). Jeśli ${\ Displaystyle | S |}$ jest zbyt duży, więc z dużym prawdopodobieństwem ${\ Displaystyle \ bigcup _ {z \ w S} F_ {z} (T) = V_{i}(T)}$ , więc prawdopodobieństwo niepowodzenia w takim przypadku byłoby niskie. Jeśli ${\ Displaystyle | S |}$ nie jest ani za mały, ani za duży, a następnie zauważając, że ${\ Displaystyle A: = V_ {i} (T) \ setminus \bigcup _{z\in S}F_{z}(T)}$ jest dużym zbiorem nieużywanych wierzchołków, możemy użyć głównego lematu i prawdopodobieństwa niepowodzenia związanego z sumą .

Aplikacje

Lemat z powiększeniem ma wiele zastosowań w osadzeniu gęstych grafów.

Hipoteza Pósy-Seymoura

W 1962 roku $,$ Pósa przypuszczał że każdy $wierzchołkowy o minimalnym$ najmniej zawiera kwadrat cyklu Hamiltona , uogólniając Diraca ' twierdzenie s . Przypuszczenie zostało dalej rozszerzone przez Paula Seymoura w 1974 roku na następujące:

Każdy wykres na $wierzchołkach$ o minimalnym stopniu co najmniej ${\ Displaystyle {\ Frac {kn} {k + 1}}}$ zawiera -tą potęgę hamiltonianu $\ displaystyle n}$ cykl.

Powiększony lemat został użyty przez Komlósa, Sárközy'ego i Szemerédiego, aby udowodnić hipotezę dla wszystkich wystarczająco dużych wartości $displaystyle$ dla ustalonego $k}$ ) w 1998 roku.

Hipoteza Alona-Yustera

W 1995 roku Noga Alon i Raphael Yuster rozważyli uogólnienie dobrze znanego twierdzenia $\ displaystyle H}$ – Szemerédiego na dowolne - czynniki (zamiast tylko pełnych wykresów) i udowodnili następujące stwierdzenie: H {

Dla każdego ustalonego wykresu z wierzchołkami ${\ displaystyle h}$$,$ dowolnego wykresu G z n wierzchołkami i minimalnym stopniem $Displaystyle d \ geq {\ frac {\ chi (H) -1} {\ chi (H)}} n}$ zawiera ${\ Displaystyle (1-o (1)) n / h}$ rozłączne kopie wierzchołków H.

Przypuszczali również, że wynik utrzymuje się tylko ze stałym (zamiast liniowym) błędem:

Dla każdej liczby całkowitej $H$$\$ taka $wierzchołkami$ że ​​dla $displaystyle G}$$wykresu$ z wykres $displaystyle$ z $H.$ i minimalnym stopniem ${\ Displaystyle d \ geq {\ Frac {\ chi (H) -1} {\ chi$ zawiera co najmniej rozłączne kopie wierzchołków $/hc (h) }$${\ Displaystyle$ .

To przypuszczenie zostało udowodnione przez Komlósa, Sárközy'ego i Szemerédiego w 2001 roku za pomocą lematu z powiększeniem.

Historia i warianty

Powiększony lemat, opublikowany po raz pierwszy w 1997 roku przez Komlósa, Sárközy'ego i Szemerédiego, pojawił się jako udoskonalenie istniejących technik dowodowych wykorzystujących metodę regularności do osadzania grafów rozpinających, jak w dowodzie hipotezy Bollobása o drzewach rozpinających, pracy nad Hipoteza Pósy-Seymoura o minimalnym stopniu potrzebnym do zawarcia k-tej potęgi grafowej cyklu Hamiltona oraz dowód hipotezy Alona-Yustera o minimalnym stopniu potrzebnym do tego, aby graf miał doskonały współczynnik H. Dowody wszystkich tych twierdzeń polegały na użyciu losowego algorytmu zachłannego do osadzenia większości wierzchołków, a następnie użyciu argumentu podobnego do Kőniga-Halla, aby znaleźć osadzenie dla pozostałych wierzchołków. W pierwszym dowodzie lematu z powiększeniem również wykorzystano podobny argument. Jednak później, w 1997 r., ci sami autorzy opublikowali inny artykuł, w którym znaleźli ulepszenie losowego algorytmu, aby uczynić go deterministycznym.

Peter Keevash znalazł uogólnienie powiększonego lematu na hipergrafy w 2010 roku.

Stefan Glock i Felix Joos odkryli wariant powiększonego lematu dla grafów tęczowych w 2018 roku.

W 2019 roku Peter Allen, Julia Böttcher, Hiep Hàn, Yoshiharu Kohayakawa i Yury Person znaleźli nieliczne analogi lematu do osadzenia ograniczonych grafów stopni w grafach losowych i pseudolosowych