Pytania otagowane jako spectral-graph-theory

4
Dowody uzyskane jedynie za pomocą teorii grafów spektralnych
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 …
2
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 | / 2G=(V,E)G=(V,E)G=(V,E)dddSSS≤|V|/2≤|V|/2\leq |V|/2SSS ϕ(S):=Edge s ( S, V- S)re⋅ | S.| ⋅ | V.- S|ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|} Gdzie jest liczbą krawędzi z jednego punktu końcowego …
2
Czy Cheeger jest stały -trwały?
Przeczytałem w niezliczonych artykułach, że wyznaczanie stałej Cheegera na wykresie to -hard. To wydaje się być twierdzeniem ludowym, ale nigdy nie znalazłem ani cytatu, ani dowodu na to stwierdzenie. Komu mam to przypisać? W starym artykule (Isoperimetric Numbers of Graphs, J. Comb. Theory B, 1989) Mohar potwierdza to twierdzenie „dla …
1
Obraz geometryczny za ekspanderami kwantowymi
( tutaj też nie ma odpowiedzi) (d,λ)(d,λ)(d,\lambda)νν\nuU(d)U(d)\mathcal{U}(d)|supp ν|=d|supp ν|=d|\mathrm{supp} \ \nu| =d∥EU∼νU⊗U†−EU∼μHU⊗U†∥∞≤λ‖EU∼νU⊗U†−EU∼μHU⊗U†‖∞≤λ\Vert \mathbb{E}_{U \sim \nu} U \otimes U^{\dagger} - \mathbb{E}_{U \sim \mu_H} U \otimes U^{\dagger}\Vert_{\infty} \leq \lambdaμHμH\mu_Hddd przez Harrow and Low. Moje pytanie brzmi - czy ekspandery kwantowe dopuszczają jakąkolwiek interpretację geometryczną podobną do ekspanderów klasycznych (gdzie szczelina widmowa izoperymetria …
1
Próbkowanie z wielowymiarowego Gaussa z grafem kowariancji Laplaciana (odwrotna)
Wiemy np. Z Koutis-Miller-Peng (na podstawie pracy Spielmana i Tenga), że możemy bardzo szybko rozwiązać układy liniowe dla macierzy które są wykresem macierzy Laplaciana dla niektórych rzadkich wykresów z nieujemnymi wagami krawędzi .Ax=bAx=bA x = bAAA Teraz (pierwsze pytanie) rozważ użycie jednej z tych grafów macierzy Laplaciana jako kowariancji lub …
2
Zastosowania teorii wykresów spektralnych w teorii informacji i kodowania
Chciałem dowiedzieć się, jakie są zastosowania SGT w dziedzinie informacji i teorii kodowania, a może komunikacji. Najbardziej związana, która przychodzi mi na myśl, to praca nad kodami ekspanderów Michael Sipser i Daniel Spielman, „Kody ekspanderów”, Transakcje IEEE dotyczące teorii informacji, tom 42, nr 6, s. 1710–1722. 1996 Inne przykłady?
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.