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| 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 (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ń ?
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 )
Dzięki!
Odpowiedzi:
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 tre h1,…,hd v h1(v),…,hd(v) (k,ϵ) d=k(t−1)/(2ϵ) t n=qt m=dq q>d h1,…,hd t z nich jest liniowo niezależnych.
źródło
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.
źródło