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
