Pytania otagowane jako expanders

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.

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 …
1
Lemma regularności dla rzadkich wykresów
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 (liczba zestawów w partycji i parametr rozszerzenia zależą od parametru …
2
Trudne problemy NP na grafach ekspanderów?
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ć taki wynik dla -hard problemu?NPNPNP
1
Przewodnictwo i średnica na zwykłych wykresach
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 odwrotnie, przypuśćmy, że wiem, że przewodnictwo wynosi co najmniej (lub przynajmniej) . Co to mówi mi o średnicy, jeśli w ogóle?DDDαα\alpha
1
Jakie są przeszkody w przedłużeniu
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 jest tworzony przez wielokrotne kwadratowe obliczenie …
1
Deterministyczna redukcja błędów, najnowocześniejszy?
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.= Θ ( log( 1 / δ)T=Θ(log⁡(1/δ)T=\Theta(\log(1/\delta) razy ) i przyjmowanie większości głosów …
1
Istnienie długo indukowanych ścieżek na wykresach ekspanderów
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 się obecnie, czy …
2
Czy sieci społecznościowe są zwykle dobrymi ekspansorami?
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ś sprawdził, powiedzmy, lukę spektralną wykresu na Facebooku? Lub luka widmowa innych dużych sieci …
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.