D-regular bővítő gráfot kell készítenem n csúcs néhány kis fix d-jéhez (például 3 vagy 4).
Mi a legegyszerűbb módszer erre a gyakorlatban? Egy véletlenszerű d-szabályos gráf felépítése, amely bizonyítottan egyebek között van. bővítő?
Olvastam a Margulis-konstrukciókról és a Ramanujan-grafikonokról is, amelyek bővítők és cikk-cakk termék felhasználásával készült konstrukciók. A Wikipedia szép, de nagyon rövid áttekintést nyújt: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 De a gyakorlatban melyik módszert választom?
Számomra ezek a módszerek nagyon bonyolultnak tűnnek megvalósítani, és különösen megérteni, és talán meglehetősen specifikusak. Nincs egyszerűbb módszer, talán permutációk alapján, vagy hasonlóan, a d-regular bővítő grafikonok gyakorlatilag generálásához?
Lehet, hogy könnyebb elkészíteni a d-regular kétoldalas bővítő grafikonokat?
Van még egy kérdésem: Mi a helyzet a rossz d-regular bővítők családjaival? Van-e értelme egy ilyen elképzelésnek? Felépíthet-e egy olyan d-reguláris gráfcsaládot (amely természetesen kapcsolódik), amely a lehető legrosszabb a bővítő értelme?
Előre is köszönöm.
Megjegyzések
- Könnyebb explicit konstrukciók vannak, mint amiket felsoroltál , de a véletlenszerű grafikonoknak meg kell tenniük a trükköt, és jobb paraméterekkel kell rendelkezniük.
- Esetleg adhat neveket vagy hivatkozásokat a konstrukciókra? Jobb paraméterek alatt jobb (él) bővítést értesz, azt hiszem?
- Andr á s megemlítette a példát, amelyet gondoltam, de általában a véletlenszerű grafikonok jobbak (szinte mindig) jobbak, mint az explicit konstrukciók. Nemcsak az élkiterjedés nagyobb, an y más hasonló tulajdonság, amely hasznos az algoritmusához, valószínűleg véletlenszerű gráfokkal teljesül.
- Ok, a 3. fokozat esetében Andr á s példa vagy a véletlenszerű grafikonok úgy tűnik, hogy elég jó a jelentkezésemhez. Érdekes lenne, különös tekintettel a véletlenszerű grafikonokra, egy 3-reg gráfcsaládot létrehozni, amely nem bővítő. De ez valószínűleg nagyon nehéz vagy nem lehetséges?
- Vegyünk egy $ K_4 $ s uniót. Ha összekapcsolt grafikont szeretne, távolítson el egy élt minden $ K_4 $ -ból (képezzen egy gyémántgráf néven ismert gráfot), és kapcsolja össze őket egy ciklusban.
Válasz
Ha nem készít öngörbével ellátott grafikonokat, akkor valószínűleg ez a “legkönnyebb” bővítőcsalád, amely 3 szabályos bővítőket ad.
Kezdjen néhány $ p $ prímszámmal, és szerkessze a $ 0 $ – $ p-1 $ számú csúcsokat. Minden $ u \ ne 0 $ csúcshoz kösse össze a $ u $ -t a $ u-1 $ és $ u + 1 $ értékekkel. , modulo $ p $. Csatlakoztassa a $ u $ -ot az $ v $ egyedi csúcshoz is úgy, hogy $ uv \ equiv 1 \ mod p $.
Például a család 7-csúcsú grafikonja egy 7 ciklus, amelynek csúcsaival a ciklus körül egymás után számoznak; vannak $ 6 $, $ 0 $ és $ 1 $ önhurkok; végül vannak akkordok, amelyek összekapcsolják a $ 3 $ és $ 5 $, valamint a $ 2 $ és a $ 4 $ értékeket.
További beszélgetésekért és hivatkozásokért lásd: https://mathoverflow.net/questions/124708/an-expander-graph . Sok részletesebb mutató található a ” bővítő “a CSTh helyen eory , Math.SE és MO .
Ahogy Yuval Filmus rámutat, a véletlenszerű konstrukció valószínűleg általában jobb eredményeket fog hozni, de természetesen nem biztos, hogy bővítőt eredményez (különösen kis grafikonok esetében).
Megjegyzések
- Köszönöm a megjegyzést. Korábban már kerestem bővítőket a többi webhelyen, de a MO-n nem, úgy tűnik, hogy több az eredmény.
Válasz
Adott egy véletlenszerű szabályos gráf egy bővítő, whp (kövesse az alább hivatkozott MATLAB-kód dokumentációjában megadott hivatkozást), egyszer a következőket használtam: