MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
This is probably known to you, but there is a simple bound based on interpolation that does not use either expansion or symmetry. For any stochastic matrix $A$, we have $||A||_{\infty} = 1$, and so by the Riesz-Thorin theorem, $$ ||A||_p \leq ||A||_2^{2/p}$$ for all $p \geq 2$. – alex o. Aug 7 '12 at 1:02
Right. But none of these norm interpolation inequalities seems to give a bound $\| Ax \|_p^p \le \lambda^\alpha$ for $\alpha > 2$. – Cristopher Moore Aug 8 '12 at 19:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.