Exercice 16, § 2

On conserve les notations de l’exercice précédent, et on suppose que S et F sont finis. On note $h_G$ la constante de Cheeger du graphe G, définie par

Card(E(V$,S$ - V))

$h_G=$ inf,

$_{\emptyset\not=V\subset S}$ inf(Card(V), Card(S - V))

où $E(V,W)$ désigne l’ensemble des flèches de G dont une extrémité est dans V et une dans W.

a) On a $\varrho (M_G) = 1$ et $\lambda = 1$ est une valeur propre de $M_G$ de multiplicité 1. On a $-1\in$ Sp(M$_G$) si et seulement si G est bipartite (cf. TA, II, p. 219, exercice 2) ; dans ce cas, le spectre de $M_G$ est invariant par $\lambda \mapsto -\lambda$ et la multiplicité spectrale de $\lambda$ est égale à celle de $-\lambda$ pour tout $\lambda \in \mathbf{C}$.

On note $L^2_0(S, \nu )$ l’orthogonal dans $L^2_{\mathbf{C}}(S, \nu )$ de l’union des sous-espaces propres de $M_G$ relatifs aux valeurs propres 1 et $-1$. L’endomorphisme $M_G$ induit par passage aux sous-espaces un endomorphisme de $L^2_0(S, \nu )$, noté $M_{G,0}$. On a $\varrho (M_{G,0})<1$. On note $\lambda_1(G)$ la plus petite valeur propre non nulle de $1-M_G$

b) Soient $v_+=$ sup $v(x)$ et $v_-=$ inf $v(x)$. On a

c) Soit $\varphi : S\rightarrow \mathbf{R}$ une fonction non constante sur S à valeurs réelles ; soient $m=$ inf$_{-1}\varphi (x)$ et M = sup $\varphi (x)$. Soit $t_0\in \mathbf{R}$ tel que, pour tout $t\in \mathbf{R}$, l’ensemble $W_t=\varphi (]- \infty , t_0[)$ vérifie Card(W$_t$)$\leqslant$ Card(S)$/2$ si et seulement si $t < t_0$. Soit $\nu$ une mesure diffuse (INT, V, p. 67, déf. 5) supportée sur $[m,M]$. Posons

$(x,y)\in S^2$

$B =\sum_{x\in S}\nu ([t_0, \varphi (x)])$, où, si $a < b$ sont des nombres réels, on note $\nu ([b, a]) =\nu ([a, b])$. Il existe $t\in \mathbf{R}$ tel que

Card(E(W$_t,S$ - $W_t$) A

inf(Card(W$_t$), Card(S - $W_t$)) B

d) On a

(Appliquer la question précédente avec $\varphi$ fonction propre de $M_G$ pour la valeur propre $\lambda_1(G)$ et pour une mesure $\nu$ bien choisie.)

e) On dit qu’une famille $(G_j)_{j\in J}$ de graphes finis $G_j= (S_j,F_j, o_j, t_j, i_j)$ est une famille de graphes expanseurs si les conditions suivantes sont vérifiées :

(i) On a Card(S$_j$)$\rightarrow +\infty$ selon le filtre des complémentaires des parties finies de J ;

(ii) Il existe $C\geqslant 0$ tel que pour tout $j$ et tout $x\in S_j$, la valence de $G_j$ en $x$ est $\leqslant C$;

(iii) Il existe $\delta >0$ tel que $h_{G_j}\geqslant \delta$ pour tout $j\in J$.

Montrer que $(G_j)$ est une famille de graphes expanseurs si et seulement si (i), (ii) sont vérifiées ainsi que la condition

(iii’) Il existe $\delta >0$ tel que $\lambda_1(G_j)\geqslant \delta$ pour tout $j\in J$.