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

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ę.

graph-theory combinatorics cryptography discrete-mathematics expanders użytkownik2145167
źródło

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

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

Weź połączenie

s. Jeśli chce podłączony wykresu usunąć jedną z krawędzi każdej

(tworzących wykres zwany wykres diamentu) i połączyć je w cyklu.

K_{4}

$K_4$

K_{4}

$K_4$

Yuval Filmus,

Odpowiedzi:

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 do . Dla każdego wierzchołka połączyć do oraz modulo . Również połączyć unikalnemu wierzchołka $p$ $0$ $p-1$ $u \ne 0$ $u$ $u-1$ $u+1$ $p$ $u$ $v$ tak, że . $uv \equiv 1 \mod p$

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 , i ; wreszcie są akordy łączące i oraz $6$ $0$ $1$ $3$ $5$ $2$ 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

Biorąc pod uwagę, że losowy wykres zwykły jest ekspanderem whp (postępuj zgodnie z odnośnikiem podanym w dokumentacji kodu MATLAB, do którego link znajduje się poniżej), kiedyś użyłem następującego:

http://www.mathworks.com/matlabcentral/fileexchange/29786-random-regular-generator/content/randRegGraph/createRandRegGraph.m

Hoda
źródło