Lemma regularności dla rzadkich wykresów

Lemma regularności Szemerediego mówi, że każdy gęsty wykres może być aproksymowany jako połączenie $O(1)$ wielu dwustronnych grafów ekspanderów. Dokładniej, istnieje podział większości wierzchołków na zestawy $O(1)$ tak że większość par zestawów tworzy dwustronne ekspandery (liczba zestawów w partycji i parametr rozszerzenia zależą od parametru aproksymacji):

http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma

Istnieją wersje tego lematu dla „dobrze zachowujących się” rzadkich wykresów, patrz np .:

http://www.estatistica.br/~yoshi/MSs/FoCM/sparse.pdf

http://people.maths.ox.ac.uk/scott/Papers/sparseregularity.pdf

To, co mnie zaskakuje w tych preparatach, to fakt, że gwarantują one jedynie, że większość par zestawów w partycjach tworzy dwustronne ekspandery, a te dwustronne ekspandery mogą być puste. Tak więc, ogólnie rzadkie wykresy, całkiem możliwe jest, że wszystkie krawędzie między różnymi częściami w podziale wierzchołków nie należą do ekspandera.

Zastanawiam się, czy istnieją formuły, które dają większość krawędzi między częściami z ekspandera, czy też nie ma nadziei na taką formułę.

graph-theory co.combinatorics expanders

— Dana Moshkovitz
źródło

ale czy nie wydaje się intuicyjne, że thm, który jest przeznaczony do gęstych wykresów, rozkłada się w jakiś sposób na rzadkich? zwróć uwagę, że odnośnik do wikipedii faktycznie nie mówi o grafach ekspanderów, co sugeruje, że może to być późniejsza interpretacja / sformułowanie ...

— vzn 24.12.12

(1) Zwykłym terminem określającym dobrze zachowujące się pary zestawów są „pary regularne” (w Wikipedii „para pseudolosowa”). Zastąpiłem go „ekspansjami dwustronnymi”, ponieważ uważam, że terminologia ta jest dla mnie bardziej naturalna. W każdym razie chodzi o to, że jeśli wybierzesz wystarczająco duże podzbiory z obu stron pary, liczba krawędzi między podzbiorami jest proporcjonalna do liczby krawędzi w parze. (2) Oczywiście to, co jest prawdziwe dla grafów gęstych, może przestać być prawdziwe dla grafów rzadkich. Moje pytanie dotyczy dokładnie zakresu, w jakim właściwości z gęstej skrzynki nadal zachowują się w rzadkiej obudowie.

— Dana Moshkovitz,

Poniżej znajduje się odpowiedź rozwlekły, ale tl; dr w ogólnym przypadku nie ma nadziei dla takiego preparatu, ale dla wielu z poszczególnych klas nielicznych wykresów, które mają prawidłowości lematy preparat ten nie istnieje.

W tle dostępne są dwie popularne wersje SRL. Są to: dla każdego stałego $\varepsilon > 0$ i dowolnego $n$ węzłowego wykresu $G = (V, E)$ , można podzielić $V = V_0 \cup V_1 \cup \dots \cup V_p$ na części $p = O_{\varepsilon}(1)$ , aby. ..

(Zwrot kombinatoryczny) (1) $|V_0| \le \varepsilon n$ i wymiary każdego $V_1, \dots, V_p$ różni się co najwyżej $1$ ( $V_0$ nazywa się "wyjątkowe zestaw") i (2) wszystkie ale $\varepsilon p^2$ pary pozostałych części $(V_i, V_j)$ spełniają
$| d (S, T) - d (V_{i}, V_{j}) | < ε for all S \subseteq V_{i}, T \subseteq V_{j}$ $\left|d(S, T) - d(V_i, V_j)\right| < \varepsilon \text{ for all } S \subseteq V_i, T \subseteq V_j$ (tutaj $d(\cdot, \cdot)$ daje gęstość między częściami, tj. część obecnych krawędzi).

$d i s c (V_{i}, V_{j}) := max_{S \subseteq V_{i}, T \subseteq V_{j}} | V_{i} | | V_{j} | | d (V_{i}, V_{j}) - d (S, T) |,$ $\mathop{disc}(V_i, V_j) := \max \limits_{S \subseteq V_i, T \subseteq V_j} |V_i||V_j|\left|d(V_i, V_j) - d(S, T)\right|,$ $\sum_{i, j = 0}^{p} d i s c (V_{i}, V_{j}) < ε n^{2} .$ $\sum \limits_{i, j =0}^p \mathop{disc}(V_i, V_j) < \varepsilon n^2.$

„Frazowanie kombinatoryczne” (właśnie wymyśliłem te nazwy, nie są one standardowe) jest oryginalne i prawdopodobnie bardziej znane, podczas gdy „frazowanie analityczne” jest bardziej nowoczesne i związane z limitami graficznymi itp. (Myślę, że zostało tutaj spopularyzowane). Moim zdaniem analitycznym jest właściwa formalizacja „wykresu przybliżonego przez połączenie ekspanderów dwudzielnych”, ponieważ daje kontrolę nad całkowitym „błędem” takiego przybliżenia i nie ma wyjątkowego zestawu, w którym można ukryć masę. Ale w tym momencie jest to po prostu kosmetyk, ponieważ jest łatwym, ale ważnym lematem, że te dwa wyrażenia są równoważne. Aby przejść od kombinatorycznego do analitycznego, po prostu związek przyczynił się do rozbieżności nieregularnych części i wyjątkowego zestawu. Aby przejść z Analitycznego na Kombinatorialny, wystarczy przesunąć dowolną część, która powoduje zbyt dużą rozbieżność do wyjątkowego zestawu i zastosować Nierówność Markowa, aby kontrolować jego masę.

Teraz rzadka regularność. Celem rzadki prawidłowość jest zastąpienie w odpowiednich nierówności o , w którym stanowi frakcję wszystkie możliwe krawędzie obecny w . Krytycznie, przy tej zmianie dwa sformułowania nie są już równoważne. Przeciwnie, frazowanie analityczne jest silniejsze: nadal sugeruje kombinatoryjne dokładnie tak jak poprzednio, ale kombinatoryjne zasadniczo nie implikuje analityczne, ponieważ (jak przewidziano w OP) potencjalnie można ukryć dużą gęstość w wyjątkowym zestawie lub między nieregularnymi pary części. W rzeczywistości ten podział jest formalny: dolne granice wykresów dla gęstej SRL (powiedzmy, ten $\varepsilon$ $\varepsilon d(G)$ $d(G)$ $G$ ) sugeruje, że frazowanie analityczne nie rozciąga się zasadniczo na grafy rzadkie, ale praca Scotta połączona w OP pokazuje, że frazowanie kombinatoryczne faktycznie obejmuje wszystkie rzadkie grafy bez żadnych warunków.

Ankieta połączona w PO mówi głównie o SRL dla rzadkich wykresów „o wyższej regularności”, co z grubsza oznacza, że wykres nie ma cięć gęstszych niż średnia o więcej niż stały czynnik. Dla tych konkretnych wykresów kombinacje kombinacyjne i analityczne są równoważne, ponieważ w wyjątkowych częściach nie może być ukryta zbyt duża masa, więc ich udział w rozbieżności może być ograniczony przez związek, jak w przypadku gęstym. Zatem wykresy te mają interpretację „przybliżoną przez połączenie ekspanderów dwustronnych”.

Na koniec powinienem wspomnieć, że w literaturze istnieje wiele innych hipotez, które również sugerują równoważność tych sformułowań. Na przykład Górna prawidłowość (zdefiniowana tutaj ) jest bardziej ogólna niż Górna regularność i wciąż wystarcza, aby sugerować równoważność. Jednak w przypadku tej klasy grafów i innych jestem świadomy jedynie powiązanych z nimi lematów o słabej regularności. $L_p$

— GMB
źródło

Przepraszam za nekromancję wątku - tak się złożyło, że było to zgodne z moją obecną, oświetloną recenzją, i pomyślałem, że podzielę się tym, co znalazłem.

— GMB