Dejemos que $L$ sea el laplaciano discreto asociado a un grafo no dirigido. Es bien sabido que el brecha espectral de $L$ es decir, el menor valor propio distinto de cero, es una medida de lo bien conectado que está el grafo; cuanto menor sea la brecha espectral, menos cortes serán necesarios para desconectar el grafo.
He observado experimentalmente que el número de valores propios "pequeños" se corresponde con el número de "grupos poco conectados" en el gráfico. Por ejemplo, tomemos cuatro grafos A, B, C, D, cada uno con cuatro vértices, de forma que cada vértice esté conectado con todos los demás vértices dentro de cada uno de los cuatro grafos. A continuación, forme un único grafo conectado G conectando un vértice de A con un vértice de B, un vértice de B con un vértice de C y un vértice de C con un vértice de D. Los primeros valores propios del laplaciano de G son:
0, .1126, .3542, .5688, 4, 4,...
Sospecho que si esta observación se formulara correctamente no sería difícil convertirla en un teorema, pero si alguien conoce una referencia se lo agradecería. Mi pregunta principal es: ¿se puede formular una versión cuantitativa de mi observación? En otras palabras, si te doy el espectro del laplaciano de un gráfico, ¿puedes decirme cuántos "clusters poco conectados" hay en el gráfico? No quiero comprometerme con ningún significado preciso de la frase "clusters poco conectados"; espero respuestas que incluyan una definición adecuada.
