Ik moet d-regular expander graph construeren voor een kleine vaste d (zoals 3 of 4) van n hoekpunten.
Wat is de eenvoudigste methode om dit in de praktijk te doen? Het construeren van een willekeurige d-reguliere grafiek, waarvan is bewezen dat deze a.a.s. een expander?
Ik las ook over Margulis-constructies en Ramanujan-grafieken die expanders zijn en een constructie met een zigzagproduct. Wikipedia geeft een mooi maar heel kort overzicht: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Maar welke methode kies ik in de praktijk?
Voor mij lijken deze methoden allemaal erg ingewikkeld om te implementeren en in het bijzonder om te begrijpen en misschien wel heel specifiek. Zijn er geen gemakkelijkere methoden, misschien gebaseerd op permutaties of zo, om praktisch een reeks d-reguliere expander-grafieken te genereren?
Is het misschien gemakkelijker om d-reguliere bipartiete expander-grafieken te construeren?
Ik heb ook nog een andere vraag: hoe zit het met families van slechte d-reguliere expanders? Heeft zon idee zin? Kan iemand een familie van d-reguliere grafieken maken (die natuurlijk met elkaar verbonden zijn) die zo slecht mogelijk is in het gevoel van een expander?
Bij voorbaat dank.
Reacties
- Er zijn eenvoudiger expliciete constructies dan degene die je hebt genoemd , maar willekeurige grafieken zouden het moeten doen en betere parameters hebben.
- Kun je misschien namen of referenties van de constructies geven? Met betere parameters bedoel je een betere (rand) uitbreiding, denk ik?
- Andr á s gaf het voorbeeld dat ik in gedachten had, maar over het algemeen zijn willekeurige grafieken (bijna altijd) beter dan expliciete constructies. Niet alleen is de randuitbreiding groter, een y andere vergelijkbare eigenschap die nuttig is voor uw algoritme, wordt waarschijnlijk automatisch vervuld door willekeurige grafieken.
- Ok, voor graad 3, Andr á s voorbeeld of de willekeurige grafieken lijken goed genoeg te zijn voor mijn sollicitatie. Vooral met betrekking tot de willekeurige grafieken zou het interessant zijn om een 3-reg-grafiekfamilie te construeren die geen expander is. Maar dit is waarschijnlijk erg moeilijk of niet mogelijk?
- Neem een vereniging van $ K_4 $ s. Als je een verbonden grafiek wilt, verwijder dan een rand van elke $ K_4 $ (en vorm een grafiek die bekend staat als de diamantgrafiek), en verbind ze in een cyclus.
Antwoord
Als je het niet erg vindt om grafieken met self-loops te maken, is de “gemakkelijkste” expander-familie waarschijnlijk deze, die expanders geeft die 3-regular zijn.
Begin met een priemgetal $ p $, en construeer hoekpunten genummerd $ 0 $ tot $ p-1 $. Verbind voor elk hoekpunt $ u \ ne 0 $ $ u $ met $ u-1 $ en $ u + 1 $ , modulo $ p $. Verbind $ u $ ook met het unieke hoekpunt $ v $ zodat $ uv \ equiv 1 \ mod p $.
Als voorbeeld is de 7-hoekpuntgrafiek in de familie een 7-cyclus met hoekpunten opeenvolgend genummerd rond de cyclus; er zijn zelflussen op $ 6 $, $ 0 $ en $ 1 $; tenslotte zijn er akkoorden die aansluiten bij $ 3 $ en $ 5 $ en $ 2 $ en $ 4 $.
Zie https://mathoverflow.net/questions/124708/an-expander-graph voor verdere bespreking en referenties. Er zijn veel meer gedetailleerde aanwijzingen door te zoeken op ” expander “at CSTh eory , Math.SE , en MO .
Zoals Yuval Filmus opmerkt, geeft de willekeurige constructie in het algemeen waarschijnlijk betere resultaten, maar levert deze natuurlijk geen expander op (vooral voor kleine grafieken).
Opmerkingen
- Bedankt voor de opmerking. Ik had eerder naar expanders gezocht op de andere sites, maar niet op MO, er lijken echt meer resultaten te zijn.
Answer
Gegeven een willekeurige reguliere grafiek is een expander whp (volg de verwijzing in de documentatie van de MATLAB-code die hieronder is gelinkt), ik heb ooit het volgende gebruikt: