Jeg har brug for at konstruere d-regelmæssig udvidelsesgraf til nogle små faste d (som 3 eller 4) med n hjørner.
Hvad er den nemmeste metode til at gøre dette i praksis? Konstruktion af en tilfældig d-regulær graf, der er bevist at være a.a.s. en ekspander?
Jeg læste også om Margulis-konstruktioner og Ramanujan-grafer, der er ekspandere og en konstruktion, der bruger et zig-zag-produkt. Wikipedia giver en flot, men meget kort oversigt: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Men hvilken metode vælger jeg i praksis?
For mig virker disse metoder alle meget komplicerede at implementere og især at forstå og måske ret specifikke. Er der ikke lettere metoder, måske baseret på permutationer eller deromkring, til praktisk talt at generere en sekvens af d-regulære ekspandergrafer?
Er det måske lettere at konstruere d-regelmæssige bipartit-ekspandergrafer?
Jeg har også et andet spørgsmål: Hvad med familier med dårlige d-regulære udvidere? Er en sådan opfattelse fornuftig? Kan man konstruere en familie af d-regelmæssige grafer (som selvfølgelig er forbundet), der er så dårlige som muligt i fornemmelsen af en ekspander?
På forhånd tak.
Kommentarer
- Der er lettere eksplicitte konstruktioner end dem, du har angivet , men tilfældige grafer skal gøre tricket og have bedre parametre.
- Kan du måske give navne eller referencer til konstruktionerne? Ved bedre parametre mener du en bedre (kant) udvidelse, tror jeg?
- Andr á s gav det eksempel, jeg havde i tankerne, men generelt er tilfældige grafer (næsten altid) bedre end eksplicitte konstruktioner. Ikke kun er kantudvidelsen større, en y anden lignende egenskab, der er nyttig for din algoritme, bliver sandsynligvis automatisk tilfredsstillet af tilfældige grafer.
- Ok, for grad 3, Andr á s eksempel eller tilfældige grafer synes at være god nok til min ansøgning. Det ville være interessant, især med hensyn til tilfældige grafer, at konstruere en 3-reg graffamilie, der ikke er en ekspander. Men dette er sandsynligvis meget hårdt eller ikke muligt?
- Tag en sammenslutning på $ K_4 $ s. Hvis du vil have en tilsluttet graf, skal du fjerne en kant fra hver $ K_4 $ (danne en graf kendt som diamantgrafen) og forbinde dem i en cyklus.
Svar
Hvis du ikke har noget imod grafer med selvløkker, er den “nemmeste” udvidelsesfamilie sandsynligvis denne, hvilket giver udvidere, der er 3-regelmæssige.
Start med noget primtal $ p $, og konstruer hjørner nummereret $ 0 $ til $ p-1 $. For hvert toppunkt $ u \ ne 0 $ skal du forbinde $ u $ til $ u-1 $ og $ u + 1 $ , modulo $ p $. Tilslut også $ u $ til det unikke toppunkt $ v $ således at $ uv \ equiv 1 \ mod p $.
Som et eksempel er 7-toppunktgrafen i familien en 7-cyklus med hjørner nummereret sekventielt rundt om cyklussen; der er selvløkker på $ 6 $, $ 0 $ og $ 1 $; endelig er der akkorder, der slutter sig til $ 3 $ og $ 5 $, og $ 2 $ og $ 4 $.
Se https://mathoverflow.net/questions/124708/an-expander-graph for yderligere diskussion og referencer. Der er mange mere detaljerede henvisninger ved at søge på ” udvide “ved CSTh eory , Math.SE og MO .
Som Yuval Filmus påpeger, vil den tilfældige konstruktion sandsynligvis give bedre resultater generelt, men selvfølgelig giver det muligvis ikke en ekspander (især for små grafer).
Kommentarer
- Tak for bemærkningen. Jeg havde tidligere søgt på udvidere på de andre websteder, men ikke på MO, der synes virkelig at være flere resultater.
Svar
Når en tilfældig regelmæssig graf er en ekspanderende whp (følg henvisningen i dokumentationen til nedenstående MATLAB-kode), jeg brugte engang følgende: