<p>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 </p>

<ul>
<li>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|$.</li>
</ul>

<p>My question is:</p>

<blockquote>
  <p>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?</p>
</blockquote>

<hr>

<p>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 <a href="http://portal.acm.org/citation.cfm?id=510003">Capalbo, Reingold, Vadhan and Wigderson</a>.
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.</p>

<p>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)&lt; |S_q|(k-1) + 1$.
Hence, $$|S_q| &lt; \frac{1}{1-\epsilon k} \text.$$</p>

<p>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| &gt; \frac{nk}{m}$, and we have $\frac{nk}{m}&lt; \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 &gt;0 $$ 
which, for sufficiently small $\epsilon$ and $n&gt;m$ forces $k&gt;\frac{1}{\epsilon}$ (or $k&lt;0$).</p>

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

CC BY-SA 3.0
2011-06-24T23:01:42.827Z
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)$.
Sasho Nikolov
CC BY-SA 3.0
2011-06-25T12:11:32.193Z
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}$.
Lior Eldar
CC BY-SA 3.0
2011-06-28T19:23:02.790Z
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...
Lior Eldar
<graph-theory><co.combinatorics><expanders>
Bi-partite expander graphs
Lior Eldar
# Bi-partite expander graphs

(Asked by: username_0 on 2011-06-24)

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](http://portal.acm.org/citation.cfm?id=510003).
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.

**Tags:** graph-theory, co.combinatorics, expanders
> **Comments:**
> **username_1**: 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)$.  
> **username_0**: 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}$.  
> **username_0**: 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...  

---

## 0 answers

