Beziehung zwischen Graphenexpansion und Leitfähigkeit

Ich bin ziemlich verwirrt über die genaue Beziehung zwischen der Erweiterung eines Graphen und seiner Leitfähigkeit. Meine erste Frage ist:

• Könnte mich jemand auf eine Referenz verweisen, die diese beiden Begriffe behandelt? (Ich habe verschiedene Vorlesungsunterlagen zu verwandten Themen gefunden, aber diese scheinen sich entweder auf die Erweiterung oder auf die Leitfähigkeit zu konzentrieren ...)

Ich habe gelesen, dass die Ausdehnung von ein Maß für die Geschwindigkeit des Mischens eines zufälligen Spaziergangs auf , dh die Zeit, um sich der stationären Verteilung zu nähern. Für einen regulären Graphen mit konstanter Expansion beträgt die Mischzeit beispielsweise . Das gleiche scheint für die Leitfähigkeit , dh wenn konstant ist, mischt sich ein zufälliger Spaziergang auf auch in der -Zeit. Darüber hinaus gilt diese Eigenschaft der Leitfähigkeit auch in nicht regulären Graphen, und für -reguläre Graphen kann die Expansion von durch einfaches Teilen der Leitfähigkeit von$G$$G$$d$$\Theta(\log n)$$\Phi(G)$$\Phi(G)$$G$$\Theta(\log n)$$d$$G$$G$von . Dies wirft die folgende Frage auf:$d$

• Warum sollten wir die Erweiterung eines Graphen Betracht ziehen , wenn die Leitfähigkeit ein stärkeres Maß zu sein scheint (das die Erweiterung subsumiert)?$G$

Es gibt verschiedene Definitionen für die Erweiterung eines Diagramms, die jedoch alle räumlich sind. Eine gebräuchliche Definition definierte die Erweiterung eines Graphen als wobei eine Menge von Eckpunkten ist, die höchstens die Hälfte der Eckpunkte enthalten, und die (Kanten-) Grenze von , die Anzahl der Kanten, die mit . Für einen regelmäßig verbundenen Graphen besteht eine starke Verbindung zwischen und einem Spektralparameter, der Eigenwertlücke$h(G)$$G$

$$h(G) = \min_{|S| \leq |G|/2} \frac{|\partial S|}{|S|},$$ $S$$\partial S$$S$$S$$\overline{S}$$d$$h(G)$ $\lambda(G)$Dies ist der kleinste Nicht-Null-Eigenwert des Laplace. Für einen unregelmäßig verbundenen Graphen gibt Cheegers Ungleichung an , dass Dies wird oft als zweitgrößter Eigenwert der Adjazenzmatrix von ausgedrückt , der erfüllt . Es muss Versionen von Cheegers Ungleichung für nicht reguläre Diagramme geben, und ich lasse Sie sie nachschlagen.$d$ $$\frac{\lambda(G)}{2} \leq h(G) \leq \sqrt{2d\lambda(G)}.$$ $\lambda_2(G)$$G$$\lambda_2(G) = d - \lambda(G)$

Viele Informationen zu Expander-Diagrammen finden Sie in der Umfrage (basierend auf Kursnotizen). Expander-Diagramme und ihre Anwendungen von Hoori, Linial und Wigderson. Weitere Informationen finden Sie in den Vorlesungsunterlagen und sogar in den jüngsten Veröffentlichungen.