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

14

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 S ^ c .G=(V,E)

minSV e(S,Sc)min(|S|,|Sc|),
e(S,Sc)SSc

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) α . O que isso me diz sobre o diâmetro, se alguma coisa?

Robinson
fonte
2
Parece que a propriedade que você está solicitando é a expansão do gráfico, em vez da condutância do gráfico, definida como minSV e(S,S¯)/min{vol(S),vol(S¯)} , em que vol(S) é definido como vSdeg(v) . Qual é a propriedade que você quer ??
Hsien-Chih Chang #
2
@ 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 .
22668 robinson
1
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

Respostas:

13

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.ddd

É 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

minSV e(S,Sc)dmin{|S|,|Sc|}α

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 t -hop vizinhança tem tamanho pelo menos | V | / 2 . Portanto, o| S | | V | / 2 α d | S | S G d S S ( 1 + α ) | S | S = { u } u t = O ( log 1 + α | V | ) uS|S||V|/2αd|S|SGdSS(1+α)|S|S={u}ut=O(log1+α|V|)ut|V|/2vizinhança t + 1 -hop de qualquer vértice v deve cruzar avizinhança t -hop de u , ou o gráfico teria mais de | V | vértices, uma contradição. Então você temt+1vtu|V|

D=O(registro|V|registro(1+α))

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
1
@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
1
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