Dokumenty do uznania za spektralny podział grafów

Jeśli jest nieukierunkowane -regular wykres i jest podzbiorem wierzchołków liczności , wywołać ekspansję krawędzi o o ilościd S ≤ | V | /$G=(V,E)$$d$$S$$\leq |V|/2$$S$

$\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|}$

Gdzie jest liczbą krawędzi z jednego punktu końcowego w i jednego punktu końcowego w . Następnie problemem rozszerzenia krawędzi jest znalezienie zestawu z który minimalizuje . Wywołaj rozszerzenie optymalnego zestawu.A $Edges(A,B)$$A$$B$| S | ≤ | V | / 2 ϕ ( S ) ϕ ( G $S$$|S|\leq |V|/2$$\phi(S)$$\phi(G)$

Widmowa podziału Algorytm do problemu rozszerzeń krawędź działa od stwierdzenia wektor własny z drugiej największej wartości własnej macierz przylegania do , i biorąc pod uwagę wszystkie `` zestawów progowe „” formy powyżej wszystkich progów . Jeśli pozwolimy, aby była drugą co do wielkości wartością własną macierzy , wówczas analiza algorytmu podziału spektralnego pokazuje, że najlepszy zestaw progów znaleziony przez algorytm spełniaA G S { v : x ( v ) ≤ t } t λ 2 $x$$A$$G$$S$$\{ v : x(v) \leq t \}$$t$$\lambda_2$SS$\frac 1d \cdot A$$S_{SP}$

$\phi(S_{SP}) \leq 2\sqrt {\phi(G)}$

Wynika to z nierówności Cheegera

$\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

i

$1-\lambda_2 \leq 2 \phi(G)$

Jaki jest pierwszy artykuł, który wysunął takie roszczenie? Jakie dokumenty mają przypisać pomysły? Oto co mam:

• N. Alon i VD Milman. , nierówności izoperymetryczne dla wykresów i superkoncentratory, Journal of Combinatorial Theory, Series B, 1985, 38 (1): 73-88 $\lambda_1$

  Udowodnij wynik w duchu „prostej” nierówności Cheegera , ale zamiast ekspansji wierzchołków zamiast ekspansji krawędzi. Uznaj, że związek między ekspansją krawędzi a wartościami własnymi jest dyskretną wersją problemu badanego przez Cheegera w $1-\lambda_2 \leq 2\phi(G)$

  J. Cheeger. Dolna granica najmniejszej wartości własnej Laplaciana. Problemy w analizie, 1970.

• N. Alon. Wartości własne i ekspandery. Combinatorica. 6 (2): 83–96, 1986.

  Udowadnia wynik w duchu trudnej nierówności Cheegera ale do rozszerzenia wierzchołków zamiast rozszerzenia krawędzi. $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

• A. Sinclair, M. Jerrum. Przybliżone liczenie, jednolite generowanie i szybkie mieszanie łańcuchów Markowa. Information and Computation 82: 93-133, 1989 (wersja konferencyjna 1987)

  Udowodnij nierówności Cheegera, jak wspomniano powyżej. (Ich praca bada przewodnictwo_ odwracalnych w czasie łańcuchów Markowa, które zdarzają się na równi z ekspansją krawędzi na regularnych wykresach). Za techniki przypisują pracę Alona i Milmana oraz Alona. Uznają również Aldousa za powiązaną granicę między czasem mieszania a rozszerzaniem krawędzi na zwykłych wykresach.

• M. Mihail. Przewodnictwo i zbieżność łańcuchów Markowa - kombinatoryczne leczenie ekspanderów. FOCS 1989, strony 526–531

  Chociaż głównym punktem pracy jest to, że jej techniki mają zastosowanie do nieodwracalnych w czasie łańcuchów Markowa, to gdy stosuje się ją do zwykłych grafów bezkierunkowych, ma ona przewagę nad poprzednimi pracami: pokazuje, że jeśli uruchomimy algorytm podziału widmowego z arbitralnym wektor, nadal uzyskuje się nierówność gdzie jest ilorazem Rayleigha wektora. Argumenty Alona, ​​Milmana, Sinclaira i Jerruma wymagają rzeczywistego wektora własnego. Jest to istotne w przypadku algorytmów szybkiego podziału widmowego, które wykorzystują przybliżone wektory własne. λ$\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda')}$$\lambda'$

Kiedy znaczenie algorytmiczne powyższych wyników, jako algorytmów podziału grafów, jest po raz pierwszy rozpoznawane? Powyższe artykuły nie mają takiej dyskusji.

Wydaje się, że pierwszym referatem wprowadzającym ten zestaw pomysłów (przy użyciu niezmiennika algebraicznego , drugiej najmniejszej wartości własnej wykresu Laplaciana, w celu powiązania różnych właściwości wykresu) do teorii grafów była „Algebraiczna łączność wykresów” Fiedlera w czechosłowackiej matematyce Dziennik. Pojawił się w 1973 roku, mniej więcej w tym samym czasie, co artykuł Cheegera (1970), który zajmował się rozmaitością. Nie jestem pewien, kto jako pierwszy zaobserwował podobieństwo między wykresami i rozmaitościami. jest czasem nazywana liczbą Fiedlera.λ $\lambda_2$$\lambda_2$

Co ciekawe, na końcu artykułu Fiedlera znajduje się uwaga, wskazująca na niezależny raport techniczny Andersona i Morleya zatytułowany Wartości własne Laplaciana na wykresie z 1971 r., Który najwyraźniej miał podobne pomysły. Jednak artykuł Andersona i Morleya o tym samym tytule ukazał się w Algebrze liniowej i wieloliniowej dopiero w 1985 roku.

Kilka dodatkowych odniesień, które pamiętam z tamtej epoki:

1) Diaconis i Stroock, Geometryczne granice wartości własnych łańcuchów Markowa, The Annals of Applied Probabil, 1991; ale pamiętam, jak kiedyś dostałem preprint w 1990 roku. To z kolei odnosi się do tego artykułu

2) Dodziuk, Równania różnicowe, nierówność izoperymetryczna i przemijalność niektórych losowych spacerów, Transactions of the American Mathematical Society, 1984.

Istotnym dokumentem „towarzyszącego algorytmu” dla Sinclaira i Jerruma w tym czasie był

3) Dyer Frieze Kannan, algorytm losowego wielomianu czasowego do aproksymacji objętości ciał wypukłych, STOC 89. Oczywiście, wyniki tutaj zostały zbudowane na SJ.