AnnalesÉcoles d'ingénieurs

X-ENS MP 2016 — Maths D

Spectres de graphes, constante de Cheeger et expanseurs · 8 pages

Le sujet étudie le laplacien $T_G$ d'un graphe fini : positivité, caractérisation min-max des valeurs propres, noyau des constantes pour un graphe connexe, majoration par $2d_G$ avec cas d'égalité (graphe régulier et biparti), monotonie par rapport aux arêtes et spectre du graphe complet. Il traite ensuite le graphe de Cayley de $A_5$ pour les générateurs $(12345)$ et $(12)(34)$ , modèle du buckminsterfullerène, où des arguments de représentation donnent des multiplicités au moins 3 puis 4. Il relie la constante de Cheeger $h_G$ au diamètre et à $\lambda_2$ ( $h_G^2/(2d_G) \leqslant \lambda_2 \leqslant 2h_G$ ), majore $\lambda_2$ pour les graphes à plongement sphérique, et étudie enfin par transformée de Fourier discrète sur $(\mathbb{Z}/n\mathbb{Z})^2$ le tore discret et l'opérateur de Gabber-Galil, dont les valeurs propres non nulles sont minorées par $7/20$ .

Le sujet, partie par partie

Préambule, Notations et Partie I — Estimations élémentaires p. 1–4

Théorie spectrale des graphes · Quotient de Rayleigh et Courant-Fischer · Théorème spectral · Graphes — laplacien d'un graphe, Courant-Fischer, graphe biparti, graphe régulier, graphe complet, graphe connexe

Partie II — Le graphe de $A_5$ (buckminsterfullerène) p. 4–5

Théorie spectrale des graphes · Représentations des groupes finis · Groupe symétrique · Graphes de Cayley et croissance des groupes · Actions de groupes · Isométries et groupe orthogonal — groupe alterné $A_5$ , graphe de Cayley, générateurs d'un groupe, représentation de permutation, multiplicité des valeurs propres, buckminsterfullerène

Partie III — Constante de Cheeger p. 5–6

Théorie spectrale des graphes · Quotient de Rayleigh et Courant-Fischer · Inégalité de Cauchy-Schwarz · Graphes · Géométrie affine et euclidienne — constante de Cheeger, inégalité de Cheeger, diamètre d'un graphe, distance dans un graphe, plongement sphérique, graphes planaires

Partie IV — Graphes de Gabber et Galil p. 7–8

Théorie spectrale des graphes · Transformées de Fourier et de Laplace · Inégalités classiques · Congruences et Z/nZ · Groupes de matrices · Nombres complexes — graphes expanseurs, Gabber-Galil, transformée de Fourier discrète, formule de Plancherel, tore discret, trou spectral

Dans l'édifice

Matrices d'une application linéaire Espaces de Hilbert et théorème de projection Groupes Groupe symétrique et signature Le groupe linéaire et l'inversion des matrices Groupes de Lie et groupes de matrices Espaces vectoriels et sous-espaces Transformée de Fourier des fonctions intégrables Formule d'inversion de Fourier Théorème de Plancherel Espaces vectoriels normés et espaces de Banach Les anneaux ℤ/nℤ Théorème de Cartan-von Neumann Conjugaison et module Racines carrées et équations du second degré La fonction exponentielle