Muszę zbudować wykres ekspandera d-regularnego dla kilku małych ustalonych d (takich jak 3 lub 4) z n wierzchołków.
Co jest to najłatwiejsza metoda w praktyce? Skonstruowanie losowego d-regularnego wykresu, który okazał się być a.a.s. ekspander?
Czytałem również o konstrukcjach Margulis i wykresach Ramanujana, które są ekspanderami i konstrukcją z wykorzystaniem iloczynu zygzakowatego. Wikipedia daje przyjemny, ale bardzo krótki przegląd: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Ale jaką metodę wybrać w praktyce?
Dla mnie wszystkie te metody wydają mi się bardzo skomplikowane do wdrożenia, a zwłaszcza do zrozumienia i być może dość specyficzne. Czy nie ma prostszych metod, być może opartych na permutacjach lub czegoś podobnego, do praktycznego wygenerowania sekwencji d-regularnych grafów ekspanderów?
Czy może być łatwiej zbudować d-regularne dwudzielne grafy ekspanderów?
Mam też inne pytanie: A co z rodzinami złych ekspanderów d-regularnych? 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 tylko możliwe w sens ekspandera?
Z góry dziękuję.
Komentarze
- Istnieją prostsze konstrukcje jawne niż te, które wymieniłeś , ale losowe wykresy powinny załatwić sprawę i mieć lepsze parametry.
- Czy możesz podać nazwy lub odniesienia do konstrukcji? Lepsze parametry oznaczają, jak sądzę, lepszą (krawędziową) ekspansję?
- Andr á s podał przykład, który miałem na myśli, ale generalnie losowe wykresy są (prawie zawsze) lepsze niż jawne konstrukcje. Nie tylko rozszerzenie krawędzi jest większe, na y inna podobna właściwość, która jest pomocna dla twojego algorytmu, jest prawdopodobnie automatycznie spełniana przez losowe wykresy.
- OK, dla stopnia 3, przykład Andr á lub losowe wykresy wydaje się być wystarczająco dobry dla mojej aplikacji. Byłoby interesujące, zwłaszcza w odniesieniu do grafów losowych, skonstruowanie rodziny grafów 3-reg, która nie jest ekspanderem. Ale to prawdopodobnie bardzo trudne lub niemożliwe?
- Weź sumę $ K_4 $ s. Jeśli chcesz mieć połączony wykres, usuń jedną krawędź z każdego $ K_4 $ (tworząc wykres znany jako wykres diamentowy) i połącz je w cyklu.
Odpowiedź
Jeśli nie masz nic przeciwko wykresom z pętlami własnymi, najłatwiejszą rodziną ekspanderów jest prawdopodobnie ta, która zapewnia ekspandery, które są 3-regularne.
Zacznij od liczby pierwszej $ p $ i skonstruuj wierzchołki ponumerowane od $ 0 $ do $ p-1 $. Dla każdego wierzchołka $ u \ ne 0 $ połącz $ u $ z $ u-1 $ i $ u + 1 $ , modulo $ p $. Połącz także $ u $ z unikalnym wierzchołkiem $ v $ tak, aby $ uv \ equiv 1 \ mod p $.
Na przykład, 7-wierzchołkowy wykres w rodzinie to 7-cykl z wierzchołkami ponumerowanymi sekwencyjnie wokół cyklu; są pętle własne na 6 $, 0 $ i 1 $; wreszcie są akordy łączące 3 $ i 5 $ oraz 2 $ i 4 $.
Zobacz https://mathoverflow.net/questions/124708/an-expander-graph , aby zapoznać się z dalszą dyskusją i odniesieniami. Istnieje wiele bardziej szczegółowych wskazówek, wyszukując „ expander „at CSTh eory , Math.SE i MO .
Jak wskazuje Yuval Filmus, losowa konstrukcja prawdopodobnie da ogólnie lepsze wyniki, ale oczywiście może nie dać ekspandera (szczególnie w przypadku małych wykresów).
Komentarze
- Dziękuję za uwagę. Szukałem wcześniej ekspanderów w innych witrynach, ale nie w MO, naprawdę wydaje się, że jest więcej wyników.
Odpowiedź
Dany losowy, regularny wykres jest ekspanderem whp (postępuj zgodnie z odniesieniem podanym w dokumentacji kodu MATLAB, do którego link znajduje się poniżej), kiedyś użyłem następującego: