ENS Mathématiques D MP 2016

CONCOURS D'ADMISSION 2016
FILIÈRE MPI

(Durée : 6 heures)

L'utilisation des calculatrices n'est pas autorisée.

Ce problème est consacré à l'étude des spectres de graphes finis. À tout graphe fini - composé de sommets et d'arêtes reliant ces sommets - on associe une matrice dont les valeurs propres sont intimement liées aux propriétés géométriques du graphe. La première partie établit quelques estimations élémentaires des valeurs propres. La deuxième étudie le cas particulier du graphe à 60 sommets reproduisant la structure du Buckminsterfullerène. Dans une troisième partie, on relie la constante de Cheeger - dite aussi constante isopérimétrique - à la deuxième valeur propre du graphe puis on s'intéresse au cas des graphes planaires. Finalement, la quatrième partie étudie les propriétés des graphes découverts par Gabber et Galil en 1980. Ce sont des "graphes expanseurs" qui possèdent des propriétés de connectivité exceptionnelles. Mathématiquement, cela se traduit par une minoration uniforme de leur deuxième valeur propre.

On note le cardinal d'un ensemble fini . On appelle graphe un couple où est un ensemble fini non vide et est un sous-ensemble vérifiant la propriété suivante :

On appellera les éléments de les sommets et ceux de les arêtes. On dit que deux sommets et sont reliés par un chemin de longueur s'il existe une suite avec et pour .

Si pour tout il existe tel que et soient reliés par un chemin de longueur , le graphe sera dit connexe.

Pour tout sommet , on appelle valence de et on note le cardinal de l'ensemble tel que . On dira que est régulier si pour tout , on a .

Le graphe est biparti s'il existe des parties et de telles que avec , et qu'on a .

On note l'espace euclidien des fonctions de dans muni du produit scalaire défini par : pour tous . On notera la norme associée à ce produit scalaire. On définit l'endomorphisme de par la formule suivante :

pour toute application . On notera la fonction définie par : pour tout .

On rappelle que si est un endomorphisme symétrique d'un espace vectoriel euclidien de dimension , il existe une seule suite finie de nombres réels tels que la matrice de dans une base orthonormée soit une matrice diagonale de coefficients diagonaux . Pour on appellera la -ième valeur propre de . On appelle multiplicité d'une valeur propre de la dimension de l'espace propre correspondant.

Pour tout entier , on notera l'anneau des entiers modulo , l'algèbre des matrices carrées de taille à coefficients réels, le groupe des matrices inversibles de et le sous-groupe de formé des matrices orthogonales. Enfin on notera l'espace des endomorphismes d'un espace vectoriel .

Les parties II, III et IV sont indépendantes entre elles.

Fixons un graphe et posons . On supposera dans tout le sujet que l'on a .

Dans le reste de cette partie, on note les valeurs propres de .
2. Soit une base orthonormée de vérifiant pour tout .
2.a Montrer que pour tout on a :

où sont les coordonnées de dans la base . En déduire que .
2.b Notons la sphère unité de et pour tout notons l'orthogonal de dans . Montrer que pour tout on a :

et en déduire que pour tout .
2.c Pour tout , notons l'ensemble des sous-espaces vectoriels de dimension de . Montrer que pour tout on a :

Dans le reste de cette partie on suppose que le graphe est connexe.
3.a Montrer que le noyau de est engendré par la fonction constante égale à 1 .
3.b Calculer et montrer l'inégalité .
4. Posons .
4. a Montrer que toutes les valeurs propres de sont inférieures ou égales à (si est un vecteur propre de , on pourra considérer un sommet tel que est maximal).
4.b Montrer que si est biparti et régulier alors est valeur propre de .
4.c Prouver réciproquement que si est valeur propre de alors est régulier et biparti.
5. Soit un graphe vérifiant et soient les valeurs propres de .
5.a Montrer que pour tout , on a .
5.b Soit le graphe tels que . Calculer les valeurs propres de . En déduire que pour tout graphe , les valeurs propres de sont inférieures ou égales à .

Pour tout , on note le groupe des permutations de de signature +1 .
1.a Montrer que est engendré par le cycle (123).
1.b Montrer que est engendré par les éléments (123) et (12)(34) (on pourra se ramener au cas des permutations vérifiant .
1.c Montrer que est engendré par les éléments (12345) et (12)(34).

Dans le reste de cette partie, on pose où

2.c En déduire que toute valeur propre non nulle de est de multiplicité au moins 3 (on montrera qu'il n'y a pas de morphisme non trivial de vers les groupes et .
3. Soit le morphisme défini par

pour tout et pour tout .
3.a Soit le sous-espace de d'équation . Montrer que pour tout , l'espace est stable par : on note l'endomorphisme défini par pour tout . Montrer que la famille engendre linéairement .
3.b Déterminer à quelle condition sur , il existe tel que la fonction définie par soit une
fonction propre de pour la valeur propre . On pourra introduire la matrice suivante

dont on admettra que le polynôme caractéristique vérifie : pour tout .
3.c Montrer que chacune des valeurs propres de la question précédente est de multiplicité au moins 4 .

Soit un graphe connexe. Pour une partie de , on note tels que et . On appelle constante de Cheeger la quantité

Pour tout , il existe un chemin de longueur reliant à (avec si . On note la plus petite longueur d'un tel chemin et on pose :

et on rappelle que .
1.a Montrer que pour toute partie de , et que si , on a :

1.b En déduire l'inégalité suivante :

2.b En déduire l'inégalité .
3. On établit cette fois une minoration de la valeur propre .
3.a Pour , on note . Montrer l'inégalité .
3.b Soit une fonction vérifiant . Montrer l'inégalité (on pourra écrire avec et appliquer l'inégalité définissant pour tout vérifiant .
3.c En déduire l'inégalité .
4. Soit un espace vectoriel euclidien non nul. Dans cette partie, les notations et feront référence au produit scalaire de .
4.a Soit la fonction définie par pour tout . Montrer qu'on a l'égalité suivante : avec .
4.b On appelle plongement sphérique de dans une application : vérifiant les propriétés suivantes où on a posé pour tout :

Montrer qu'il existe un plongement sphérique du graphe défini en I.5.b dans un espace euclidien de dimension 3.
4.c Montrer que si admet un plongement sphérique dans un espace euclidien de dimension 3 alors on a l'inégalité . (Les arguments géométriques même incomplets seront valorisés).

Soit un entier supérieur ou égal à 2 et posons le groupe . On note le produit scalaire usuel de deux vecteurs et on pose . On notera la puissance -ième de que désigne un entier ou une classe modulo . De même, si , on note aussi . On note le groupe des matrices carrées de taille 2 à coefficients entiers de déterminant et la transposée de . 1. Notons l'espace vectoriel des fonctions de dans et on note pour et dans .
1.a Pour on définit par . Montrer que pour tout on a . En déduire que l'application est un isomorphisme de dans lui-même.
1.b Soit un élément de . Si et , notons pour tout . Montrer qu'on a

1.c Soit où

Montrer que est un graphe connexe et régulier et déterminer la deuxième valeur propre de en fonction de (on pourra considérer les fonctions définies par pour tous ).
2. Soit et . On définit l'endomorphisme de par la formule suivante où :
.
On prendra garde qu'il ne s'agit pas d'un endomorphisme associé à un graphe.
2.a Montrer que si est un vecteur propre de associé à une valeur propre non nulle alors on a : .
2.b Pour tout et tout on pose :

Montrer que si la propriété :

est satisfaite, alors toute valeur propre non nulle de vérifie (on pourra considérer l'endomorphisme de défini par pour tout ).
2.c Posons pour

Montrer que la propriété suivante implique la propriété :
positive avec on a .
2.d Si , notons l'unique représentant de modulo dans l'intervalle . On notera ou si et et que l'une des inégalités est stricte. Si on n'a ni ni , on dira que et ( ) sont incomparables.
Soit . Montrer que pour tout on a :