Relação entre expansão de grafos e condutância

Estou bastante confuso sobre a relação exata entre a expansão de um gráfico e sua condutância. Minha primeira pergunta é:

• Alguém poderia me indicar uma referência que discuta essas duas noções? (Encontrei várias notas de aula sobre tópicos relacionados, mas estes parecem se concentrar tanto na expansão quanto na condutância ...)

Eu li que a expansão de $G$ é uma medida da velocidade de mistura de uma caminhada aleatória $G$, ou seja, o tempo para se aproximar da distribuição estacionária. Para$d$-regular com expansão constante, por exemplo, o tempo de mistura é $\Theta(\log n)$. O mesmo parece ser verdade para a condutância$\Phi(G)$, ou seja, se $\Phi(G)$ é constante, então uma caminhada aleatória $G$ também vai misturar $\Theta(\log n)$Tempo. Além disso, essa propriedade de condutância é válida mesmo em gráficos não regulares e, por$d$-regulares gráficos a expansão de $G$ pode ser encontrada simplesmente dividindo a condutância de $G$ de $d$. Isso gera a seguinte pergunta:

• Por que devemos considerar a expansão de um gráfico $G$, quando a condutância parece ser uma medida mais forte (que implica expansão)?

Existem várias definições diferentes para a expansão de um gráfico, mas todas são espaciais. Uma definição comum definiu a expansão$h(G)$ de um gráfico $G$ Como

$$h(G) = \min_{|S| \leq |G|/2} \frac{|\partial S|}{|S|},$$ onde é um conjunto de vértices que contém no máximo metade dos vértices e é o limite (borda) de , o número de arestas que conectam a . Para um gráfico conectado regular, existe uma forte conexão entre e um parâmetro espectral, o intervalo de valor próprio , que é o menor valor próprio não-zero do Laplaciano. Para um gráfico conectado regular, a desigualdade de Cheeger indica que $S$$\partial S$$S$$S$$\overline{S}$$d$$h(G)$ $\lambda(G)$$d$ $$\frac{\lambda(G)}{2} \leq h(G) \leq \sqrt{2d\lambda(G)}.$$ Isso geralmente é colocado em termos do segundo maior autovalor da matriz de adjacência de , que satisfaz . Deve haver versões da desigualdade de Cheeger para gráficos não regulares, e eu deixarei você procurá-las.$\lambda_2(G)$$G$$\lambda_2(G) = d - \lambda(G)$

Muitas informações sobre gráficos expansores podem ser encontradas na pesquisa (com base nas notas do curso). Gráficos expansores e suas aplicações por Hoori, Linial e Wigderson. Outras informações estão espalhadas entre anotações de palestras e até artigos recentes.