Tengo un interés creciente en la teoría de gráficos espectrales, lo cual me parece fascinante, y he comenzado a recopilar algunos documentos que aún no he leído más a fondo de lo que hasta ahora tengo.
Sin embargo, tengo curiosidad acerca de una declaración que apareció en varias fuentes (por ejemplo, allí ), que dice en esencia que algunos resultados en la teoría de grafos se han probado utilizando solo técnicas basadas en el espectro, y que hasta ahora, no hay pruebas de que evita esas técnicas es conocido.
A menos que me salte eso, no recuerdo haber visto un ejemplo así en la literatura que he leído hasta ahora. ¿Alguno de ustedes sabe de ejemplos de tales resultados?
graph-theory
co.combinatorics
proofs
spectral-graph-theory
Anthony Labarre
fuente
fuente
Respuestas:
El teorema de Hoffman-Singleton .
fuente
¿Qué tal este resultado en la computación cuántica?
Mario Szegedy Aceleración cuántica de los algoritmos basados en la cadena de Markov. En FOCS'04.
Extiende las cadenas de Markov a las cadenas cuánticas de Markov, y muestra que el tiempo de golpe cuántico está limitado por la raíz cuadrada del tiempo de golpe clásico. Lo hace relacionando los vectores singulares de la cadena clásica de Markov con los vectores singulares de la cadena cuántica de Markov. Antes de este artículo, no se conocía ninguna relación entre los paseos aleatorios y cuánticos. No puedo imaginar cómo hacer lo mismo usando técnicas no espectrales.
fuente
Creo que el teorema de la amistad (véase también el artículo de Huneke ) es un buen ejemplo, aunque estrictamente hablando ahora existen pruebas del teorema de la amistad que evitan los valores propios. Las pruebas que evitan por completo los valores propios son mucho más desordenadas que la prueba espectral.
(El teorema de la amistad establece que si en una habitación de personas, cada par de personas tiene exactamente un amigo común, entonces hay alguien que conoce a todos los demás).
fuente
Aunque la afirmación del teorema es discutiblemente no "inherentemente espectral", no creo que se sepa cómo se puede obtener este resultado o un resultado similar sin utilizar técnicas espectrales.
fuente