Lemma regularności Szemerediego mówi, że każdy gęsty wykres może być aproksymowany jako połączenie wielu dwustronnych grafów ekspanderów. Dokładniej, istnieje podział większości wierzchołków na zestawy 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łę.
źródło
Odpowiedzi:
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ε > 0 i dowolnego n węzłowego wykresu G = ( V, E) , można podzielić V.= V.0∪ V.1∪ ⋯ ∪ V.p na części p = 0ε( 1 ) , aby. ..
„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ε ε d( G ) re( G ) sol ) 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
źródło