Ekspander jest rzadkim (niskiego stopnia) wykresem o dużej „rozszerzalności”, mierzonej na jeden z kilku sposobów; zwykle zbliżone do minimalnego stosunku wielkości granicy podgrafu do objętości podgrafu.
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...
Ostatnio uczyłem ekspanderów i wprowadziłem pojęcie grafów ramanujańskich. Michael Forbes zapytał, dlaczego tak się nazywają, i musiałem przyznać, że nie wiem.
Lemma regularności Szemerediego mówi, że każdy gęsty wykres może być aproksymowany jako połączenie O ( 1 )O(1)O(1) wielu dwustronnych grafów ekspanderów. Dokładniej, istnieje podział większości wierzchołków na zestawy O ( 1 )O(1)O(1) tak że większość par zestawów tworzy dwustronne ekspandery...
Szukam niezrównoważonych ekspanderów, które są „dobre” i „zajmują mało miejsca”. W szczególności dwustronny wykres lewostronny , , , z lewym stopniem jest rozszerzeniem jeśli dla dowolnego wielkości co najwyżej , liczba różnych sąsiadów w wynosi co najmniej. Wiadomo, że metoda probabilistyczna daje...
To pytanie jest inspirowane wielomianową hipotezą Hirscha (PHC). Biorąc pod uwagę -facet polytop w , czy szczelina widmowa jego wykresu wierzchołek-krawędź (nazwij to ) jest niższa ograniczona przez ? Zauważ, że wykres cyklu wierzchołków pokazuje, że nawet dla szczelina widmowa może być tak mała...
W prezentacji z 2006 r. Zatytułowanej WYKRESY EKSPANDERA - CZY POZOSTAJĄ ŻADNE TAJEMNICE? Nati Linial postawił następujący otwarty problem: Które -hard obliczeniowa problemu na wykresie pozostają trudne, gdy ogranicza się do wykresów ekspandera?NPNPNP Od tego czasu postęp poczyniono udowodnić...
G=(V,E)G=(V,E)G=(V,E)minS⊂V e(S,Sc)min(|S|,|Sc|),minS⊂V e(S,Sc)min(|S|,|Sc|),\min_{S \subset V} ~\frac{e(S,S^c)}{\min(|S|,|S^c|)},e(S,Sc)e(S,Sc)e(S,S^c)SSSScScS^c Bardziej konkretnie przypuszczać wiem średnica wynosi co najmniej (albo co najwyżej) . Co to mówi mi o przewodności, jeśli w ogóle? I...
Dowód omer Reingold, że daje algorytm USTCON (W U ndirected wykres ze szczególnym wierzchołki s i t są one Con podłączeń z sieciami?) Za pomocą tylko logspace. Podstawową ideą jest zbudowanie wykresu ekspandera z oryginalnego wykresu, a następnie przejście do wykresu ekspandera. Wykres ekspandera...
Powiedzmy, że rodzina grafów ma długo indukowane ścieżki, jeśli istnieje stała ϵ > 0, tak że każdy wykres G w F zawiera ścieżkę indukowaną na | V ( G ) | ϵ wierzchołki. Interesują mnie właściwości rodzin grafów, które zapewniają istnienie długo indukowanych ścieżek. W szczególności zastanawiam...
Załóżmy, że jeden ma losowy (BPP) algorytm ZAAA przy użyciu rrr bitów przypadkowości. Istnieją naturalne sposoby na zwiększenie prawdopodobieństwa sukcesu do 1 - δ1−δ1-\delta dla każdego wybranego δ> 0δ>0\delta>0 Niezależne przebiegi + większość głosów: przebieg ZAAA niezależnie T.= Θ (...
Interesują mnie kombinatoryczne właściwości sieci społecznościowych w postaci grafów. Ludzie patrzyli na takie rzeczy, jak rozkład stopni, współczynnik grupowania i ściśliwość tych wykresów. Jedno podstawowe pytanie brzmi: czy te wykresy są zazwyczaj dobrymi wykresami ekspanderów? Czy ktoś...