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 p-expectation norm of functions. And for a vector space $W$ one defines $\Vert W \Vert_{p-> q} := max_{ g \in W} \frac{ \Vert g \Vert_q }{ \Vert g \vert _p}$ We also define the expectation inner product between two functions as $\langle g_1, g_2\rangle = \mathbb{E} [g_1(x)g_2(x) ] $ (...hence in particular we have, $\Vert f \Vert_p = \mu^{1/p}$ and $\langle f,f \rangle = \mu$...)

Now apparently the following identities hold,

• $\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?

Towards proving the above one can note the following identities between Euclidean (subscripted as $l_2$) inner products and the expectation innerproduct that,

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