Condutância e diâmetro em gráficos regulares

Dado um gráfico regular e não direcionado , qual é a relação entre seu diâmetro - definido como a maior distância entre dois nós - e sua condutância, definida como onde é o número de arestas que cruzam entre e . $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$

Mais concretamente suponho eu sei o diâmetro é de pelo menos (ou no máximo) $D$ . O que isso me diz sobre a condutância, se alguma coisa? E, inversamente, suponha que eu saiba que a condutância é no máximo (ou pelo menos) $\alpha$ . O que isso me diz sobre o diâmetro, se alguma coisa?

graph-theory co.combinatorics expanders Robinson
fonte

Parece que a propriedade que você está solicitando é a expansão do gráfico, em vez da condutância do gráfico, definida 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})\}}$ , em que

v o l (S)

$\mathsf{vol}(S)$ é definido como

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

$\sum_{v \in S} \deg(v)$ . Qual é a propriedade que você quer ??

Hsien-Chih Chang #

@ Hsien-Chi Chang - como o gráfico é regular, acredito que condutância e expansão devem ser as mesmas até um fator multiplicativo do grau

d

$d$ .

22668 robinson

Ah, eu não percebi que o gráfico é regular. Obrigada pelo esclarecimento.

Hsien-Chih Chang #: 01/07/11

@ Hsien-ChihChang 之之: Eu pensei que expansão de gráfico e condutância de gráfico são o mesmo conceito. Você tem referências sobre a definição em seu comentário?

Tim

Como Hsieh observa, sua definição de condutância é diferente da que conheço por um fator de , onde é o grau do gráfico regular. Isso também é conhecido como expansão de borda para gráficos regulares. $d$ $d$

É fácil mostrar uma relação entre expansão da borda e diâmetro. Intuitivamente, um expansor é "como" um gráfico completo; portanto, todos os vértices são "próximos" um do outro. Mais formalmente, vamos

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$

Pegue qualquer conjunto de vértices com . Existem pelo menosarestas que saem de e como é regular, a vizinhança de (incluindo o próprio ) é de tamanho pelo menos. Aplicando esta reivindicação indutivamente, começando a partir de para qualquer vértice , vemos que para alguns , 's -hop vizinhança tem tamanho pelo menos . Portanto, o $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$ vizinhança -hop de qualquer vértice deve cruzar avizinhança -hop de , ou o gráfico teria mais devértices, uma contradição. Então você tem $t+1$ $v$ $t$ $u$ $|V|$

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

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

Obviamente, também se segue que ter um limite inferior no diâmetro implica um limite superior na expansão da borda.

Não acho que diâmetro pequeno implique condutância. Se você não insistir em gráficos regulares (e usar a definição de Hsieh), dois gráficos completos conectados por uma única aresta fornecerão um contra-exemplo.

Sasho Nikolov
fonte

Estou prestes a postar uma resposta e agora não preciso, posso simplesmente votar em sua;) Obrigado pela boa resposta!

Hsien-Chih Chang #

Espero que o tempo total que você e eu passamos longe de pesquisa foi minimizado :)

Sasho Nikolov

@robinson: esse fato simples e a mistura rápida são a base de muitas (a maioria?) aplicações de famílias expansoras de gráficos regulares. o estabelecimento pequeno diâmetro, por exemplo, é a base do pedido para a solução de conectividade r em logspace

Sasho Nikolov

minha resposta original teve um erro: o argumento que eu escrevi era para expansão de vértice, mas estamos trabalhando com expansão de borda aqui. i já reparou o erro, e o limite agora é um pouco pior

Sasho Nikolov

Condutância e diâmetro em gráficos regulares

Respostas: