AnnalesEnseignement

Agrégation interne 2011 — Épreuve 1

Spectre du laplacien normalisé d'un graphe · 7 pages

Le problème étudie le laplacien normalisé $L$ d'un graphe sans sommet isolé, de coefficients $1$ sur la diagonale et $-1/\sqrt{d_i d_j}$ pour deux sommets voisins, et les informations combinatoires portées par ses valeurs propres $\lambda_1 \leqslant \dots \leqslant \lambda_n$ . Il calcule le spectre pour un graphe à trois sommets, le graphe complet et le graphe cyclique (via les matrices circulantes), montre que $\lambda_1 = 0$ , que le graphe est connexe si et seulement si $\lambda_2 > 0$ , établit le principe du minimax, caractérise $\lambda_2 = n/(n-1)$ (graphe complet) et $\lambda_n = 2$ (graphe biparti), et minore le nombre chromatique par $\chi(G) \geqslant 1 + 1/(\lambda_n - 1)$ .

Le sujet, partie par partie

Notations et Partie A — Exemples p. 2–4

Théorie spectrale des graphes · Matrices remarquables · Diagonalisation · Nombres complexes · Théorème spectral — matrice laplacienne normalisée, graphe complet, graphe cyclique, matrice circulante, racines de l'unité, multiplicité des valeurs propres

Partie B — Quelques généralités p. 4–5

Théorie spectrale des graphes · Quotient de Rayleigh et Courant-Fischer · Matrices symétriques positives · Inégalité de Cauchy-Schwarz · Graphes — composantes connexes, graphe connexe, noyau du laplacien, quotient de Rayleigh, principe du minimax, base orthonormée de vecteurs propres

Partie C — Étude des bornes des valeurs propres p. 5–6

Théorie spectrale des graphes · Quotient de Rayleigh et Courant-Fischer · Calcul matriciel · Graphes — trace du laplacien, graphe complet, graphe biparti, plus grande valeur propre, cas d'égalité, deuxième valeur propre

Partie D — À propos du nombre chromatique p. 6–7

Théorie spectrale des graphes · Entrelacement et inégalités spectrales · Matrices par blocs · Matrices symétriques positives · Graphes — nombre chromatique, coloriage, ensemble indépendant, sous-matrice principale, matrice de rang 1, entrelacement des valeurs propres

Dans l'édifice

Matrices d'une application linéaire Conjugaison et module Racines carrées et équations du second degré La fonction exponentielle Espaces de Hilbert et théorème de projection