My question relates to bi-partite expander graphs, defined as bi-partite graphs on $n$ left vertices, $m$ right vertices, constant left-degree $k$, such that

  • For any linear-sized subset $S$ of the left vertices of size $|S| = O(\gamma n)$ (where $\gamma$ is some constant), the set of right neighbors is close to full-expansion, i.e. $k (1-\epsilon) |S|$.

My question is:

What is known about the degrees of the right vertices? Is there a phenomenon, where some vertices have a very high degree, while others have a very small degree?

Below, is a proof that assuming that for every such expander all right vertices have degrees at most sublinear in $n$ implies some contradiction to a theorem by Capalbo, Reingold, Vadhan and Wigderson. This theorem states that for any $n,m,\epsilon$ there exists some $k = \mathrm{polylog}(n/m)$, $\gamma=g(n,m,\epsilon)$ for which there exists such a bi-partite expander.

Let $G$ be such a bi-partite expander. Let $q$ be some right vertex, and let $S_q$ be the set of left vertices adjacent to $q$. Suppose on the negative that each $|S_q|$ is of some bounded small size, and so it must abide by the expansion property. So the number of neighbors of $S_q$ is at least $|S_q|k(1-\epsilon)$. Yet, we know that since all vertices of $S_q$ share $q$ then the number of neighbors is upper-bounded by $|S_q|(k-1)+1$, and so $ |S_q|k(1-\epsilon)< |S_q|(k-1) + 1$. Hence, $$|S_q| < \frac{1}{1-\epsilon k} \text.$$

On the other hand, the number of edges is $nk$ and so there exists a right vertex of degree at least $\frac{nk}{m}$, and so there exists some $q$ for which $|S_q| > \frac{nk}{m}$, and we have $\frac{nk}{m}< \frac{1}{1-\epsilon k}$. This implies the following quadratic equation in variable $k$: $$ \frac{n \epsilon}{m}k^2 - \frac{n}{m}k + 1 >0 $$ which, for sufficiently small $\epsilon$ and $n>m$ forces $k>\frac{1}{\epsilon}$ (or $k<0$).

Yet, by the theorem $k< (\frac{n}{m})^t$ for some constant $t$ so $\frac{1}{\epsilon}< (\frac{n}{m})^t$. But one can easily choose $n,m,\epsilon$ which do not hold the above, by contradiction.

  • $\begingroup$ I don't see that the quadratic inequality forces $k > \epsilon^{-1}$. As far as I can see, for $\epsilon < \frac{n}{4m}$, you can take any $k$ satisfying $k < \frac{1}{2\epsilon}\left(1 - \sqrt{1 - \frac{4\epsilon}{n/m}}\right)$. $\endgroup$ – Sasho Nikolov Jun 24 '11 at 23:01
  • $\begingroup$ Regarding the quadratic, its roots are: $\frac{1}{2\epsilon}(1 \pm \sqrt{1-4\epsilon m/n})$, so approximating $ \sqrt{1-x} \sim 1-\frac{1}{2}x $ we get $ k< \frac{m}{n} $ or $k> \frac{1}{\epsilon} - \frac{m}{n}$. Taking $\frac{m}{n}$ to be very small we get that the lower bound on $k$ that is less than $1$, but $k$ must be a positive integer (degree of a graph node), so we can just ignore the low range, and assume $k> \frac{1}{\epsilon}$. $\endgroup$ – Lior Eldar Jun 25 '11 at 12:11
  • $\begingroup$ To the editors - I mistakenly wrote my answer to Sasho Nikolov as an answer to the question itself. Is it possible to move it here? I don't want people to get the impression that this question has been answered... $\endgroup$ – Lior Eldar Jun 28 '11 at 19:23

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.