Jak praktycznie konstruować zwykłe wykresy ekspanderów?

14

Muszę skonstruować wykres ekspandera regularnego d dla niektórych małych stałych d (jak 3 lub 4) n wierzchołków.

Jaka jest najłatwiejsza metoda na zrobienie tego w praktyce? Konstruujesz losowy wykres d-regularny, który okazał się być ekspanderem?

Czytałem także o konstrukcjach Margulis i grafach Ramanujana, które są ekspanderami i konstrukcją wykorzystującą produkt zygzakowaty. Wikipedia podaje ładny, ale bardzo krótki przegląd: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Ale jaką metodę wybrać w praktyce?

Dla mnie te metody wydają się bardzo skomplikowane w implementacji, a szczególnie zrozumiałe i być może dość specyficzne. Czy nie istnieją łatwiejsze metody, być może oparte na permutacjach lub mniej więcej, w celu praktycznego wygenerowania sekwencji grafów d-regularnych ekspanderów?

Czy może łatwiej jest zbudować dwuczęściowe wykresy ekspanderów D-regular?

Mam też inne pytanie: co z rodzinami złych ekspanderów d-regular? Czy takie pojęcie ma sens? Czy można zbudować rodzinę grafów d-regularnych (które są oczywiście połączone), które są tak złe, jak to możliwe w sensie ekspandera?

Z góry dziękuję.

użytkownik2145167
źródło
2
Istnieją łatwiejsze konstrukcje jawne niż te, które wymieniłeś, ale losowe wykresy powinny załatwić sprawę i mieć lepsze parametry.
Yuval Filmus
Czy możesz podać nazwy lub odniesienia do konstrukcji? Wydaje mi się, że lepsze parametry oznaczają lepsze rozszerzenie (krawędź)?
user2145167
1
András podał przykład, który miałem na myśli, ale generalnie losowe wykresy są (prawie zawsze) lepsze niż wyraźne konstrukcje. Rozszerzenie krawędzi jest nie tylko większe, ale każda inna podobna właściwość, która jest pomocna w algorytmie, jest prawdopodobnie automatycznie zaspokajana przez losowe wykresy.
Yuval Filmus
Ok, dla stopnia 3 przykład Andrása lub losowe wykresy wydają się wystarczające do mojej aplikacji. Interesujące byłoby, szczególnie w odniesieniu do grafów losowych, skonstruowanie rodziny grafów 3-reg, która nie jest ekspanderem. Ale to prawdopodobnie bardzo trudne czy niemożliwe?
user2145167
3
Weź połączenie s. Jeśli chce podłączony wykresu usunąć jedną z krawędzi każdej K 4 (tworzących wykres zwany wykres diamentu) i połączyć je w cyklu. K4K4
Yuval Filmus,

Odpowiedzi:

9

Jeśli nie masz nic przeciwko wykresom z pętlami własnymi, „najłatwiejsza” rodzina ekspanderów to prawdopodobnie ta, oferująca ekspandery, które są 3-regularne.

Zacznij od jakiejś liczby pierwszej i konstruuj wierzchołki o numerach od 0 do p - 1 . Dla każdego wierzchołka u 0 połączyć u do u - 1 oraz u + 1 modulo p . Również połączyć u unikalnemu wierzchołka vp0p1u0uu1u+1puv tak, że .uv1modp

Na przykład wykres 7-wierzchołkowy w rodzinie to 7-cykl z wierzchołkami ponumerowanymi kolejno wokół cyklu; istnieją pętle własne dla , 0 i 1 ; wreszcie są akordy łączące 3 i 5 oraz 2601352 i .4

Zobacz /mathpro/124708/an-expander-graph celu dalszej dyskusji i odniesień. Istnieje wiele bardziej szczegółowych wskazówek, wyszukując hasło „expander” w CSTheory , Math.SE i MO .

Jak zauważa Yuval Filmus, losowa konstrukcja prawdopodobnie daje lepsze wyniki, ale oczywiście może nie dać ekspandera (szczególnie w przypadku małych wykresów).

András Salamon
źródło
Dziękuję za uwagę. Wcześniej szukałem ekspanderów na innych stronach, ale nie na MO, wydaje się, że naprawdę jest więcej wyników.
user2145167