Niezwykle wydajne pod względem przestrzeni niewyważone ekspandery przemysłowe

24

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 taki wykres dla i . Jednak trzebaG=(A,B,E)| B | = m d ( k , ϵ ) S A k S B ( 1 - ϵ ) d | S | d = O ( log ( n / k ) / ϵ ) m = O ( k log ( n / k ) / ϵ 2 ) O (|A|=n|B|=md(k,ϵ)SAkSB(1ϵ)d|S|d=O(log(n/k)/ϵ)m=O(klog(n/k)/ϵ2)O(nd)przestrzeń do przechowywania takiego wykresu. Trzeba także uzyskać dostęp do tego magazynu, robiąc cokolwiek z wykresem, co również może kosztować. Idealnie byłoby mieć wyraźną konstrukcję. Jednak, o ile mi wiadomo, znane konstrukcje osiągają parametry, które są nadal nieco dalekie od powyższego (przynajmniej możliwe do udowodnienia).

Moje pytanie: czy są jakieś inne konstrukcje, być może nieprecyzyjne, które osiągają granice „bliżej” do tych powyżej, ale wykorzystują „znacznie mniej” niż przestrzeń ?O(nd)

Szukam odpowiedzi w jednej z tych trzech kategorii: (a) twierdzenia (b) przypuszczenia (c) obserwacje i „historie wojenne”, takie jak: „zrobiliśmy to i wydawało się, że zadziałało (tak jakby)”. Tj. Ekspandery „przemysłowe” są w porządku. Wolę (a) niż (b) i (b) niż (c), ale żebracy nie mogą wybierać :)

Oto przykład konstrukcji typu (c). Weź losowe liniowe funkcje skrótu (mod ) i połącz każdy wierzchołek z . Ja i mój uczeń przeprowadziliśmy na nim kilka eksperymentów i wydawało się, że działa „dobrze”. Czy są jakieś twierdzenia lub przypuszczenia na temat tej lub powiązanych konstrukcji?h i : [ n ] [ m ] m i h 1 ( i ) h d ( i )dhi:[n][m]mih1(i)hd(i)

Dzięki!

Piotr
źródło
2
To świetne pytanie, ale wydaje się, że nie ma odpowiedzi! Czy nikt nie używa ekspanderów innych niż magiczna różdżka, aby dowody działały? Myślałem, że niektóre typy grafów Ramanujana są dość proste do skonstruowania.
András Salamon,
2
Wykresy Ramanujana są rzeczywiście stosunkowo łatwe do skonstruowania, ale są zrównoważone , tj. M = n.
Piotr
Czy obejrzałeś konstrukcję Guruswami-Umans-Vadhan? Zastanawiam się, dlaczego nie spełnia twoich wymagań.
Zeyu

Odpowiedzi:

10

Eickmeyer i Grohe (2010) udowadniają, że twoja kandydująca konstrukcja może być jednoznaczna: weź nieco liniowo niezależne liniowe funkcje skrótu i połącz lewe wierzchołki z prawymi wierzchołkami . Eickmeyer i Grohe pokazują, że ta konstrukcja daje -rozszerzenia z lewym stopniem , ilekroć jest liczbą całkowitą, lewy zestaw wierzchołków ma rozmiar , prawy zestaw wierzchołków ma rozmiar , a jest siłą pierwszą. Funkcje skrótu są wybierane w taki sposób, aby dowolneh 1 , , h d v h 1 ( v ) , , h d ( v ) ( k , ϵ ) d = k ( t - 1 ) / ( 2 ϵ ) t n = q t m = d q q > d h 1 , , h d tdh1,,hdvh1(v),,hd(v)(k,ϵ)d=k(t1)/(2ϵ)tn=qtm=dqq>dh1,,hdt z nich jest liniowo niezależnych.

Holger
źródło
5

Pomyślałem, że rzucić okiem na ankiety / rozmowy Aviego Wigdersona mogą pomóc w twoim pytaniu. Oto slajdy z ostatniego przemówienia: Samouczek ekspandera, czerwiec 2010 r . Konstrukcje zaczynają się na stronie 40.

Jeśli chodzi o złożoność przestrzeni, myślę, że może być pomocne, jeśli określisz operacje, które musisz wykonać na wykresie. Jeśli się nie mylę, niektóre konstrukcje umożliwiają działanie takie jak obliczanie sąsiedztwa w przestrzeni logów.

Kaveh
źródło