Exercise 16, § 2

We retain the notation of the preceding exercise, and we suppose that S and F are finite. We denote by $h_G$ the Cheeger constant of the graph G, defined by

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

$h_G=$ inf,

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

where $E(V,W)$ denotes the set of arrows of G with one end in V and one in W.

a) One has $\varrho (M_G) = 1$ and $\lambda = 1$ is an eigenvalue of $M_G$ of multiplicity 1. One has $-1\in$ Sp(M$_G$) if and only if G is bipartite (cf. TA, II, p. 219, exercise 2); in this case, the spectrum of $M_G$ is invariant under $\lambda \mapsto -\lambda$ and the spectral multiplicity of $\lambda$ is equal to that of $-\lambda$ for every $\lambda \in \mathbf{C}$.

We denote by $L^2_0(S, \nu )$ the orthogonal complement in $L^2_{\mathbf{C}}(S, \nu )$ of the union of the eigenspaces of $M_G$ corresponding to the eigenvalues 1 and $-1$. The endomorphism $M_G$ induces by passing to the subspaces an endomorphism of $L^2_0(S, \nu )$, denoted by $M_{G,0}$. One has $\varrho (M_{G,0})<1$. We denote by $\lambda_1(G)$ the smallest nonzero eigenvalue of $1-M_G$

b) Let $v_+=$ sup $v(x)$ and $v_-=$ inf $v(x)$. One has

c) Let $\varphi : S\rightarrow \mathbf{R}$ be a non-constant function on S with real values; let $m=$ inf$_{-1}\varphi (x)$ and M = sup $\varphi (x)$. Let $t_0\in \mathbf{R}$ be such that, for every $t\in \mathbf{R}$, the set $W_t=\varphi (]- \infty , t_0[)$ satisfies Card(W$_t$)$\leqslant$ Card(S)$/2$ if and only if $t < t_0$. Let $\nu$ be a diffuse measure (INT, V, p. 67, Def. 5) supported on $[m,M]$. Put

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

$B =\sum_{x\in S}\nu ([t_0, \varphi (x)])$, where, if $a < b$ are real numbers, we write $\nu ([b, a]) =\nu ([a, b])$. There exists $t\in \mathbf{R}$ such that

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

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

d) One has

(Apply the preceding question with $\varphi$ an eigenfunction of $M_G$ for the eigenvalue $\lambda_1(G)$ and for a suitably chosen measure $\nu$.)

e) A family $(G_j)_{j\in J}$ of finite graphs $G_j= (S_j,F_j, o_j, t_j, i_j)$ is said to be a family of expander graphs if the following conditions are satisfied:

(i) One has Card(S$_j$)$\rightarrow +\infty$ with respect to the filter of complements of finite subsets of J;

(ii) There exists $C\geqslant 0$ such that for every $j$ and every $x\in S_j$, the valency of $G_j$ at $x$ is $\leqslant C$;

(iii) There exists $\delta >0$ such that $h_{G_j}\geqslant \delta$ for every $j\in J$.

Now prove that $(G_j)$ is a family of expander graphs if and only if (i), (ii) are satisfied, as well as the condition

(iii’) There exists $\delta >0$ such that $\lambda_1(G_j)\geqslant \delta$ for every $j\in J$.