Ich muss einen d-regulären Expander-Graphen für ein kleines festes d (wie 3 oder 4) von n Eckpunkten erstellen.
Was ist die einfachste Methode, dies in der Praxis zu tun? Erstellen eines zufälligen d-regulären Graphen, der nachweislich a.a.s. ein Expander?
Ich habe auch über Margulis-Konstruktionen und Ramanujan-Diagramme gelesen, die Expander und eine Konstruktion mit einem Zick-Zack-Produkt sind. Wikipedia gibt einen schönen, aber sehr kurzen Überblick: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Aber welche Methode wähle ich in der Praxis?
Für mich scheinen diese Methoden alle sehr kompliziert zu implementieren und insbesondere zu verstehen und vielleicht ziemlich spezifisch zu sein. Gibt es keine einfacheren Methoden, die möglicherweise auf Permutationen oder so basieren, um praktisch eine Folge von d-regulären Expander-Graphen zu erzeugen?
Ist es vielleicht einfacher, d-reguläre zweigeteilte Expander-Graphen zu erstellen?
Ich habe noch eine andere Frage: Was ist mit Familien von schlechten d-regulären Expandern? Ist ein solcher Begriff sinnvoll? Kann man eine Familie von d-regulären Graphen (die natürlich miteinander verbunden sind) konstruieren, die so schlecht wie möglich ist? das Gefühl eines Expanders?
Vielen Dank im Voraus.
Kommentare
- Es gibt einfachere explizite Konstruktionen als die von Ihnen aufgelisteten , aber zufällige Graphen sollten den Trick machen und bessere Parameter haben.
- Können Sie vielleicht Namen oder Referenzen der Konstruktionen angeben? Mit besseren Parametern meinen Sie eine bessere (Kanten-) Erweiterung, denke ich?
- Andr á s gab das Beispiel an, das ich mir vorgestellt hatte, aber im Allgemeinen sind zufällige Graphen (fast immer) besser als explizite Konstruktionen. Nicht nur die Kantenerweiterung ist größer, ein Eine andere ähnliche Eigenschaft, die für Ihren Algorithmus hilfreich ist, wird wahrscheinlich automatisch durch zufällige Diagramme erfüllt.
- Ok, für Grad 3 das Beispiel von Andr á oder die zufälligen Diagramme scheinen gut genug für meine Bewerbung zu sein. Insbesondere im Hinblick auf die Zufallsgraphen wäre es interessant, eine 3-Reg-Graphenfamilie zu konstruieren, die kein Expander ist. Aber das ist wahrscheinlich sehr schwer oder nicht möglich?
- Nehmen Sie eine Vereinigung von $ K_4 $ s. Wenn Sie ein verbundenes Diagramm möchten, entfernen Sie eine Kante von jedem $ K_4 $ (bilden Sie ein Diagramm, das als Diamantdiagramm bezeichnet wird) und verbinden Sie sie in einem Zyklus.
Antwort
Wenn es Ihnen nichts ausmacht, Diagramme mit Selbstschleifen zu erstellen, ist die „einfachste“ Expander-Familie wahrscheinlich diese, die Expander gibt, die 3-regulär sind.
Beginnen Sie mit einer Primzahl $ p $ und konstruieren Sie Scheitelpunkte mit den Nummern $ 0 $ bis $ p-1 $. Verbinden Sie für jeden Scheitelpunkt $ u \ ne 0 $ $ u $ mit $ u-1 $ und $ u + 1 $ , modulo $ p $. Verbinden Sie $ u $ auch mit dem eindeutigen Scheitelpunkt $ v $, so dass $ uv \ equiv 1 \ mod p $.
Als Beispiel ist das 7-Scheitelpunkt-Diagramm in der Familie Ein 7-Zyklus mit Scheitelpunkten, die fortlaufend um den Zyklus herum nummeriert sind. Es gibt Selbstschleifen für $ 6 $, $ 0 $ und $ 1 $. Schließlich gibt es Akkorde, die $ 3 $ und $ 5 $ sowie $ 2 $ und $ 4 $ verbinden.
Weitere Informationen und Referenzen finden Sie unter https://mathoverflow.net/questions/124708/an-expander-graph . Es gibt viele detailliertere Hinweise, wenn Sie auf “ expander „at CSTh eory , Math.SE und MO .
Wie Yuval Filmus hervorhebt, liefert die zufällige Konstruktion im Allgemeinen wahrscheinlich bessere Ergebnisse, liefert jedoch möglicherweise keinen Expander (insbesondere für kleine Diagramme).
Kommentare
- Danke für die Bemerkung. Ich hatte zuvor auf den anderen Websites nach Expandern gesucht, aber nicht auf MO. Es scheint wirklich mehr Ergebnisse zu geben.
Antwort
Bei einem zufälligen regulären Graphen ist ein Expander whp (Befolgen Sie die Referenz in der Dokumentation des unten verlinkten MATLAB-Codes.) Ich habe einmal Folgendes verwendet: