Am nevoie să construiesc un grafic de expansiune regulat d pentru niște mici d fixe (cum ar fi 3 sau 4) de n vârfuri.
Ce este cea mai ușoară metodă de a face acest lucru în practică? Construirea unui grafic aleatoriu d-regulat, care sa dovedit a.a.s. un expansor?
Am citit și despre construcțiile Margulis și graficele Ramanujan care sunt expansoare și o construcție folosind un produs în zig-zag. Wikipedia oferă o prezentare generală frumoasă, dar foarte scurtă: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Dar ce metodă aleg în practică?
Pentru mine, aceste metode par toate foarte complicate de implementat și mai ales de înțeles și poate destul de specifice. Nu există metode mai ușoare, poate bazate pe permutări sau cam așa ceva, pentru a genera practic o secvență de grafice de expansiune d-regulate?
Este poate mai ușor să construiești grafice de expansiune b-partide d-regulate?
Am, de asemenea, o altă întrebare: Ce se întâmplă cu familiile de expansori d-regular răi? Are un sens o astfel de noțiune? Se poate construi o familie de grafice d-regular (care sunt bineînțeles conectate) care să fie cât mai rău posibil în sensul unui expansor?
Vă mulțumim anticipat.
Comentarii
- Există construcții explicite mai ușoare decât cele pe care le-ați enumerat , dar graficele aleatorii ar trebui să facă trucul și să aibă parametri mai buni.
- Poți da nume sau referințe ale construcțiilor? Prin parametri mai buni, înseamnă că o expansiune (de margine) mai bună, cred?
- Andr á s-a dat exemplul pe care îl aveam în minte, dar, în general, graficele aleatorii sunt (aproape întotdeauna) mai bune decât construcțiile explicite. Nu numai că extinderea marginii este mai mare, un y altă proprietate similară care este utilă pentru algoritmul dvs. este probabil satisfăcută automat de grafice aleatorii.
- Ok, pentru gradul 3, exemplul Andr á sau graficele aleatorii par a fi suficient de bune pentru aplicația mea. Ar fi interesant, în special în ceea ce privește graficele aleatorii, să se construiască o familie de grafice cu 3 reg, care nu este un expansor. Dar acest lucru este probabil foarte greu sau nu este posibil?
- Luați o uniune de $ K_4 $ s. Dacă doriți un grafic conectat, eliminați o margine din fiecare $ K_4 $ (formând un grafic cunoscut sub numele de grafic diamant) și conectați-le într-un ciclu.
Răspuns
Dacă nu vă deranjează graficele cu auto-bucle, familia „cea mai ușoară” de expander este probabil aceasta, oferind expansoare care sunt 3-regulate.
Începeți cu un număr prim $ p $ și construiți vârfuri numerotate de la $ 0 $ la $ p-1 $. Pentru fiecare vârf $ u \ ne 0 $, conectați $ u $ la $ u-1 $ și $ u + 1 $ , modulo $ p $. De asemenea, conectați $ u $ la vârful unic $ v $ astfel încât $ uv \ equiv 1 \ mod p $.
De exemplu, graficul cu 7 vârfuri din familie este un ciclu de 7 cu vârfuri numerotate secvențial în jurul ciclului; există autocicluri la 6 $, 0 $ și 1 $; în cele din urmă, există acorduri care unesc 3 $ și 5 $ și 2 $ și 4 $. >
Consultați https://mathoverflow.net/questions/124708/an-expander-graph pentru discuții suplimentare și referințe. Există o mulțime de indicii mai detaliate căutând pe ” expander „la CSTh eory , Math.SE și MO .
După cum subliniază Yuval Filmus, este posibil ca construcția aleatorie să dea rezultate mai bune în general, dar, desigur, nu poate produce un expansor (în special pentru grafice mici).
Comentarii
- Vă mulțumim pentru remarcă. Mai căutasem extindători pe celelalte site-uri, dar nu și pe MO, se pare că există mai multe rezultate.
Răspuns
Având în vedere un grafic regulat aleatoriu este un expansor whp (urmați referința dată în documentația codului MATLAB legat mai jos), am folosit odată următoarele: