Conductancia y diámetro en gráficos regulares

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

Más concretamente supongo que sé el diámetro es de al menos (o como máximo) $D$ . ¿Qué me dice esto sobre la conductancia, si acaso? Y, por el contrario, supongamos que sé que la conductancia es como máximo (o al menos) $\alpha$ . ¿Qué me dice esto sobre el diámetro, si acaso?

graph-theory co.combinatorics expanders Robinson
fuente

Parece que la propiedad que está preguntando es la expansión del gráfico en lugar de la conductancia del gráfico, que se define como

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})\}}$ , donde

v o l (S)

$\mathsf{vol}(S)$ se define como

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

$\sum_{v \in S} \deg(v)$ . ¿Cuál es la propiedad que quieres?

Hsien-Chih Chang 張顯之

@ Hsien-Chi Chang: como el gráfico es regular, creo que la conductancia y la expansión deberían ser las mismas hasta un factor multiplicativo del grado

d

$d$ .

robinson

Ah, no me di cuenta de que el gráfico es regular. Gracias por la explicación.

Hsien-Chih Chang 張顯之

@ Hsien-ChihChang 張顯之: Pensé que la expansión gráfica y la conductancia gráfica son el mismo concepto. ¿Tiene referencias sobre la definición en su comentario?

Tim

Como señala Hsieh, su definición de conductancia es diferente de la que conozco por un factor de , donde es el grado de la gráfica regular. Esto también se conoce como expansión de borde para gráficos regulares. $d$ $d$

Una relación entre la expansión del borde y el diámetro es bastante fácil de mostrar. Intuitivamente, un expansor es "como" un gráfico completo, por lo que todos los vértices están "cerca" entre sí. Más formalmente, dejemos

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$

Tome cualquier conjunto de vértices con . Hay al menos bordes que salen de y dado que es regular, la vecindad de (incluido el propio ) tiene al menos un tamaño . Aplicando esta afirmación inductivamente, comenzando desde para cualquier vértice $S$ $|S| \leq |V|/2$ $\alpha d |S|$ $S$ $G$ $d$ $S$ $S$ $(1+\alpha)|S|$ $S = \{u\}$ $u$ , Vemos que para algunos , 's -hop barrio tiene tamaño al menos . Por lo tanto, el vecindario -hop de cualquier vértice tiene que intersectar con el vecindario -hop de , o la gráfica tendría más de vértices, una contradicción. Así que tienes $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)$

Por supuesto, también se deduce que tener un límite inferior en el diámetro implica un límite superior en la expansión del borde.

No creo que el diámetro pequeño implique conductancia. Si no insiste en gráficos regulares (y usa la definición de Hsieh), entonces dos gráficos completos conectados por un solo borde proporcionan un contraejemplo.

Sasho Nikolov
fuente

Estoy a punto de publicar una respuesta y ahora no tengo que hacerlo, simplemente puedo votar la suya;) ¡Gracias por la buena respuesta!

Hsien-Chih Chang 張顯之

Espero que se haya minimizado el tiempo total que pasamos lejos de la investigación :)

Sasho Nikolov

@robinson: este hecho simple y la mezcla rápida son la base de muchas (¿la mayoría?) aplicaciones de familias de expansores de gráficos regulares. la propiedad de diámetro pequeño, por ejemplo, es la base de la aplicación para resolver la conectividad st en el espacio de registro

Sasho Nikolov

mi respuesta original tenía un error: el argumento que había escrito era para la expansión de vértices, pero aquí estamos trabajando con la expansión de borde. He solucionado el error, y el límite ahora es un poco peor

Sasho Nikolov

Conductancia y diámetro en gráficos regulares

Respuestas: