ENS Mathématiques D MP 2016Sujet et corrigé

Q: Sur quels chapitres porte le sujet de mathématiques D de l'ENS MPI 2016 ?

Il porte sur la réduction des endomorphismes symétriques, appliquée à l'étude spectrale de graphes finis, avec des incursions en théorie des groupes et en analyse combinatoire.

Q: Quelles parties sont indépendantes dans ce sujet de l'ENS 2016 ?

Les parties II, III et IV sont indépendantes entre elles ; la partie I introduit les notations et résultats utilisés dans les suivantes.

Q: Faut-il des connaissances en théorie des groupes pour ce sujet de l'ENS ?

Oui, la partie II utilise les propriétés du groupe alterné A5 et de ses générateurs, ainsi que des morphismes vers les groupes orthogonaux.

Q: Le sujet de mathématiques D de l'ENS MPI 2016 autorise-t-il la calculatrice ?

Non, l'énoncé précise que l'utilisation des calculatrices n'est pas autorisée.

Pas encore noté

Explorer les annales

BanqueX-ENS Année2016 FilièreMP MatièreMathématiques

Annales X-ENS MP Mathématiques X-ENS MP 2016 MP Mathématiques Mathématiques 2016

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Lire en ligne LaTeX Word

Rapport du jury : non disponible

Présentation du sujet

Spectres de graphes finis : estimations de valeurs propres, graphe du groupe alterné A5, constante de Cheeger et graphes expanseurs de Gabber-Galil

Ce problème associe à tout graphe fini un endomorphisme symétrique T_G dont les valeurs propres sont liées aux propriétés géométriques du graphe. Après des estimations élémentaires sur ces valeurs propres, le sujet étudie le graphe de Cayley du groupe alterné A5, qui reproduit la structure du Buckminsterfullerène, puis relie la constante de Cheeger (isopérimétrique) à la deuxième valeur propre. Il se termine par l'étude des graphes de Gabber-Galil, des graphes expanseurs à forte connectivité.

1Partie IÉtablit des estimations élémentaires des valeurs propres de l'endomorphisme T_G, notamment via un principe variationnel de type min-max.
2Partie IIÉtudie le graphe construit sur le groupe alterné A5 et montre que ses valeurs propres non nulles ont une multiplicité minorée.
3Partie IIIRelie la constante de Cheeger d'un graphe à sa deuxième valeur propre, par un encadrement, puis s'intéresse aux graphes planaires via un plongement sphérique.
4Partie IVÉtudie les graphes expanseurs de Gabber-Galil construits sur (Z/nZ)^2 et minore leur deuxième valeur propre par une inégalité de convexité.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

ÉCOLE NORMALE SUPÉRIEURE

CONCOURS D'ADMISSION 2016
FILIÈRE MPI

COMPOSITION DE MATHÉMATIQUES - D - (U)

(Durée : 6 heures)

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

Préambule

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.

Notations

On note

|X|

le cardinal d'un ensemble fini

X

. On appelle graphe un couple

G = (V, E)

où

V

est un ensemble fini non vide et

E \subset V \times V

est un sous-ensemble vérifiant la propriété suivante :

\forall(x, y) \in E, x \neq y et (y, x) \in E.

On appellera les éléments de

V

les sommets et ceux de

E

les arêtes. On dit que deux sommets

x

y

sont reliés par un chemin de longueur

k \in ℕ

s'il existe une suite

(x_i)_(i = 0, \dots, k)

avec

x_0 = x, x_k = y

(x_i, x_(i + 1)) \in E

pour

i = 0, \dots, k - 1

Si pour tout

x, y \in V

il existe

k \in ℕ

tel que

x

y

soient reliés par un chemin de longueur

k

, le graphe

G

sera dit connexe.

Pour tout sommet

x \in V

, on appelle valence de

x

et on note

val(x)

le cardinal de l'ensemble

{y \in V

tel que

(x, y) \in E}

. On dira que

G

est régulier si pour tout

x, y \in V

, on a

val(x) = val(y)

Le graphe

G

est biparti s'il existe des parties

A

B

V

telles que

V = A \cup B

avec

A \cap B = \emptyset

, et qu'on a

E \subset A \times B \cup B \times A

On note

ℝ^V

l'espace euclidien des fonctions de

V

dans

ℝ

muni du produit scalaire défini par :

⟨f, g⟩ = \sum_(x \in V)f(x)g(x)

pour tous

f, g \in ℝ^V

. On notera

‖ \cdot ‖

la norme associée à ce produit scalaire. On définit l'endomorphisme

T_G

ℝ^V

par la formule suivante :

(T_G f)(x) = \sum_(y \in V tel que (x, y) \in E)(f(x) - f(y)) pour tout x \in E

pour toute application

f \in ℝ^V

. On notera

q_G

la fonction définie par :

q_G(f) = ⟨T_G f, f⟩

pour tout

f \in ℝ^V

On rappelle que si

A

est un endomorphisme symétrique d'un espace vectoriel euclidien de dimension

n

, il existe une seule suite finie de nombres réels

λ_1 \leq \dots \leq λ_n

tels que la matrice de

A

dans une base orthonormée soit une matrice diagonale de coefficients diagonaux

λ_1, \dots, λ_n

. Pour

k \in {1, \dots, n}

on appellera

λ_k

k

-ième valeur propre de

A

. On appelle multiplicité d'une valeur propre de

A

la dimension de l'espace propre correspondant.

Pour tout entier

n \in ℕ^*

, on notera

ℤ/nℤ

l'anneau des entiers modulo

n

M_n(ℝ)

l'algèbre des matrices carrées de taille

n

à coefficients réels,

GL_n(ℝ)

le groupe des matrices inversibles de

M_n(ℝ)

O(n)

le sous-groupe de

GL_n(ℝ)

formé des matrices orthogonales. Enfin on notera

End(V)

l'espace des endomorphismes d'un espace vectoriel

V

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

I

Fixons un graphe

G = (V, E)

et posons

n = |V|

. On supposera dans tout le sujet que l'on a

n \geq 2

Montrer que $T_G$ est un endomorphisme symétrique de $ℝ^V$ et que pour tout $f \in ℝ^V$ , on a :

q_G(f) = 1/2\sum_((x, y) \in E)(f(x) - f(y))^2.

Dans le reste de cette partie, on note

λ_1 \leq \dots \leq λ_n

les valeurs propres de

T_G

.
2. Soit

(e_1, \dots, e_n)

une base orthonormée de

ℝ^V

vérifiant

T_G(e_i) = λ_i e_i

pour tout

i \in {1, \dots, n}

.
2.a Montrer que pour tout

f \in ℝ^V

on a :

q_G(f) = \sum_(i = 1)^n λ_i f_i^2

où

(f_1, \dots, f_n)

sont les coordonnées de

f

dans la base

(e_1, \dots, e_n)

. En déduire que

λ_1 \geq 0

.
2.b Notons

S

la sphère unité de

ℝ^V

et pour tout

k \in {1, \dots, n}

notons

F_k

l'orthogonal de

ℝe_1 + \dotsℝe_(k - 1)

dans

ℝ^V

. Montrer que pour tout

k \in {1, \dots, n}

on a :

λ_k = inf_(f \in F_k \cap S)q_G(f)

et en déduire que

q_G(f) \geq λ_k‖f‖^2

pour tout

f \in F_k

.
2.c Pour tout

k \in {1, \dots, n}

, notons

W_k

l'ensemble des sous-espaces vectoriels de dimension

k

ℝ^V

. Montrer que pour tout

k \in {1, \dots, n}

on a :

λ_k = inf_(W \in W_k)(sup_(f \in W \cap S)q_G(f)).

Dans le reste de cette partie on suppose que le graphe

G

est connexe.
3.a Montrer que le noyau de

T_G

est engendré par la fonction constante égale à 1 .
3.b Calculer

λ_1

et montrer l'inégalité

λ_2 > 0

.
4. Posons

d_G = max{val(x), x ∈ V}

.
4. a Montrer que toutes les valeurs propres de

T_G

sont inférieures ou égales à

2d_G

(si

f

est un vecteur propre de

T_G

, on pourra considérer un sommet

x \in V

tel que

|f(x)|

est maximal).
4.b Montrer que si

G

est biparti et régulier alors

2d_G

est valeur propre de

T_G

.
4.c Prouver réciproquement que si

2d_G

est valeur propre de

T_G

alors

G

est régulier et biparti.
5. Soit

G^' = (V, E^')

un graphe vérifiant

E^' \subset E

et soient

λ_1^' \leq \dots \leq λ_n^'

les valeurs propres de

T_(G^')

.
5.a Montrer que pour tout

k \in {1, \dots, n}

, on a

λ_k^' \leq λ_k

.
5.b Soit

K_n

le graphe

({1, …, n}, {(i, j) ∈ {1, …, n}^2

tels que

i \neq j})

. Calculer les valeurs propres de

T_(K_n)

. En déduire que pour tout graphe

G = (V, E)

, les valeurs propres de

T_G

sont inférieures ou égales à

|V|

II

Pour tout

n \in ℕ^*

, on note

A_n

le groupe des permutations de

{1, \dots, n}

de signature +1 .
1.a Montrer que

A_3

est engendré par le cycle (123).
1.b Montrer que

A_4

est engendré par les éléments (123) et (12)(34) (on pourra se ramener au cas des permutations

σ \in A_4

vérifiant

σ(4) = 4)

.
1.c Montrer que

A_5

est engendré par les éléments

a =

(12345) et

b =

(12)(34).

Dans le reste de cette partie, on pose

G = (A_5, E)

où

E = {(g, h) ∈ A_5, g^(− 1)h ∈ {a, a^(− 1), b}}.

Pour $g \in A_5$ , on note $L_g$ l'endomorphisme de $ℝ^V$ défini par $(L_g f)(x) = f(g^(- 1)x)$ pour tout $f \in ℝ^V$ et pour tout $x \in A_5$ .
2.a Montrer que $G$ est un graphe connexe et régulier.
2.b Montrer que $L_g$ est une isométrie de $ℝ^V$ qui vérifie les identités suivantes :

\forallg, h \in A_5, L_g \circ L_h = L_(gh) et T_G \circ L_g = L_g \circ T_G.

2.c En déduire que toute valeur propre non nulle de

T_G

est de multiplicité au moins 3 (on montrera qu'il n'y a pas de morphisme non trivial de

A_5

vers les groupes

O(1)

O(2))

.
3. Soit

ρ : A_5 \to GL_5(ℝ)

le morphisme défini par

ρ(g)(x) = (x_(g^(- 1)(1)), \dots, x_(g^(- 1)(5)))

pour tout

g \in A_5

et pour tout

x = (x_1, \dots, x_5) \in ℝ^5

.
3.a Soit

F

le sous-espace de

ℝ^5

d'équation

x_1 + x_2 + x_3 + x_4 + x_5 = 0

. Montrer que pour tout

g \in A_5

, l'espace

F

est stable par

ρ(g)

: on note

ρ~(g) \in End(F)

l'endomorphisme défini par

ρ~(g)(x) = ρ(g)(x)

pour tout

x \in F

. Montrer que la famille

(ρ~(g))_(g \in A_5)

engendre linéairement

End(F)

.
3.b Déterminer à quelle condition sur

λ \in ℝ

, il existe

M \in End(F)

tel que la fonction

f \in ℝ^V

définie par

f(g) = Tr(ρ~(g)M)

soit une
fonction propre de

T_G

pour la valeur propre

λ

. On pourra introduire la matrice suivante

A = (3, - 2, 0, 0, - 1; - 2, 3, - 1, 0, 0; 0, - 1, 3, - 2, 0; 0, 0, - 2, 3, - 1; - 1, 0, 0, - 1, 2)

dont on admettra que le polynôme caractéristique vérifie :

P(x) = det(xI_5 - A) = x(x - 2)(x - 5)(x^2 - 7x + 8)

pour tout

x \in ℝ

.
3.c Montrer que chacune des valeurs propres de la question précédente est de multiplicité au moins 4 .

III

Soit

G = (V, E)

un graphe connexe. Pour une partie

A

V

, on note

\partialA = {(x, y) \in E

tels que

x \in A

y \in V∖A}

. On appelle constante de Cheeger la quantité

h_G = inf{(|∂A|)/(|A|), A ⊂ V tel que 0 < |A| ≤ (|V|)/2}

Pour tout

x, y \in V

, il existe un chemin de longueur

k \in ℕ

reliant

x

y

(avec

k = 0

x = y)

. On note

d(x, y)

la plus petite longueur d'un tel chemin et on pose :

Δ_G = max_((x, y) \in V^2)d(x, y)

Montrer que pour tous $x, y, z \in V$ on a : $d(x, y) = d(y, x)$ et $d(x, z) \leq d(x, y) + d(y, z)$ .
Pour toute partie $A$ de $V$ et pour tout $k \in ℕ$ , on note :

B(A, k) = {x \in V, \existsy \in A, d(x, y) \leq k}

et on rappelle que

d_G = max{val(x), x ∈ V}

.
1.a Montrer que

B(A, 0) = A

pour toute partie

A

V

, et que si

|A| \leq |V|/2

, on a :

|B(A, 1)| \geq (1 + (h_G)/(d_G))|A|

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

Δ_G \leq (2ln(|V|/2))/(ln(1 + h_G/d_G)) + 2

Notons $λ_2$ la deuxième valeur propre de $T_G$ .
2.a Soit $A$ et $B$ deux parties de $V$ non vides telles que $A \cup B = V$ et $A \cap B = \emptyset$ . Notons $a = |A|$ et $b = |B|$ et soit $f : V \to ℝ$ la fonction définie par $f|_A = b$ et $f|_B = - a$ . Montrer que $f$ est orthogonale au noyau de $T_G$ et vérifie :

q_G(f) = ((a + b)|\partialA|)/(ab)‖f‖^2.

2.b En déduire l'inégalité

λ_2 \leq 2h_G

.
3. On établit cette fois une minoration de la valeur propre

λ_2

.
3.a Pour

f \in ℝ^V

, on note

S(f) = 1/2\sum_((x, y) \in E)|f(x)^2 - f(y)^2|

. Montrer l'inégalité

S(f) \leq \sqrt(2d_G q_G(f))‖f‖

.
3.b Soit

f : V \to [0, + \infty[

une fonction vérifiant

|f^(- 1)(]0, + \infty[)| \leq |V|/2

. Montrer l'inégalité

S(f) \geq h_G‖f‖^2

(on pourra écrire

V = {x_1, …, x_n}

avec

f(x_1) \geq f(x_2)\dots \geq f(x_n)

et appliquer l'inégalité définissant

h_G a^‵A = {x_1, …, x_k}

pour tout

k

vérifiant

k \leq n/2)

.
3.c En déduire l'inégalité

λ_2 \geq (h_G^2)/(2d_G)

.
4. Soit

E

un espace vectoriel euclidien non nul. Dans cette partie, les notations

‖ \cdot ‖

⟨ \cdot, \cdot ⟩

feront référence au produit scalaire de

E

.
4.a Soit

Q : E^V \to ℝ

la fonction définie par

Q(f) = 1/2\sum_((x, y) \in E)‖f(x) - f(y)‖^2

pour tout

f \in E^V

. Montrer qu'on a l'égalité suivante :

λ_2 = inf_(f \in S)Q(f)

avec

S = {f : V → E, ∑_(x ∈ V)‖f(x)‖^2 = 1, ∑_(x ∈ V)f(x) = 0}

.
4.b On appelle plongement sphérique de

G

dans

E

une application

u

V \to E

vérifiant les propriétés suivantes où on a posé

D(x) = {w \in E, ‖w‖ = 1, ⟨u(x), w - u(x)⟩ > 0}

pour tout

x \in V

pour tout $x \in V, 0 < ‖u(x)‖ < 1$ .
$\sum_(x \in V)(u(x))/(‖u(x)‖) = 0$ .
pour tout $x, y \in V$ tels que $x \neq y$ on a $D(x) \cap D(y) = \emptyset$ et $(D(x)^- \cap D(y)^- \neq \emptyset) ⟺ ((x, y) \in E)$ .

Montrer qu'il existe un plongement sphérique du graphe

K_4

défini en I.5.b dans un espace euclidien de dimension 3.
4.c Montrer que si

G

admet un plongement sphérique dans un espace euclidien de dimension 3 alors on a l'inégalité

λ_2 \leq 8(d_G)/(|V|)

. (Les arguments géométriques même incomplets seront valorisés).

IV

Soit

n

un entier supérieur ou égal à 2 et posons

H_n

le groupe

(ℤ/nℤ)^2

. On note

x \cdot y

le produit scalaire usuel de deux vecteurs

x, y \in ℤ^2

et on pose

ω = exp((2iπ)/n)

. On notera

ω^k

la puissance

k

-ième de

ω

que

k

désigne un entier ou une classe modulo

n

. De même, si

x, y \in H_n

, on note aussi

x \cdot y \in ℤ/nℤ

. On note

GL_2(ℤ)

le groupe des matrices carrées de taille 2 à coefficients entiers de déterminant

\pm 1

A^T

la transposée de

A \in GL_2(ℤ)

. 1. Notons

H_n

l'espace vectoriel des fonctions de

H_n

dans

ℂ

et on note

⟨f, g⟩ = \sum_(x \in H_n)f(x)^-g(x)

pour

f

g

dans

H_n

.
1.a Pour

f \in H_n

on définit

f^ \in H_n

par

f^(x) = \sum_(y \in H_n)f(y)ω^(- x \cdot y)

. Montrer que pour tout

f, g \in H_n

on a

⟨f^, g^⟩ = n^2⟨f, g⟩

. En déduire que l'application

f \mapsto f^

est un isomorphisme de

H_n

dans lui-même.
1.b Soit

f

un élément de

H_n

. Si

A \in GL_2(ℤ)

b \in ℤ^2

, notons

g(x) = f(Ax + b)

pour tout

x \in H_n

. Montrer qu'on a

g^(x) = ω^((A^(- 1)b) \cdot x)f^((A^(- 1))^T x)

1.c Soit

G = (H_n, E)

où

E = {(x, y) ∈ H_n^2, x − y ∈ {(1, 0), (− 1, 0), (0, 1), (0, − 1)}}.

Montrer que

G

est un graphe connexe et régulier et déterminer la deuxième valeur propre

λ_2

T_G

en fonction de

n

(on pourra considérer les fonctions

χ_y \in H_n

définies par

χ_y(x) = ω^(y \cdot x)

pour tous

x, y \in H_n

).
2. Soit

T_1 = (1, 2; 0, 1), T_2 = (1, 0; 2, 1), e_1 = (1/0)

e_2 = (0/1)

. On définit l'endomorphisme

T

H_n

par la formule suivante où

f \in H_n

(Tf)(x) = 4f(x) - f(T_1 x) - f(T_2 x) - f(T_1 x + e_1) - f(T_2 x + e_2), \forallx \in H_n

.
On prendra garde qu'il ne s'agit pas d'un endomorphisme associé à un graphe.
2.a Montrer que si

f

est un vecteur propre de

T

associé à une valeur propre non nulle alors on a :

\sum_(x \in H_n)f(x) = 0

.
2.b Pour tout

F \in H_n

et tout

x = (x_1, x_2) \in H_n

on pose :

(UF)(x) = F(T_2^(- 1)x)(1 + ω^(- x_1)) + F(T_1^(- 1)x)(1 + ω^(- x_2)).

Montrer que si la propriété :

(T1)\forallF \in H_n tel que F(0, 0) = 0 on a |⟨F, UF⟩| \leq (73)/(20)⟨F, F⟩

est satisfaite, alors toute valeur propre non nulle

λ

T

vérifie

|λ| \geq 7/(20)

(on pourra considérer l'endomorphisme

T^

H_n

défini par

T^f^ = Tfˆ

pour tout

f \in H_n

).
2.c Posons pour

x = (x_1, x_2) \in H_n

(U^' G)(x) = G(T_2^(- 1)(x))|cos((πx_1)/n)| + G(T_1^(- 1)(x))|cos((πx_2)/n)|.

Montrer que la propriété suivante implique la propriété

(T1)

(T2)\forallG : H_n \to ℝ

positive avec

G(0, 0) = 0

on a

⟨G, U^' G⟩ \leq (73)/(40)⟨G, G⟩

.
2.d Si

x \in ℤ

, notons

x¯

l'unique représentant de

x

modulo

n

dans l'intervalle

[ - n/2, n/2[

. On notera

(x_1, x_2)≺(y_1, y_2)

(y_1, y_2)≻(x_1, x_2)

|x_1^-| \leq |y_1^-|

|x_2^-| \leq |y_2^-|

et que l'une des inégalités est stricte. Si on n'a ni

(x_1, x_2)≺(y_1, y_2)

(x_1, x_2)≻(y_1, y_2)

, on dira que

(x_1, x_2)

et (

y_1, y_2

) sont incomparables.
Soit

D_n = {(x_1, x_2) ∈ [ − n/2, n/2[^2, |x_1| + |x_2| < n/2}

. Montrer que pour tout

x ∈ D_n∖{(0, 0)}

on a :

soit trois points parmi $T_1 x, T_2 x, T_1^(- 1)x, T_2^(- 1)x$ sont $≻x$ et l'un est $≺x$ .
soit deux points parmi $T_1 x, T_2 x, T_1^(- 1)x, T_2^(- 1)x$ sont $≻x$ et deux sont incomparables à $x$ .
2.e Notons $γ : H_n^2 → {4/5, 1, 5/4}$ la fonction définie par $γ(x, y) = 5/4$ si $x≻y, γ(x, y) = 4/5$ si $x≺y$ et $γ(x, y) = 1$ sinon. Montrer pour tout $x = (x_1, x_2) ∈ H_n∖{(0, 0)}$ l'inégalité

|cos((πx_1)/n)|(γ(x, T_2 x), + γ(x, T_2^(- 1)x)); + |cos((πx_2)/n)|(γ(x, T_1 x) + γ(x, T_1^(- 1)x)) \leq (73)/(20)

2.f Montrer que pour toute fonction

G : H_n \to ℝ_+

et tous

x, y \in H_n

on a:

2G(x)G(y) \leq γ(x, y)G^2(x) + γ(y, x)G^2(y)

et en déduire que la propriété (T2) est vérifiée.

Questions fréquentes

4 questions

Sur quels chapitres porte le sujet de mathématiques D de l'ENS MPI 2016 ?

Il porte sur la réduction des endomorphismes symétriques, appliquée à l'étude spectrale de graphes finis, avec des incursions en théorie des groupes et en analyse combinatoire.

Quelles parties sont indépendantes dans ce sujet de l'ENS 2016 ?

Les parties II, III et IV sont indépendantes entre elles ; la partie I introduit les notations et résultats utilisés dans les suivantes.

Faut-il des connaissances en théorie des groupes pour ce sujet de l'ENS ?

Oui, la partie II utilise les propriétés du groupe alterné A5 et de ses générateurs, ainsi que des morphismes vers les groupes orthogonaux.

Le sujet de mathématiques D de l'ENS MPI 2016 autorise-t-il la calculatrice ?

Non, l'énoncé précise que l'utilisation des calculatrices n'est pas autorisée.

Pas de description pour le moment

Commentaires• ENS Mathématiques D MP 2016

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...