Проводимость и диаметр в регулярных графиках

Учитывая неориентированный регулярный граф , какова связь между его диаметром - определенным как наибольшее расстояние между двумя узлами - и его проводимостью, определенной как где - количество ребер, пересекающих и . $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$

Более конкретно предположу , что я знаю , что диаметр, по крайней мере (или в большинстве) $D$ . Что это говорит мне о проводимости, если что? И, наоборот, предположим, я знаю, что проводимость не более (или не менее) $\alpha$ . Что это говорит мне о диаметре, если что?

graph-theory co.combinatorics expanders Robinson
источник

Похоже, что запрашиваемое вами свойство - это расширение графа вместо проводимости графа, которое определяется как , где определяется как . Какую собственность вы хотите ??

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

Сянь-Чи Чан 之之

@ Сянь-Чи Чанг - поскольку график регулярный, я считаю, что проводимость и расширение должны быть одинаковыми с точностью до множителя степени .

d

$d$

Робинсон

Ах, я не заметил, что график правильный. Спасибо за объяснение.

Сянь-Чи Чанг 之之

@ Hsien-ChihChang 張顯之: Я думал, что расширение графа и проводимость графа - это одно и то же понятие. У вас есть ссылки на определение в вашем комментарии?

Тим

Как отмечает Се, ваше определение проводимости отличается от того, которое я знаю, с коэффициентом , где - степень регулярного графа. Это также называется расширением ребер для регулярных графов. $d$ $d$

Соотношение между расширением кромки и диаметром довольно легко показать. Интуитивно понятно, что расширитель «похож» на полный граф, поэтому все вершины «близки» друг к другу. Более формально, пусть

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$

Возьмем любой набор вершин с . Есть хотя бы ребра , выходящие из и так как является -регулярной, окрестность ( в том числе самого) имеет размер , по меньшей мере , Применяя это утверждение индуктивно, начиная с для любой вершины $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|$

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

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

Конечно, из этого также следует, что нижняя граница диаметра подразумевает верхнюю границу расширения кромки.

Я не думаю, что маленький диаметр подразумевает проводимость. Если вы не настаиваете на регулярных графах (и используете определение Се), то два полных графа, соединенных одним ребром, дают контрпример.

Сашо Николов
источник

Я собираюсь опубликовать ответ, и теперь мне не нужно, я могу вместо этого просто поднять ваш голос;) Спасибо за хороший ответ!

Сянь-Чи Чанг 之之

Я надеюсь, что общее время, которое вы и я провели вдали от исследований, было сведено к минимуму :)

Сашо Николов

@robinson: этот простой факт и быстрое смешивание являются основой многих (большинства?) применений расширителей семейств регулярных графов. Например, свойство малого диаметра является основой приложения для решения проблемы связности в пространстве журналов

Сашо Николов

В моем первоначальном ответе была ошибка: я написал аргумент для расширения вершины, но здесь мы работаем с расширением ребра. я исправил ошибку, и теперь оценка немного хуже

Сашо Николов

Проводимость и диаметр в регулярных графиках

Ответы: