Przewodnictwo i średnica na zwykłych wykresach

$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$

Bardziej konkretnie przypuszczać wiem średnica wynosi co najmniej (albo co najwyżej) . Co to mówi mi o przewodności, jeśli w ogóle? I odwrotnie, przypuśćmy, że wiem, że przewodnictwo wynosi co najmniej (lub przynajmniej) . Co to mówi mi o średnicy, jeśli w ogóle? $D$ $\alpha$

graph-theory co.combinatorics expanders robinson
źródło

Wygląda na to, że właściwość, o którą pytasz, to rozszerzenie wykresu zamiast przewodności wykresu, która jest zdefiniowana jako

, gdzie

jest zdefiniowane jako

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)$ . Która z nich jest właściwością, którą chcesz?

Hsien-Chih Chang 之之

@ Hsien-Chi Chang - ponieważ wykres jest regularny, uważam, że przewodnictwo i ekspansja powinny być takie same, aż do mnożnika stopnia

d

$d$

robinson

Ach, nie zauważyłem, że wykres jest regularny. Dziękuję za wyjaśnienie.

Hsien-Chih Chang 張顯之

@ Hsien-ChihChang 張顯之: Myślałem, że ekspansja i przewodnictwo grafu są tą samą koncepcją. Czy w swoim komentarzu masz odniesienia do definicji?

Tim

Odpowiedzi:

Jak zauważa Hsieh, twoja definicja przewodności jest inna niż ta, którą znam współczynnikiem , gdzie jest stopniem zwykłego wykresu. Jest to również znane jako rozszerzenie krawędzi dla zwykłych wykresów. $d$ $d$

Zależność między rozszerzeniem krawędzi a średnicą jest dość łatwa do wykazania. Intuicyjnie ekspander jest „jak” pełny wykres, więc wszystkie wierzchołki są „blisko” siebie. Bardziej formalnie, niech

min_{S. \subseteq V.} \frac{mi (S., {S.}^{do})}{re \cdot min {| S. |, | {S.}^{do} |}} \geq α

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

$S$ $|S| \leq |V|/2$ $\alpha d |S|$ $S$ $G$ $d$ $S$ $S$ $(1+\alpha)|S|$ $S = \{u\}$ $u$ $t = O(\log_{1 + \alpha } |V|)$ $u$ $t$ $|V|/2$ $t+1$ $v$ $t$ $u$ $|V|$

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

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

Oczywiście wynika również, że posiadanie dolnej granicy średnicy oznacza górną granicę rozszerzalności krawędzi.

Nie sądzę, że mała średnica oznacza przewodnictwo. Jeśli nie nalegasz na zwykłe wykresy (i korzystasz z definicji Hsieha), wówczas dwa pełne wykresy połączone jedną krawędzią zapewniają kontrprzykład.

Sasho Nikolov
źródło

Zaraz opublikuję odpowiedź, a teraz nie muszę, mogę po prostu głosować na twoją;) Dzięki za dobrą odpowiedź!

Hsien-Chih Chang 張顯之

Mam nadzieję, że całkowity czas spędzony z

nami na

@robinson: ten prosty fakt i szybkie mieszanie są podstawą wielu (większości?) zastosowań rodzin ekspanderów zwykłych wykresów. na przykład właściwość małej średnicy jest podstawą aplikacji do rozwiązywania problemów z łącznością w przestrzeni logów

Sasho Nikolov

moja pierwotna odpowiedź zawierała błąd: argument, który napisałem, dotyczył ekspansji wierzchołków, ale pracujemy tutaj z ekspansją krawędzi. naprawiłem błąd, a granica jest teraz nieco gorsza

Sasho Nikolov