expansion with respect to p-norms for p other than 2 - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T18:51:16Z http://mathoverflow.net/feeds/question/104153 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/104153/expansion-with-respect-to-p-norms-for-p-other-than-2 expansion with respect to p-norms for p other than 2 Cristopher Moore 2012-08-06T22:08:01Z 2012-08-06T22:08:01Z <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 > 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 > 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>