Is there a way to construct a bipartite $c$-expander graph, for a given $c >0$?

72 Views Asked by At

Suppose that $c > 0$ is a real number. Suppose that we are given integers $n > 0$ and $m > 0$. There are many bipartite graphs $G = (L, R, E)$ with $|L| = |R| = n$ vertices on each side and $|E| = m$ edges (let's suppose that we are given values of $n, m$ so that one exists). I am wondering whether there is a way to construct one (with high probability is good enough, if this construction is randomized) that is a $c$-expander in the following sense: for all $X \subseteq L$ (same for $X \subseteq R$) with $|X| \leq n/2$, we have that $|N(X)| \geq c|X|$.

If $m = dn$ for some constant $d$, then there is some value $c'(d)$ such that a random $d$-regular bipartite graph is a $c'$-expander. Is there a way to obtain a $c$-expander for any $c < c'$ in this model?

More generally, what are some ranges of values for $c$, $n$, $m$ for which this is possible?