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

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 trzeba$G=(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|=m$$d$$(k,\epsilon)$$S \subset A$$k$$S$$B$$(1-\epsilon)d|S|$$d=O(\log (n/k)/\epsilon)$$m=O(k \log(n/k)/\epsilon^2)$$O(n d)$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 $d$$h_i: [n] \to [m]$$m$$i$$h_1(i) \ldots h_d(i)$

Dzięki!

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$d$$h_1,\dots,h_d$$v$$h_1(v),\dots,h_d(v)$$(k,\epsilon)$$d=k(t-1)/(2\epsilon)$$t$$n=q^t$$m=dq$$q>d$$h_1,\dots,h_d$$t$ z nich jest liniowo niezależnych.

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.