<p>Suppose I have an $d$-regular expander graph with $n$ vertices, where the stochastic version of its adjacency matrix $A$ (with entries $1/d$ and zero) has second eigenvalue $\lambda$.  </p>

<p>Let $x \in {\mathbb C}^n$ be a vector whose components are on the unit circle, i.e. $|x_i|=1$ for all $1 \le i \le n$.  Note that the $k$-norm of $x$ is $|x|_k^k = \sum_i |x_i|^k = n$ for any $k &gt; 0$.  Furthermore, suppose that $x$ is perpendicular to the uniform vector, so that ${\mathbb E}_i x_i=0$.  Then </p>

<p>${\mathbb E}_i |(Ax)_i|^2 = \frac{1}{n} |Ax|_2^2 \le \lambda^2$.</p>

<p>Can we say anything about the $k$-norm of $Ax$, </p>

<p>${\mathbb E}_i |(Ax)_i|^k = \frac{1}{n} |Ax|_k^k$</p>

<p>for $k \ge 2$?  For instance, is </p>

<p>$\frac{1}{n} |Ax|_3^3 \le \lambda^\alpha$ for some $\alpha &gt; 2$?</p>

<p>If $x_i = \pm 1$ for all $i$, then this has to do with how nonuniform the neighborhoods are.  If a $\lambda^2$ fraction of vertices $i$ have the same value of $x_j$ for all their neighbors $j$ so that $|(Ax)_i|=1$, and the other $1-\lambda^2$ fraction have half $x_j=+1$ and half $x_j=-1$ so that $(Ax)_i=0$, then ${\mathbb E}_i |(Ax)_i|^k = \lambda$ for all $k$.  But is this possible?  If there is more of a spread in the fraction of neighbors $j$ with $a_j=+1$, then perhaps an nice inequality holds.</p>

<p>I am especially interested in the case of Ramanujan-like graphs, where $\lambda = O(1/\sqrt{d})$.</p>

<p>Thanks!
- Cris</p>

CC BY-SA 3.0
2012-08-07T00:13:26.317Z
Just a note: something like this is true in expectation for random $x \in \{\pm 1\}^n$, by Khintchine's inequality.
Sasho Nikolov
CC BY-SA 3.0
2012-08-08T05:11:36.847Z
I agree.  But I want something for all $x \in \{\pm 1\}^n$.
Cristopher Moore
<co.combinatorics><spectral-graph-theory><expanders><norms>
expansion with respect to p-norms for p other than 2
Cristopher Moore
# expansion with respect to p-norms for p other than 2

(Asked by: username_0 on 2012-08-06)

Suppose I have an $d$-regular expander graph with $n$ vertices, where the stochastic version of its adjacency matrix $A$ (with entries $1/d$ and zero) has second eigenvalue $\lambda$.

Let $x \in {\mathbb C}^n$ be a vector whose components are on the unit circle, i.e. $|x\_i|=1$ for all $1 \le i \le n$. Note that the $k$-norm of $x$ is $|x|\_k^k = \sum\_i |x\_i|^k = n$ for any $k > 0$. Furthermore, suppose that $x$ is perpendicular to the uniform vector, so that ${\mathbb E}\_i x\_i=0$. Then

${\mathbb E}\_i |(Ax)\_i|^2 = \frac{1}{n} |Ax|\_2^2 \le \lambda^2$.

Can we say anything about the $k$-norm of $Ax$,

${\mathbb E}\_i |(Ax)\_i|^k = \frac{1}{n} |Ax|\_k^k$

for $k \ge 2$? For instance, is

$\frac{1}{n} |Ax|\_3^3 \le \lambda^\alpha$ for some $\alpha > 2$?

If $x\_i = \pm 1$ for all $i$, then this has to do with how nonuniform the neighborhoods are. If a $\lambda^2$ fraction of vertices $i$ have the same value of $x\_j$ for all their neighbors $j$ so that $|(Ax)\_i|=1$, and the other $1-\lambda^2$ fraction have half $x\_j=+1$ and half $x\_j=-1$ so that $(Ax)\_i=0$, then ${\mathbb E}\_i |(Ax)\_i|^k = \lambda$ for all $k$. But is this possible? If there is more of a spread in the fraction of neighbors $j$ with $a\_j=+1$, then perhaps an nice inequality holds.

I am especially interested in the case of Ramanujan-like graphs, where $\lambda = O(1/\sqrt{d})$.

Thanks!
- Cris

**Tags:** co.combinatorics, spectral-graph-theory, expanders, norms

> **Comments:**
> **username_1**: Just a note: something like this is true in expectation for random $x \in \{\pm 1\}^n$, by Khintchine's inequality.  
> **username_0**: I agree.  But I want something for all $x \in \{\pm 1\}^n$.  

---

## 0 answers

