Minun on rakennettava d-säännöllinen laajennuskuvaaja pienelle kiinteälle d: lle (kuten 3 tai 4) n: stä pisteestä.
Mitä on helpoin tapa tehdä tämä käytännössä? Rakennetaan satunnainen d-säännöllinen kaavio, joka on osoittautunut mm. laajennin?
Luin myös Margulis-rakenteista ja Ramanujan-kaavioista, jotka ovat laajentimia ja siksak-tuotetta käyttävästä rakentamisesta. Wikipedia antaa mukavan mutta hyvin lyhyen yleiskatsauksen: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Mutta minkä menetelmän valitsen käytännössä?
Minulle nämä menetelmät vaikuttavat olevan erittäin monimutkaisia toteuttaa ja erityisesti ymmärrettäviä ja ehkä melko tarkkoja. Eikö ole helpompia menetelmiä, jotka perustuvat ehkä permutaatioihin tai niin, käytännöllisesti katsoen generoida d-säännöllisten laajentajakaavioiden sekvenssi?
Onko d-säännöllisten kahdenvälisten laajennuskuvaajien rakentaminen ehkä helpompaa?
Minulla on myös toinen kysymys: Entä huonojen d-säännöllisten laajentimien perheet? Onko tällaisella käsitteellä järkevää? Voiko rakentaa d-säännöllisten kaavioiden perheen (joka on tietysti kytketty) niin huonoon kuin mahdollista laajentajan tunne?
Kiitos jo etukäteen.
Kommentit
- On olemassa yksinkertaisempia nimenomaisia rakenteita kuin luetellut , mutta satunnaiskaavioiden pitäisi tehdä temppu ja niillä on paremmat parametrit.
- Voitteko ehkä antaa nimiä tai viitteitä rakenteista? Paremmilla parametreilla tarkoitat parempaa (reuna) laajennusta, luulisin?
- Andr á s toi mieleeni esimerkin, mutta yleensä satunnaiskaaviot ovat (melkein aina) parempia kuin eksplisiittiset rakenteet. Ei vain reunan laajeneminen, an y muu vastaava ominaisuus, josta on hyötyä algoritmillesi, tyydytetään todennäköisesti satunnaiskaavioilla.
- Ok, asteen 3 Andr á -esimerkki tai satunnaiskaaviot. näyttävät olevan tarpeeksi hyviä hakemukselleni. Olisi mielenkiintoista, erityisesti satunnaiskaavioiden suhteen, rakentaa 3-reg-kaavio-perhe, joka ei ole laajennin. Mutta tämä on todennäköisesti erittäin vaikeaa tai ei mahdollista?
- Valitse $ K_4 $ s: n yhdistys. Jos haluat yhdistetyn kaavion, poista yksi reuna kustakin $ K_4 $: sta (muodostaen kaavion, joka tunnetaan nimellä timanttikaavio), ja yhdistä ne jaksossa.
Vastaa
Jos et piilota kuvaajia itsesilmukoilla, ”helpoin” laajenninperhe on luultavasti tämä, jolloin laajentimet ovat 3-säännöllisiä.
Aloita joillakin alkuluvulla $ p $ ja rakenna pisteet, jotka on numeroitu $ 0 $ – $ p-1 $. Yhdistä jokaiselle kärjelle $ u \ ne 0 $ jokaisen pisteen $ u \ ne 0 $ kohdalle $ u $ – $ u-1 $ ja $ u + 1 $ , modulo $ p $. Yhdistä myös $ u $ ainutlaatuiseen kärkeen $ v $ siten, että $ uv \ equiv 1 \ mod p $.
Esimerkiksi perheen seitsemän kärjen kaavio on 7-sykli, jonka kärjet on numeroitu peräkkäin syklin ympäri; $ 6 $: lla, $ 0 $: lla ja $ 1 $: lla on itsesilmukat; lopuksi on sointuja, jotka yhdistävät $ 3 $ ja $ 5 $ sekä $ 2 $ ja $ 4 $. >
Katso lisätietoja kohdasta https://mathoverflow.net/questions/124708/an-expander-graph jatkokeskusteluja ja viitteitä varten. Haulla ”on paljon yksityiskohtaisempia viitteitä” laajennin ” CSTh eory , Math.SE ja MO .
Kuten Yuval Filmus huomauttaa, satunnainen rakenne antaa todennäköisesti parempia tuloksia yleensä, mutta ei tietenkään välttämättä tuota laajenninta (varsinkaan pienille kuvaajille).
Kommentit
- Kiitos huomautuksesta. Olin etsinyt laajentimia aiemmin muilta sivustoilta, mutta en MO: lta, tuloksia näyttää olevan enemmän.
Vastaa
Koska satunnainen säännöllinen kaavio on laajennin, whp (noudata alla linkitetyn MATLAB-koodin ohjeissa annettuja viitteitä), käytin kerran seuraavaa: