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

  • 1
    $\begingroup$ Just a note: something like this is true in expectation for random $x \in \{\pm 1\}^n$, by Khintchine's inequality. $\endgroup$ Aug 7 '12 at 0:13
  • $\begingroup$ I agree. But I want something for all $x \in \{\pm 1\}^n$. $\endgroup$ Aug 8 '12 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.