About expectation norms on graphs

Question

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 two 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 }$

Answer 1

The decomposition should be taken with respect to the eigenvalues of $A/d$.

---

Discussion of the first inequality. There seems to be a slight mistake here: $V_{\ge\lambda}$ should be replaced with the orthogonal projection $P_{\ge \lambda}(G)$ onto this subspace. (Note that in the cited paper, both the statement of Theorem 2.4 and the discussion preceding the statement of Lemma B.1 all refer to projection operators, not subspaces. So Lemma B.1 should also refer to projection operators. Furthermore, the cited paper refers to this paper, which defines the norm in terms of projection operators on page 13.)

Since $f' = P_{\ge \lambda}(G) f$, it is immediate from the definition of $\|P_{\ge \lambda}(G)\|_{q/(q-1) \rightarrow 2}$ that $$\|f'\|_2 \le \|P_{\ge \lambda}(G)\|_{q/(q-1) \rightarrow 2} \, \|f\|_{q/(q-1)} .$$ (Trying to use $V_{\ge\lambda}$ instead of $P_{\ge \lambda}(G)$ would yield $f'$ on the right-hand side, instead of $f$, and that is no good.) Letting $p = q/(q-1)$ in the formula $\|f\|_p = \mu^{1/p}$ completes the proof.

---

Proof of the second inequality. Decompose $f$ as a sum of eigenvectors for $A/d$: $f = \sum_\tau f_\tau$ (where $\tau$ ranges over the eigenvalues of $A/d$). Then $$ \langle f , (A/d)f \rangle = \Bigl\langle \sum_\tau f_\tau , \sum_\tau \tau f_\tau \Bigr\rangle .$$ Since $G$ is a graph (not a digraph), the matrix $A/d$ is symmetric, so it is a fact of advanced undergraduate linear algebra that its eigenspaces are orthogonal. (This is a restatement of the fact that real symmetric matrices can be diagonalized by an orthogonal matrix.) Hence: $$ \Bigl\langle \sum_\tau f_\tau , \sum_\tau \tau f_\tau \Bigr\rangle = \sum_\tau \tau \|f_\tau\|_2^2 = \sum_{\tau< \lambda} \tau \|f_\tau\|_2^2 + \sum_{\tau\ge \lambda} \tau \|f_\tau\|_2^2 = \langle f'', (A/d)f'' \rangle + \langle f', (A/d)f' \rangle . $$ This completes the proof of the equality that is the left half of what is needed.

Now consider the inequality that constitutes the right half.

• It is obvious that $$ \sum_{\tau< \lambda} \tau \|f_\tau\|_2^2 \le \lambda \sum_{\tau< \lambda} \|f_\tau\|_2^2 = \lambda \|f''\|_2^2 .$$
• For the remaining part of the proof, note that every eigenvalue of $A/d$ is less than or equal to $1$. (This is both well known and easy to prove.) That is, we have $\tau \le 1$, so $$ \sum_{\tau \ge \lambda} \tau \|f_\tau\|_2^2 \le \sum_{\tau \ge \lambda} \|f_\tau\|_2^2 = \|f'\|_2^2 . $$