The permutation model is an expander with high probability

In the book Computational Complexity: A Modern Approach you can find the following problem enter image description here

this is actually a multi-graph with loops. Their definition of expander and a hint are attached below enter image description here enter image description here

My question is whether there's a reasonable proof of this excercise, or any that uses the hint. I am relatively convinced that the authors did not know how the proof for this excercise goes. A relatively straightforward calculation shows that for any $S$ as in the hint one has

$$\mathbb E[e(S,\overline S)]\geq d|S|$$ now, if $e(S,\overline S)$ was binomial, then a simple aplication of Chernoff plus a union bound would suffice, this is what I think the authours might've been thinking about; this random variable is in fact, not binomial. Otherwise, one might think to prove that the second largest eigenvalue of the stochastic adjacency matrix is at most $4/5$ with high probability, which would imply the expandedness property asked. From what I've researched online, this seem like the way to go. I've only found results that prove stronger things with very involved ideas and methods. See here where they prove $\lambda\leq \frac32 d^{-1/4}$ with probability $\geq 1-O\left(e^{-\sqrt d/2}\right)$ which is of course not good enough for constant $d$, and they consecture that there is some $\alpha<0$ such that $\lambda_2here where the author proves something that implies the excercise for $d\geq3$ but seems like too strong of a result and the proof is of course way more complicated than what I would expect for an excercise, and again uses the trace method; no mention of large deviations of edge counts.

Asides from that, I haven't been able to find any paper that implies the case $d=2$.

Even more evidence for the authors just thinking this was simpler than it was is that on a draft version of the book, they provide the following hint enter image description here

which to me seems like they're trying to prove vertex expansion instead of edge expansion. All of this makes me think they put the excercise, noticed they were thinking about something else and just said "Whatever, it's probably some Chernoff thing, can't be that hard". Am I going crazy?

Take Your Experience to the Next Level

New

Download our mobile app for a faster and better experience.

Comments

0
U

Join the discussion

Sign in to leave a comment

0:000:00