Leitfähigkeit und Durchmesser in regelmäßigen Diagrammen

$G=(V,E)$

min_{S \subset V} \frac{e (S, S^{c})}{min (| S |, | S^{c} |)},

$\min_{S \subset V} ~\frac{e(S,S^c)}{\min(|S|,|S^c|)},$

e (S, S^{c})

$e(S,S^c)$

S

$S$

S^{c}

$S^c$

Genauer gesagt, nehme ich an, dass der Durchmesser mindestens (oder höchstens) beträgt $D$ . Was sagt mir das über das Verhalten, wenn überhaupt? Und umgekehrt nehme ich an, ich weiß, dass die Leitfähigkeit höchstens (oder zumindest) $\alpha$ . Was sagt mir das über den Durchmesser, wenn überhaupt?

graph-theory co.combinatorics expanders Robinson
quelle

Es sieht so aus, als ob die von Ihnen Eigenschaft die Diagrammerweiterung anstelle der Diagrammleitfähigkeit ist, die als , wobei als . Welches ist die Immobilie, die Sie wollen?

min_{S \subseteq V} e (S, \bar{S}) / min {v o l (S), v o l (\bar{S})}

$\min_{S \subseteq V} \ {e(S,\overline{S})}/{\min\{\mathsf{vol}(S), \mathsf{vol}(\overline{S})\}}$

v o l (S)

$\mathsf{vol}(S)$

\sum_{v \in S} \deg (v)

$\sum_{v \in S} \deg(v)$

Hsien-Chih Chang 張顯張顯

@ Hsien-Chi Chang - da der Graph regelmäßig ist, glaube ich, dass Leitfähigkeit und Expansion bis zu einem multiplikativen Faktor des Grades .

d

$d$

Robinson

Ah, ich habe nicht bemerkt, dass die Grafik regelmäßig ist. Danke für die Erklärung.

Hsien-Chih Chang 張顯之

@ Hsien-ChihChang 張顯張顯: Ich dachte, Grafikexpansion und Grafikleitfähigkeit sind dasselbe Konzept. Haben Sie in Ihrem Kommentar Verweise auf die Definition?

StackExchange for All

Wie Hsieh bemerkt, weicht Ihre Definition der Leitfähigkeit von der mir bekannten um den Faktor , wobei der Grad des regulären Graphen ist. Dies wird auch als Kantenerweiterung für reguläre Diagramme bezeichnet. $d$ $d$

Ein Zusammenhang zwischen Kantenausdehnung und Durchmesser ist recht einfach aufzuzeigen. Intuitiv ist ein Expander "wie" ein komplettes Diagramm, sodass alle Scheitelpunkte "nahe" beieinander liegen. Genauer gesagt, lassen Sie

min_{S \subseteq V} \frac{e (S, S^{c})}{d \cdot min {| S |, | S^{c} |}} \geq α

$\min_{S \subseteq V}\ { \frac{ e(S, S^c) }{ d \cdot \min\{|S|, |S^c|\} }} \geq \alpha$

Nehmen Sie eine beliebige Menge von Scheitelpunkten mit . Es gibt mindestens kommenden Kanten der aus und da ist die Nachbarschaft von -regelmäßige, (einschließlich selbst) ist zumindest der Größe . Indem diese Behauptung induktiv anwenden, beginnend mit $S$ $|S| \leq |V|/2$ $\alpha d |S|$ $S$ $G$ $d$ $S$ $S$ $(1+\alpha)|S|$ für einen beliebigen Scheitelpunkt $S = \{u\}$ $u$ Sehen wir , dass für einige Ecken, ein Widerspruch. Also hast du , ‚s -hopfen blüten Nachbarschaft hat Größe mindestens . Daher muss die Hop-Nachbarschaft eines beliebigen Scheitelpunkts die Hop-Nachbarschaft von schneiden, oder der Graph hätte mehr als $t = O(\log_{1 + \alpha } |V|)$ $u$ $t$ $|V|/2$ $t+1$ $v$ $t$ $u$ $|V|$

D = O (\frac{\log | V |}{\log (1 + α)})

$D = O\left(\frac{\log |V|}{\log (1 + \alpha)}\right)$

Natürlich folgt daraus auch, dass eine Untergrenze des Durchmessers eine Obergrenze der Kantenexpansion impliziert.

Ich glaube nicht, dass ein kleiner Durchmesser eine Leitfähigkeit impliziert. Wenn Sie nicht auf regulären Diagrammen bestehen (und die Definition von Hsieh verwenden), sind zwei vollständige Diagramme, die durch eine einzige Kante verbunden sind, ein Gegenbeispiel.

Sasho Nikolov
quelle

Ich bin kurz davor eine Antwort zu schreiben und muss es jetzt nicht mehr. Ich kann stattdessen einfach deine positiv bewerten;) Danke für die gute Antwort!

Hsien-Chih Chang 張顯之

Ich hoffe, die Gesamtzeit, die Sie und ich außerhalb der Forschung verbracht haben, wurde minimiert :)

Sasho Nikolov

@robinson: Diese einfache Tatsache und das schnelle Mischen sind die Basis für viele (die meisten?) Anwendungen von Expanderfamilien regulärer Graphen. Die Eigenschaft mit kleinem Durchmesser ist zum Beispiel die Grundlage für die Anwendung zur Lösung der st-Konnektivität im logspace

Sasho Nikolov

Meine ursprüngliche Antwort hatte einen Fehler: Das Argument, das ich geschrieben hatte, war für die Scheitelpunkterweiterung, aber wir arbeiten hier mit der Kantenerweiterung. Ich habe den Fehler behoben, und die Grenze ist jetzt etwas schlimmer

Sasho Nikolov

Leitfähigkeit und Durchmesser in regelmäßigen Diagrammen

Antworten: