Jeg trenger å konstruere d-vanlig utvidelsesgraf for noen små faste d (som 3 eller 4) med n-toppunktene.
Hva er den enkleste metoden å gjøre dette i praksis? Konstruere en tilfeldig d-vanlig graf, som er bevist å være a.a.s. en utvidelse?
Jeg har også lest om Margulis-konstruksjoner og Ramanujan-grafer som er utvidere og en konstruksjon som bruker et sikksakkprodukt. Wikipedia gir en fin, men veldig kort oversikt: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Men hvilken metode velger jeg i praksis?
For meg virker disse metodene veldig kompliserte å implementere og spesielt å forstå og kanskje ganske spesifikke. Er det ikke enklere metoder, kanskje basert på permutasjoner eller så, for å praktisk talt generere en sekvens av d-vanlige ekspandergrafer?
Er det kanskje lettere å konstruere d-vanlige tosidige ekspandergrafer?
Jeg har også et annet spørsmål: Hva med familier med dårlige d-vanlige utvidere? Har en slik forestilling mening? Kan man konstruere en familie med d-vanlige grafer (som selvfølgelig er koblet sammen) som er så ille som mulig i følelsen av en utvidelse?
På forhånd takk.
Kommentarer
- Det er lettere eksplisitte konstruksjoner enn de du listet opp , men tilfeldige grafer skal gjøre susen og ha bedre parametere.
- Kan du kanskje gi navn eller referanser til konstruksjonene? Ved bedre parametere mener du en bedre (kant) utvidelse, antar jeg?
- Andr á s ga eksemplet jeg hadde i tankene, men generelt er tilfeldige grafer (nesten alltid) bedre enn eksplisitte konstruksjoner. Ikke bare er kantutvidelsen større, en y annen lignende egenskap som er nyttig for algoritmen din, blir sannsynligvis automatisk tilfredsstilt av tilfeldige grafer.
- Ok, for grad 3, Andr á s eksempel eller tilfeldige grafer ser ut til å være god nok for søknaden min. Det ville være interessant, spesielt med hensyn til tilfeldige grafer, å konstruere en 3-regs graffamilie som ikke er en utvidelse. Men dette er sannsynligvis veldig vanskelig eller ikke mulig?
- Ta en forening på $ K_4 $ s. Hvis du vil ha en tilkoblet graf, fjerner du en kant fra hver $ K_4 $ (danner en graf kjent som diamantgrafen), og kobler dem i en syklus.
Svar
Hvis du ikke har noe imot grafer med selvløkker, er den «enkleste» utvidelsesfamilien sannsynligvis denne, noe som gir utvidere som er 3-vanlige.
Start med noen primtall $ p $, og konstruer hjørner nummerert $ 0 $ til $ p-1 $. For hvert toppunkt $ u \ ne 0 $, koble $ u $ til $ u-1 $ og $ u + 1 $ , modulo $ p $. Koble også $ u $ til det unike toppunktet $ v $ slik at $ uv \ equiv 1 \ mod p $.
Som et eksempel er 7-toppunktgrafen i familien en 7-syklus med hjørner nummerert sekvensielt rundt syklusen; det er selvløkker på $ 6 $, $ 0 $ og $ 1 $; til slutt er det akkorder som slutter seg til $ 3 $ og $ 5 $, og $ 2 $ og $ 4 $.
Se https://mathoverflow.net/questions/124708/an-expander-graph for videre diskusjon og referanser. Det er mange mer detaljerte tips ved å søke på » utvide «at CSTh eory , Math.SE , og MO .
Som Yuval Filmus påpeker, vil den tilfeldige konstruksjonen sannsynligvis gi bedre resultater generelt, men det kan selvfølgelig ikke gi en utvidelse (spesielt for små grafer).
Kommentarer
- Takk for kommentaren. Jeg hadde søkt etter utvidere før på de andre nettstedene, men ikke på MO, det ser ut til å være flere resultater.
Svar
Gitt en tilfeldig, vanlig graf er en utvidelses-whp (følg referansen gitt i dokumentasjonen til MATLAB-koden lenket nedenfor), jeg brukte en gang følgende: