Wykres pseudolosowy

W teorii grafów o grafie mówi się, że jest grafem pseudolosowym , jeśli spełnia pewne właściwości, którym grafy losowe podlegają z dużym prawdopodobieństwem . Nie ma konkretnej definicji pseudolosowości grafu, ale istnieje wiele rozsądnych charakterystyk pseudolosowości, które można rozważyć.

Właściwości pseudolosowe zostały po raz pierwszy formalnie rozważone przez Andrew Thomasona w 1987 r. Zdefiniował on warunek zwany „pomieszaniem”: mówi się, że wykres jest ${\ Displaystyle (p, \ alpha)}$$Displaystyle G = (V, E)$ - pomieszane naprawdę ${\ Displaystyle p}$ i ${\ Displaystyle \ alpha}$ z ${\ Displaystyle 0 <p <1 \ równoważnik \ alfa}$ jeśli

${\ Displaystyle \ lewo | e (U) - p {\ binom {| U |} {2}} \ prawo | \ równoważnik \ alfa | U |}$

dla każdego podzbioru $U$ wierzchołków , gdzie $jest$ liczbą krawędzi między $}$$displaystyle$ krawędzi w podgrafie indukowanym przez zbiór wierzchołków ${\ displaystyle U}$ ). Można pokazać, że losowy wykres Erdősa – Rényiego ${\ Displaystyle G (n, p)}$ jest prawie na pewno ${\ Displaystyle (p, O ({\ sqrt {np}})}} -$ pomieszane. Jednak wykresy z mniej równomiernie rozłożonymi krawędziami , na przykład wykres na $składający$ się z $wierzchołków$ wykresu i $niezależnych$ wierzchołków, nie $alpha$$)} -$ pomieszane dla każdego małego dzięki czemu pomieszanie jest rozsądnym kwantyfikatorem „losowych” właściwości rozkładu krawędzi wykresu.

Połączenie z lokalnymi warunkami

Thomason wykazał, że warunek „pomieszania” implikuje warunek prostszy do sprawdzenia, zależny tylko od współstopnia dwóch wierzchołków, a nie od każdego podzbioru zbioru wierzchołków grafu. Pozwalając ${\ Displaystyle \ operatorname {codeg} (u, v)}$$być$ wspólnych sąsiadów dwóch wierzchołków $uwagę$ Thomason wykazał, że biorąc pod wykres sol ${\ displaystyle G}$ n $\ displaystyle n}$ wierzchołki o minimalnym stopniu ${\ displaystyle np}$ , jeśli ${\ Displaystyle \ operatorname {codeg} (u, v) \ równoważnik np ^ {2} + \ ell}$ dla każdego $\$ v $}$ displaystyle $jest$ to ${\ Displaystyle \ lewo (p, {\ sqrt {(p + \ ell) n}} \, \ prawo)} -$ pomieszane. Ten wynik pokazuje, jak algorytmicznie sprawdzić warunek pomieszania w czasie wielomianowym w liczbie wierzchołków i może być użyty do pokazania pseudolosowości określonych grafów.

Twierdzenie Chunga-Grahama-Wilsona

W duchu warunków rozważanych przez Thomasona i ich naprzemiennie globalnego i lokalnego charakteru, w 1989 roku Chung, Graham i Wilson rozważyli kilka słabszych warunków: wykres na wierzchołkach z krawędzią $\ displaystyle$$}$ gęstość i niektóre mogą spełnić każdy z tych warunków, jeśli $ε$$varepsilon > 0}$

• Rozbieżność : ${\ Displaystyle V = V (G)}$ dowolnych podzbiorów zbioru wierzchołków $)$ , liczba krawędzi między $X}$ a ${ \displaystyle$${\ displaystyle p | X||Y|}$$}$ mieści p .
• Rozbieżność w poszczególnych zestawach : dla dowolnego podzbioru V $liczba$$\ displaystyle V}$ krawędzi między ${\ displaystyle X}$ mieści się w zakresie $} X {\ displaystyle X}$${\ Displaystyle p {\ binom {| X | {2}}}$ .
• Liczenie podgrafów : dla każdego wykresu liczba oznaczonych kopii pośród podwykresów ${\ displaystyle G}$$mieści$$się$ n $Displaystyle \ varepsilon n ^ {v (H)}}$ p $\ Displaystyle p ^ {e (H)} n ^ {v (H)}}$ .
• 4-cyklowe liczenie : liczba oznaczonych cykli ${\ Displaystyle 4}$$-cykli$ między podgrafami mieści się w zakresie 4 $} styl wyświetlania p^{4}n^{4}}$${\ Displaystyle \ varepsilon n ^ {4}$ .
• Co degree : pozwalając ${\ Displaystyle \ operatorname {codeg} (u, v)}$ być liczbą wspólnych sąsiadów dwóch wierzchołków $v$ { $displaystyle v}$

${\ Displaystyle \ suma _ {u, v \ w V} {\ duży |} \ nazwa operatora {codeg} (u, v) -p ^ {2} n {\ duży |} \ równoważnik \ varepsilon n ^ {3} .}$

• Ograniczenie wartości własnej : Jeśli ${\ Displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}}$ wartościami własnymi macierzy sąsiedztwa , a następnie ${\ displaystyle$$($ w i ${\ Displaystyle$$\ varepsilon n}$ sol ${\ Displaystyle \ max \ lewo (\ lewo | \ lambda _ {2} \ prawo |, \ lewo | \ lambda _ {n} \ prawo | \ prawo) \ równoważnik \ varepsilon n}$ .

$jest$ te warunki można przedstawić za pomocą sekwencji grafów $,$ gdzie na wierzchołkach $z$${\ Displaystyle (p + o (1)} {\ binom {n} {2}}}$ krawędzie. Na przykład warunek liczenia 4 cykli polega na tym, że liczba kopii dowolnego wykresu ${\ displaystyle H}$ sol ${\ Displaystyle G_ {n}}$ jest $lewo (p ^ {e (H)} + o (1) \ prawo ) e ^ {v (H)}}$ jako ${\ Displaystyle n \ do \ infty}$ , a warunek rozbieżności staje się ${\ Displaystyle \ lewo | e (X, Y) -p | X | | Y | \ prawo | = o (n ^ {2})}$ , używając notacji little-o .

Kluczowym wynikiem dotyczącym pseudolosowości wykresu jest twierdzenie Chunga – Grahama – Wilsona , które stwierdza, że ​​​​wiele z powyższych warunków jest równoważnych, aż do zmian $wielomianu$ . Sekwencję grafów spełniającą te warunki nazywamy quasi-losową . Uważa się za szczególnie zaskakujące, że słaby warunek posiadania „prawidłowej” gęstości 4 cykli implikuje inne pozornie znacznie silniejsze warunki pseudolosowości. Grafy takie jak 4-cyklowy, których gęstość w sekwencji grafów jest wystarczająca do przetestowania quasi-losowości sekwencji, są znane jako wymuszanie wykresów .

Niektóre implikacje twierdzenia Chunga – Grahama – Wilsona są jasne dzięki definicjom warunków: rozbieżność w warunku poszczególnych zbiorów jest po prostu szczególnym przypadkiem warunku rozbieżności dla ${\ displaystyle Y = X}$ i 4 cykli liczenie jest szczególnym przypadkiem liczenia podgrafów. Ponadto lemat o liczeniu grafów, proste uogólnienie lematu o liczeniu trójkątów , implikuje, że warunek rozbieżności implikuje liczenie podgrafów.

Fakt, że liczenie 4-cyklowe implikuje warunek współstopnia, można udowodnić za pomocą techniki podobnej do metody drugiego momentu. Po pierwsze, suma współstopni może mieć górną granicę:

${\ Displaystyle \ suma _ {u, v \ w G} \ nazwa operatora {codeg} (u, v) = \ suma _ {x \ w G} \ deg (x) ^ {2} \ geq n \ lewo ({{ \frac {2e(G)}{n}}\right)^{2}=\left(p^{2}+o(1)\right)n^{3}.}$

Biorąc pod uwagę 4 cykle, suma kwadratów współstopni jest ograniczona:

${\ Displaystyle \ suma _ {u, v} \ nazwa operatora {codeg} (u, v) ^ {2} = {\ tekst {Liczba oznaczonych kopii}} C_ {4} + o (n ^ {4}) \leq \left(p^{4}+o(1)\right)n^{4}.}$

Dlatego daje nierówność Cauchy'ego-Schwarza

${\ Displaystyle \ suma _ {u, v \ w G} | \ nazwa operatora {codeg} (u, v) -p ^ {2} n | \ równoważnik n \ lewo (\ suma _ {u, v \ w G} \left(\operatorname {codeg} (u,v)-p^{2}n\right)^{2}\right)^{1/2},}$

które można rozszerzyć, używając naszych granic w pierwszym i drugim momencie ${\ displaystyle \ operatorname {codeg}},$ aby uzyskać pożądane ograniczenie. Dowód, że warunek współstopnia implikuje warunek rozbieżności, można przeprowadzić za pomocą podobnego, choć trudniejszego, obliczenia obejmującego nierówność Cauchy'ego-Schwarza.

$,$$,$ że liczba oznaczonych 4-cykli w wynika aż do cykle, ${\ Displaystyle \ operatorname {tr} \ lewo (A_ {G} ^ {4} \ prawej)}$ , gdzie ${\ Displaystyle A_ {G}}$ jest macierzą sąsiedztwa ${\ Displaystyle G}$ . Następnie można wykazać, że te dwa warunki są równoważne, odwołując się do twierdzenia Couranta – Fischera .

Powiązania z regularnością wykresu

Koncepcja grafów, które zachowują się jak grafy losowe, silnie łączy się z koncepcją regularności grafów używaną w lemacie o regularności Szemerédiego . Dla $\ Displaystyle \ varepsilon > 0}$ { $ZA$ para zestawów wierzchołków ${\ Displaystyle A \ podzbiór X, B \ podzbiór Y}$$-regular$ jeśli dla satysfakcjonujący ${\ Displaystyle | A | \ geq \ varepsilon | X |, | B | \ geq \ varepsilon | Y |}$ , utrzymuje, że

${\ Displaystyle \ lewo | d (X, Y) -d (A, B) \ prawo | \ równoważnik \ varepsilon,}$

gdzie $)}$ Displaystyle d (X, $X}$ oznacza gęstość krawędzi między a $Displaystyle$ : liczba krawędzi między ${ \$ a ${ \displaystyle Y}$ podzielone przez ${\ Displaystyle | X||Y|}$ . Warunek ten implikuje $dwudzielny$$,$ że ​​​​krawędzie między i zachowują w sposób „losowy”. Ponadto Miklós Simonovits i Vera T. Sós wykazali w 1991 r., Że wykres spełnia powyższe warunki słabej pseudolosowości użyte w twierdzeniu Chunga – Grahama – Wilsona wtedy i tylko wtedy, gdy posiada podział Szemerédiego, w którym prawie wszystkie gęstości są bliskie gęstość krawędzi całego grafu.

Rzadka pseudolosowość

Analogi twierdzeń Chunga-Grahama-Wilsona

Twierdzenie Chunga – Grahama – Wilsona, w szczególności implikacja liczenia podgrafów z rozbieżności, nie dotyczy sekwencji grafów o gęstości krawędzi zbliżającej się $lub$ , na przykład, powszechnego przypadku ${\ displaystyle d}$ regularne wykresy na $wierzchołkach$ jako $n \ do \ infty}$ . Powszechnie rozważa się następujące rzadkie analogi warunków brzegowych rozbieżności i wartości własnych:

• Rzadka rozbieżność : dla dowolnych podzbiorów zbioru wierzchołków $\$$Displaystyle V = V (G)}$$\ Displaystyle Y$ liczba krawędzi między $Displaystyle X}$ a ${\ Displaystyle {\ Frac {d} {n}} | X||Y|}$ mieści $zakresie$ w .
• $_$ ograniczenie Jeśli _ macierz sąsiedztwa , a następnie $\lambda _{n}\right|\right)\leq \varepsilon d}$${\ Displaystyle \ max \ lewo (\ lewo | \ lambda _ {2} \ prawo |, \$$lewo$ .

Ogólnie prawdą jest, że ten warunek wartości własnej implikuje odpowiedni warunek rozbieżności, ale odwrotność nie jest prawdziwa: rozłączny związek losowego dużego $wykresu$ i za ${\ displaystyle d + 1}$ - pełny wykres $wierzchołków$ ma dwie wartości własne dokładnie, prawdopodobnie spełnia właściwość rozbieżności. Jednak, jak udowodnili David Conlon i Yufei Zhao w 2017 $wykresów$ ., Niewielkie warianty rozbieżności i warunków wartości własnej dla -regularnych Cayleya są równoważne aż do liniowego skalowania w ${\ displaystyle \ varepsilon}$ . Jeden kierunek tego wynika z lematu mieszania ekspandera , drugi wymaga założenia, że ​​graf jest grafem Cayleya i wykorzystuje nierówność Grothendiecka .

Konsekwencje ograniczenia wartości własnych

ZA $d}$${$ \ } $\ displaystyle$ wykres wierzchołkach nazywa się $n$ pozwalając wartościom własnym $sąsiedztwa$ być ${\ Displaystyle d = \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}} , max$ ( $Displaystyle \max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \lambda }$ . Granica Alona -Boppany daje, że ${\ Displaystyle \ max \ lewo (\ lewo | \ lambda _ {2} \ prawo |, \ lewo | \ lambda _ {n} \ prawo | \ prawo) \ geq 2 {\ sqrt {d- 1}} -o (1)}$$Displaystyle$ termin jest taki jak $n \ do \ infty} ), a Joel$ udowodnił, że losowy $}$${ \ displaystyle$$wierzchołkach$ - regularny wykres na to ${\ Displaystyle (n, d, \ lambda)}$ dla ${\ Displaystyle \ lambda = 2 {\ sqrt {d-1}} + o (1)}$ . W tym sensie $jest$ ile $przekracza$ , ogólną Istnieją wykresy z ${\ Displaystyle \ lambda \ równoważnik 2 {\ sqrt {d-1}}}$ , które nazywane są grafami Ramanujana . Zostały one szeroko zbadane i istnieje wiele otwartych problemów związanych z ich istnieniem i powszechnością.

Biorąc pod uwagę $małych ,$ wiele standardowych teoretycznych wielkości grafów do wartości zbliżonych do tego, czego można by się spodziewać po losowym $Displaystyle \ lambda$ wykres. W szczególności rozmiar $podzbioru$ poprzez lemat mieszania ekspandera. Inne przykłady są następujące, pozwalając być an $}$${\ Displaystyle (n, d, \ lambda)}$ wykres:

• Jeśli $\ Displaystyle d \ leq {\ Frac {n} {2}}}$${\ Displaystyle \ kappa (G) \ geq d - {\ Frac {36 \ lambda ^ {2}} {d}}.}$$\$ -łączność spełnia κ ( sol $kappa (G)}$
• Jeśli $lambda \ równoważnik d-2}$$\ Displaystyle$ , $G}$ jest połączony krawędziowo . Jeśli $parzysta$ , $zawiera$ idealne
• Maksymalne cięcie wynosi najwyżej $}$${\ Displaystyle {\ Frac {n (d + \ lambda)} {4}$ .
• Największy niezależny ${\ Displaystyle {\ Frac {n} {2 (d- \ lambda)}} \ ln \ lewo ({\ Frac {| U | (d- \ lambda)} {n (\ lambda +1)}} + 1 \Prawidłowy).}$ podzbioru w $)$$rozmiar$ co
• Liczba chromatyczna $wynosi$${\ Displaystyle {\ Frac {6 (d- \ lambda)} {\ ln \ lewo ({\ Frac {d + 1} {\ lambda + 1}} \ prawej)}}.}$ najwyżej re

Powiązania z twierdzeniem Greena – Tao

Wykresy pseudolosowe odgrywają ważną rolę w dowodzie twierdzenia Greena – Tao . Twierdzenie jest udowodnione przez przeniesienie twierdzenia Szemerédiego , stwierdzenia, że ​​​​zbiór dodatnich liczb całkowitych o dodatniej gęstości naturalnej zawiera dowolnie długie ciągi arytmetyczne, do rzadkiego ustawienia (ponieważ liczby pierwsze mają gęstość naturalną ${\ displaystyle 0}$ w liczbach całkowitych). Przeniesienie do zbiorów rzadkich wymaga, aby zbiory zachowywały się pseudolosowo, w tym sensie, że odpowiednie grafy i hipergrafy mają odpowiednią gęstość podgrafów dla pewnego ustalonego zbioru małych (hiper) podgrafów. Następnie pokazano, że odpowiedni nadzbiór liczb pierwszych, zwany liczbami pseudopierwszymi, w których liczby pierwsze są gęste, spełnia te warunki pseudolosowości, kończąc dowód.