Wie werden reguläre Expandergraphen praktisch erstellt?

14

Ich muss einen d-regulären Expandergraphen für ein kleines festes d (wie 3 oder 4) von n Eckpunkten konstruieren.

Was ist die einfachste Methode, um dies in der Praxis zu tun? Erstellen eines zufälligen d-regulären Graphen, der sich als Expander erwiesen hat?

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 ganz spezifisch zu sein. Gibt es nicht einfachere Methoden, die möglicherweise auf Permutationen basieren, um praktisch eine Folge von d-regulären Expandergraphen zu generieren?

Ist es vielleicht einfacher, d-reguläre zweigliedrige Expandergraphen zu konstruieren?

Ich habe auch eine andere Frage: Was ist mit Familien von schlechten D-Regular-Expandern? Ist ein solcher Begriff sinnvoll? Kann man eine Familie von d-regulären Graphen konstruieren (die natürlich miteinander verbunden sind), die im Sinne eines Expanders so schlecht wie möglich ist?

Danke im Voraus.

graph-theory combinatorics cryptography discrete-mathematics expanders user2145167
quelle
2
Es gibt einfachere explizite Konstruktionen als die von Ihnen aufgelisteten, aber zufällige Graphen sollten den Trick machen und bessere Parameter haben.
Yuval Filmus
Können Sie vielleicht Namen oder Referenzen der Konstruktionen nennen? Mit besseren Parametern meinen Sie eine bessere (Kanten-) Expansion, denke ich?
user2145167
1
András gab das Beispiel an, an das ich gedacht hatte, aber im Allgemeinen sind Zufallsgraphen (fast immer) besser als explizite Konstruktionen. Die Kantenerweiterung ist nicht nur größer, jede andere ähnliche Eigenschaft, die für Ihren Algorithmus hilfreich ist, wird wahrscheinlich automatisch durch Zufallsgraphen erfüllt.
Yuval Filmus
Ok, für Grad 3 scheinen András Beispiel oder die Zufallsgraphen gut genug für meine Anwendung zu sein. Insbesondere im Hinblick auf die Zufallsgraphen wäre es interessant, eine 3-reg-Graphenfamilie zu konstruieren, die kein Expander ist. Ist das aber wohl sehr schwer oder nicht möglich?
user2145167
3
Nehmen Sie eine Vereinigung von s. Wenn Sie einen zusammenhängenden Graphen wünschen, entfernen Sie eine Kante von jedem K 4 (bilden Sie einen als Diamantgraphen bekannten Graphen) und verbinden Sie sie in einem Zyklus. K4K4
Yuval Filmus

Antworten:

9

Wenn Sie sich nicht um Graphen mit Self-Loops kümmern, ist die "einfachste" Expander-Familie wahrscheinlich diese, die Expander mit drei regulären Werten anbietet.

Beginnen Sie mit einer Primzahl und konstruieren Sie Eckpunkte mit den Nummern 0 bis p - 1 . Verbinden Sie für jeden Eckpunkt u ≠ 0 u mit u - 1 und u + 1 , modulo p . Verbinden Sie auch u mit dem eindeutigen Eckpunkt v, so dass u v ≡ 1 istp0p−1u≠0uu−1u+1puv .uv≡1modp

Als Beispiel ist der 7-Eckpunkt-Graph in der Familie ein 7-Zyklus mit Scheitelpunkten, die nacheinander um den Zyklus nummeriert sind. es gibt Selbstschleifen bei , 0 und 1 ; Schließlich kommen die Akkorde 3 und 5 sowie 2 und 4 zusammen .6013524

Weitere Informationen und Referenzen finden Sie unter /mathpro/124708/an-expander-graph . Es gibt viele detailliertere Hinweise , wenn Sie nach "Expander" bei CSTheory , Math.SE und MO suchen .

Wie Yuval Filmus hervorhebt, liefert die zufällige Konstruktion im Allgemeinen wahrscheinlich bessere Ergebnisse, ergibt aber möglicherweise keinen Expander (insbesondere für kleine Graphen).

András Salamon
quelle
Danke für die Bemerkung. Ich hatte schon früher auf den anderen Websites nach Expandern gesucht, aber nicht auf MO. Es scheint wirklich mehr Ergebnisse zu geben.
user2145167