Let $S \subseteq V$ of a $d-$regular graph $G$ such that $\mu = \frac{\vert S \vert }{\vert V \vert } $. Let $A$ be the adjacency matrix of the graph. Then define the quantity $\phi(S)= \frac{E(S,\bar{S})}{d \vert S \vert}$. Let $f$ be the characteristic vector of the set $S$. Let $V_{\geq \lambda}$ and $V_{< \lambda }$ be the subspaces be (adjacency? Laplacian?) eigenvalues $\geq \lambda$ and $< \lambda$ respectively. (I am not completely sure as to with which interpretation does the following hold!) Decompose $f = f' + f''$ along these spaces such that $f' \in V_{\geq \lambda}$ and $f'' \in V_{< \lambda}$

Let $\Vert g \Vert_p := ( \mathbb{E} \vert g \vert ^{p} )^{1/p}$ be the expectation norms of functiions. And for vector spaces one defines $\Vert W \Vert_{p-> q} := max_{ g \in W} \frac{ \Vert g \Vert_q }{ \Vert g \vert _p}$

Now apparently the following identities hold,

• $\phi (S) = 1 - \frac{\langle f, (A/d)f \rangle }{\Vert f \Vert_2^2 } = 1 - \frac{ \langle f, (A/d)f \rangle }{\mu } $

• Since $\Vert f \Vert_{q/(q-1) } = \mu^{ (q-1)/q }$ it follows that $\Vert f' \Vert_2 \leq \Vert V_{ \geq \lambda}\Vert_{q/(q-1) -> 2 } \mu ^{(q-1)/q }$

• $\langle f, (A/d)f \rangle = \langle f', (A/d)f' \rangle + \langle f'',(A/d)f''\rangle \leq \Vert f' \Vert_2^2 + \lambda \Vert f'' \Vert_2^2$

• Can someone kindly help prove the above identities?