Artigos a serem creditados pelo particionamento espectral de gráficos

Se é um gráfico d- regular não direcionado e S é um subconjunto dos vértices da cardinalidade ≤ | V | / 2 , chame a expansão de borda de S a quantidade$G=(V,E)$$d$$S$$\leq |V|/2$$S$

$\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|}$

Onde é o número de arestas com uma extremidade em um e um ponto de extremidade em B . O problema de expansão da borda é encontrar um conjunto S com | S | ≤ | V | / 2 que minimiza ϕ ( S ) . Chame ϕ ( G ) a expansão de um conjunto ideal.$Edges(A,B)$$A$$B$$S$$|S|\leq |V|/2$$\phi(S)$$\phi(G)$

O algoritmo de particionamento espectral para o problema de expansão de borda funciona encontrando um vetor próprio do segundo maior valor próprio de A , a matriz de adjacência de G e considerando todos os `` conjuntos de limites '' S no formato { v : x ( v ) ≤ t } em todos os limites t . Se deixarmos λ 2 ser o segundo maior autovalor da matriz $x$$A$$G$$S$$\{ v : x(v) \leq t \}$$t$$\lambda_2$, então a análise do algoritmo de particionamento espectral mostra que o melhor conjunto de limitesSSPencontrado pelo algoritmo satisfaz$\frac 1d \cdot A$$S_{SP}$

$\phi(S_{SP}) \leq 2\sqrt {\phi(G)}$

O que se segue das Desigualdades de Cheeger

$\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

e

$1-\lambda_2 \leq 2 \phi(G)$

Qual é o primeiro artigo a fazer tal afirmação? Quais documentos devem ser creditados pelas idéias? Aqui está o que eu tenho:

• N. Alon e VD Milman. , desigualdades isoperimétricas para gráficos e superconcentradores, Journal of Combinatorial Theory, Série B, 1985, 38 (1): 73-88 $\lambda_1$

  Prove um resultado no espírito da desigualdade "simples" de Cheeger , mas para expansão de vértice em vez de expansão de borda. Reconheça que a relação entre expansão de borda e valores próprios é a versão discreta de um problema estudado por Cheeger em $1-\lambda_2 \leq 2\phi(G)$

  J. Cheeger. Um limite inferior para o menor autovalor do Laplaciano. Problemas em Análise, 1970.

• N. Alon. Autovalores e expansores. Combinatorica. 6 (2): 83-96, 1986.

  Prova um resultado no espírito da difícil desigualdade de Cheeger mas para expansão de vértice em vez de expansão de aresta. $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

• A. Sinclair, M. Jerrum. Contagem aproximada, geração uniforme e mistura rápida de cadeias de Markov. Information and Computation 82: 93-133, 1989 (versão para conferência 1987)

  Prove as desigualdades de Cheeger, conforme declarado acima. (O artigo deles estuda a condutância_ de cadeias de Markov reversíveis no tempo, o que equivale a uma expansão de borda_ em gráficos regulares.) Eles creditam o trabalho de Alon e Milman e de Alon pelas técnicas. Eles também creditam à Aldous um vínculo relacionado entre tempo de mistura e expansão da borda em gráficos regulares.

• M Mihail. Condutância e convergência de cadeias de Markov - um tratamento combinatório de expansores. FOCS 1989, páginas 526-531

  Embora o ponto principal do artigo seja que suas técnicas se apliquem a cadeias de Markov não reversíveis no tempo, quando aplicadas a gráficos regulares não-direcionados, têm uma vantagem em relação ao trabalho anterior: mostra que, se alguém executa o algoritmo de partição espectral com um método arbitrário vetor, ainda se obtém a desigualdade ondeλ′é o quociente de Rayleigh do vetor. Os argumentos de Alon, Milman, Sinclair e Jerrum requerem um vetor próprio. Isso é relevante para algoritmos rápidos de particionamento espectral que usam vetores próprios aproximados. $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda')}$$\lambda'$

Quando é que o significado algorítmico dos resultados acima, como algoritmos de particionamento de gráfico, é reconhecido pela primeira vez? Os artigos acima não têm essa discussão.

Parece que o primeiro artigo que introduziu esse conjunto de idéias (usando o invariante algébrico , o segundo menor autovalor do gráfico Laplaciano, para vincular várias propriedades do gráfico) à teoria dos grafos foi a "Conectividade Algébrica de Gráficos" de Fiedler em Matemática da Checoslováquia Diário. Apareceu em 1973, aproximadamente ao mesmo tempo que o artigo de Cheeger (1970), que tratava de variedades. Não tenho certeza de quem foi o primeiro a observar o paralelo entre gráficos e variedades a esse respeito. Às vezes, λ 2 é chamado de número de Fiedler.$\lambda_2$$\lambda_2$

Curiosamente, há uma observação no final do artigo de Fiedler, apontando um relatório técnico independente de Anderson e Morley intitulado Eigenvalues ​​of the Laplacian on a Graph from 1971, que aparentemente tinha idéias semelhantes. No entanto, o artigo de Anderson e Morley com o mesmo título apareceu em Álgebra Linear e Multilinear apenas em 1985.

Lembro-me de algumas referências adicionais daquela época:

1) Diaconis e Stroock, limites geométricos para valores próprios das cadeias de Markov, The Annals of Applied Probability, 1991; mas lembro-me de colocar minhas mãos em uma pré-impressão em 1990. Este artigo, por sua vez, refere-se a

2) Dodziuk, equações de diferença, desigualdade isoperimétrica e transitoriedade de certas caminhadas aleatórias, Transactions of the American Mathematics Society, 1984.

Além disso, um importante documento "companheiro algorítmico" para Sinclair e Jerrum na época era

3) Dyer Frieze Kannan, um algoritmo de tempo polinomial aleatório para a aproximação do volume de corpos convexos, STOC 89. É claro que os resultados aqui foram construídos sobre o SJ.