Dowody uzyskane jedynie za pomocą teorii grafów spektralnych

28

Coraz bardziej interesuję się teorią wykresów spektralnych, co wydaje mi się fascynujące, i zacząłem zbierać kilka dokumentów, które muszę jeszcze przeczytać dokładniej niż dotychczas.

Jestem jednak ciekawy stwierdzenia, które pojawiło się w kilku źródłach (na przykład tam ), które mówi w istocie, że niektóre wyniki teorii grafów zostały udowodnione przy użyciu wyłącznie technik opartych na widmie i że jak dotąd nie ma dowodów na to, że omija te techniki są znane.

O ile tego nie pominąłem, nie przypominam sobie takiego przykładu w literaturze, którą czytałem do tej pory. Czy ktoś z was zna przykłady takich wyników?

— Anthony Labarre
źródło

Tytuł pytania sugeruje, że pytasz o dowody, które można uzyskać tylko za pomocą teorii grafów spektralnych, ale pytasz o dowody, które do tej pory były uzyskiwane tylko za pomocą teorii grafów spektralnych. To są dwa zupełnie różne pytania. Na obecnym etapie tytuł wprowadza w błąd i dlatego go zmieniłem.

— Dave Clarke

@Dave Zrobiłem wycofanie

— Suresh Venkat

5

Rozdział 7 Spectra of Graphs autorstwa Cvetkovića, Dooba i Sachsa podaje wiele przykładów twierdzeń, których stwierdzenia nie zawierają wyraźnej wzmianki o widmach, ale które można udowodnić za pomocą technik spektralnych. Domyślam się, że wiele z nich nie ma znanego dowodu nie-spektralnego, choć trzeba by to zweryfikować indywidualnie. Z pewnością w wielu przypadkach najprostszy lub najbardziej naturalny dowód wykorzystuje widma.

— Timothy Chow

@Timothy Chow: Dzięki, postaram się to zdobyć.

— Anthony Labarre,

@TimothyChow: Myślę, że powinieneś udzielić odpowiedzi.

— Suresh Venkat

12

Twierdzenie Hoffmana – Singletona .

— Colin McQuillan
źródło

Hoffman-Singleton też był moją pierwszą myślą. Ale nie wiem, czy istnieją jakieś nie-spektralne dowody, a jeśli nie, to dlatego, że są zbyt trudne lub dlatego, że nikt nie próbował. Standardowy dowód jest dość schludny i zwięzły, więc nie wiem od razu, jaka byłaby motywacja, aby uzyskać dowód nie widmowy.

— mhum,

9

Co powiesz na ten wynik obliczeń kwantowych.

Mario Szegedy. Kwantowe przyspieszenie algorytmów opartych na łańcuchu Markowa. W FOCS'04.

Rozciąga łańcuchy Markowa na kwantowe łańcuchy Markowa i pokazuje, że kwantowy czas uderzenia jest górny ograniczony pierwiastkiem kwadratowym klasycznego czasu uderzenia. Robi to poprzez powiązanie wektorów pojedynczych klasycznego łańcucha Markowa z wektorami osobliwymi kwantowego łańcucha Markowa. Przed tym opracowaniem nie istniała żadna znana relacja między spacerami losowymi i kwantowymi. Nie wyobrażam sobie, jak zrobić to samo, stosując techniki nie spektralne.

— Marcos Villagra
źródło

8

Myślę, że twierdzenie o przyjaźni (patrz także artykuł Huneke ) jest dobrym przykładem, chociaż ściśle mówiąc, istnieją obecnie dowody twierdzenia o przyjaźni, które unikają wartości własnych. Dowody, które całkowicie unikają wartości własnych, są znacznie bardziej nieporządne niż dowody spektralne.

(Twierdzenie o przyjaźni mówi, że jeśli w pokoju ludzi każda para ludzi ma dokładnie jednego wspólnego przyjaciela, to jest ktoś, kto zna wszystkich innych.)

— Timothy Chow
źródło

8

Niech będzie macierzą Laplaciana niekierowanego wykresu ważonego . Sparyfikator wykresu jest wykresem takim, że dla każdego zachowuje się następujące wartości: Stosując metody spektralne, Batson i in. pokaż, jak zbudować sparyzatory za pomocą krawędzi . $L_G$ $G = (V,E,w)$ $G$ $H$ $x \in R^V$

x^{T} L_{H} x (1 - ϵ) \leq x^{T} L_{G} x \leq x^{T} L_{H} x (1 + ϵ) .

$x^T L_H x (1-\epsilon) \le x^T L_G x \le x^T L_H x (1+\epsilon).$

O (n / ϵ^{2})

$O(n/\epsilon^2)$

Mimo że twierdzenie twierdzenia nie jest „z natury widmowe”, nie sądzę, aby wiadomo było, w jaki sposób można uzyskać ten wynik lub podobny wynik bez użycia technik spektralnych.

— Lew Reyzin
źródło

To trochę dyskusyjne, czy stwierdzenie nie jest z natury widmowe. W dosłownym sensie masz rację, ale jedyne uzasadnienie, jakie mogę wymyślić, dlaczego pojawia się forma kwadratowa, jest spektralne.

— Suresh Venkat

1

To jest rodzaj widmowego stwierdzenia. jest dokładnie wypukłym kadłubem wartości własnych A, jeśli A jest Laplacianem niekierowanego wykresu. Warunkiem jest prośba o kolejny wykres o mniej więcej tym samym widmie. Ale wydaje mi się, że nie wiadomo nawet, jak uzyskać inne stare spararyzatory z krawędziami w inny sposób.

F (A) = {x^{T} A x : | | x | |_{2} = 1}

$F(A) = \{x^TAx: ||x||_2 = 1\}$

O (n / ϵ^{2})

$O(n/\epsilon^2)$

— Aaron Roth,

Jasne - ale można sobie wyobrazić, że zdobędziemy te sparyfikatory w inny sposób. Ale tak, to może nie być najlepszy przykład ...

— Lew Reyzin