Jag behöver konstruera d-reguljärt expanderdiagram för några små fasta d (som 3 eller 4) med n hörn.
Vad är den enklaste metoden att göra detta i praktiken? Konstruera ett slumpmässigt d-reguljärt diagram, vilket har visat sig vara a.a.s. en expander?
Jag läste också om Margulis-konstruktioner och Ramanujan-grafer som är expanderare och en konstruktion med en sicksackprodukt. Wikipedia ger en fin men mycket kort översikt: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Men vilken metod väljer jag i praktiken?
För mig verkar dessa metoder vara väldigt komplicerade att implementera och särskilt att förstå och kanske ganska specifika. Finns det inga enklare metoder, kanske baserade på permutationer eller så, för att generera en sekvens av d-reguljära expanderdiagram?
Är det kanske lättare att konstruera d-vanliga tvåpartiga expanderdiagram?
Jag har också en annan fråga: Vad sägs om familjer med dåliga d-reguljära expanderare? Har en sådan uppfattning mening? Kan man konstruera en familj av d-vanliga grafer (som naturligtvis är kopplade) som är så dåliga som möjligt i känslan av en expander?
Tack på förhand.
Kommentarer
- Det finns enklare uttryckliga konstruktioner än de du listade , men slumpmässiga grafer bör göra tricket och ha bättre parametrar.
- Kan du kanske ge namn eller referenser till konstruktionerna? Med bättre parametrar menar du en bättre (kant) expansion, antar jag?
- Andr á gav exemplet jag tänkte på, men i allmänhet är slumpmässiga grafer (nästan alltid) bättre än uttryckliga konstruktioner. Inte bara är kantutvidgningen större, en y annan liknande egenskap som är till hjälp för din algoritm uppfylls troligen automatiskt av slumpmässiga grafer.
- Ok, för grad 3, Andr á exempel eller slumpmässiga grafer verkar vara tillräckligt bra för min ansökan. Det skulle vara intressant, särskilt med avseende på slumpmässiga grafer, att konstruera en 3-regs graffamilj som inte är en expander. Men det här är förmodligen väldigt svårt eller inte möjligt?
- Ta en sammanslutning på $ K_4 $ s. Om du vill ha ett anslutet diagram tar du bort en kant från varje $ K_4 $ (bildar en graf som kallas diamantgrafen) och ansluter dem i en cykel.
Svar
Om du inte tänker på grafer med självslingor är den ”enklaste” expanderfamiljen förmodligen den här, vilket ger expanderare som är 3-vanliga.
Börja med några primtal $ p $, och konstruera hörn numrerade $ 0 $ till $ p-1 $. För varje toppunkt $ u \ ne 0 $, anslut $ u $ till $ u-1 $ och $ u + 1 $ , modulo $ p $. Anslut också $ u $ till det unika vertex $ v $ så att $ uv \ equiv 1 \ mod p $.
Som ett exempel är 7-vertexgrafen i familjen en 7-cykel med hörn numrerade sekventiellt runt cykeln; det finns självslingor på $ 6 $, $ 0 $ och $ 1 $; slutligen finns det ackord som går med $ 3 $ och $ 5 $ och $ 2 $ och $ 4 $.
Se https://mathoverflow.net/questions/124708/an-expander-graph för ytterligare diskussion och referenser. Det finns många mer detaljerade pekare genom att söka på ” expander ”vid CSTh eory , Math.SE och MO .
Som Yuval Filmus påpekar, kommer den slumpmässiga konstruktionen sannolikt att ge bättre resultat i allmänhet, men naturligtvis kanske det inte ger en expanderare (speciellt för små grafer).
Kommentarer
- Tack för kommentaren. Jag hade tidigare sökt efter expanderare på de andra webbplatserna men inte på MO, det verkar verkligen finnas fler resultat.
Svar
En slumpmässig vanlig graf är en expander-whp (följ referensen i dokumentationen för MATLAB-koden länkad nedan), jag använde en gång följande: