Tenho um interesse crescente na teoria dos grafos espectrais, o que acho fascinante, e comecei a coletar alguns documentos que ainda tenho que ler mais profundamente do que o que tenho até agora.
No entanto, estou curioso sobre uma declaração que apareceu em várias fontes (por exemplo, por lá ), que diz em essência que alguns resultados na teoria dos grafos foram provados usando apenas técnicas baseadas em espectro, e que até agora, nenhuma prova de que ignora essas técnicas é conhecida.
A menos que eu pulei isso, não me lembro de ter visto um exemplo na literatura que li até agora. Algum de vocês conhece exemplos de tais resultados?
graph-theory
co.combinatorics
proofs
spectral-graph-theory
Anthony Labarre
fonte
fonte
Respostas:
O teorema de Hoffman-Singleton .
fonte
Que tal esse resultado na computação quântica.
Mario Szegedy. Aceleração quântica de algoritmos baseados em cadeias de Markov. Em FOCS'04.
Ele estende as cadeias de Markov às cadeias quânticas de Markov e mostra que o tempo de impacto quântico é mais alto limitado pela raiz quadrada do tempo de impacto clássico. Ele faz isso relacionando os vetores singulares da cadeia clássica de Markov aos vetores singulares da cadeia quântica de Markov. Antes deste artigo, não havia nenhuma relação conhecida entre passeios aleatórios e quânticos. Não consigo imaginar como fazer o mesmo usando técnicas não espectrais.
fonte
Penso que o teorema da amizade (veja também o artigo de Huneke ) é um bom exemplo, embora estritamente falando exista agora provas do teorema da amizade que evitam valores próprios. As provas que evitam valores próprios inteiramente são muito mais confusas que a prova espectral.
(O teorema da amizade afirma que, se em uma sala de pessoas, todo par de pessoas tem exatamente um amigo em comum, então há alguém que conhece todo mundo.)
fonte
Seja a matriz laplaciana de um gráfico ponderado não direcionado . Um esparsificador de um gráfico é um gráfico tal que para cada o seguinte vale: Usando métodos espectrais, Batson et al. mostre como construir esses sparisifiers usando arestas .LG G=(V,E,w) G H x∈RV
Mesmo que a afirmação do teorema não seja discutivelmente "inerentemente espectral", não creio que se saiba como se pode obter esse resultado ou um resultado semelhante sem o uso de técnicas espectrais.
fonte