# Random unbalanced bipartite graphs are good small set expanders

My question is about small set expansion properties of random unbalanced bipartite graphs.

Fix a positive $$\delta<1/2$$, and a positive integers $$n,m,d$$. Let us call a bipartite graph $$\mathcal{G}$$ an $$(n,m,d,\delta)$$-expander if the graph has $$n$$ left vertices, $$m$$ right vertices, every left vertex has degree $$d$$, and for every subset $$S$$ of left vertices having size at most $$\delta n$$, we have $$|\mathcal{N}(S)|>0.75 d|S|$$. Here $$\mathcal{N}(S)$$ denotes the set of neighbours of $$S$$.

Consider a random $$d$$-left regular graph, where the neighbourhood of each left vertex $$i$$ is a random subset $$V_i$$ of $$d$$ vertices on the right, and the $$V_i$$'s are chosen independently of each other. For small $$\delta$$ independent of $$n$$, and $$d=O(\log(1/\delta))$$ and $$m=O(n\delta\log (1/\delta))$$, a random $$d$$-left regular graph is an $$(n,m,d,\delta)$$-expander with high probability for sufficiently large $$n$$. We can prove this by computing $$Pr[\mathcal{N}(S)\subset T]$$ for $$S,T$$ with $$|T|=0.75 d|S|-1$$ and then taking a union bound over possible $$S,T$$ pairs.

If we force $$d$$ to be a constant independent of $$n$$, and $$m$$ to grow linearly with $$n$$ while having $$m, what are the best parameters we can hope for (in the sense of having small $$d$$ and $$m$$)? Is the above existence result order-optimal? If we are also interested in obtaining the best constants (and not just order optimality), what is known?

Also, is there a different proof/proof technique of existence of $$(n,O(n\delta\log(1/\delta)), O(\log(1/\delta)),\delta)$$ expanders? I tried to compute the expected size of the neighbourhood of $$S$$ and concentrate it using Chernoff-type bounds, but the parameters so obtained are worse.

• This seems like a question for Mathematics, to me. There doesn't really seem to be any computational aspect to what you're asking. – David Richerby Oct 30 '18 at 17:33
• Expanders come up a lot in theoretical computer science, so I think this question fits here or even on Theoretical Computer Science. – Yuval Filmus Oct 30 '18 at 18:12
• @DavidRicherby: I did ask a similar question on mathoverflow, but did not get an answer. I therefore felt that it would be a better fit in CS stackexchange. As Yuval pointed out, perhaps it would fit even better on TCS. – curiousperson Oct 31 '18 at 9:10
• @YuvalFilmus I agree, but programming comes up a lot in computer science but we don't accept questions about that. This is certainly a question that some computer scientists could answer, but that doesn't make it a question about computer science. – David Richerby Oct 31 '18 at 9:50
• Cross-posted by OP, cstheory.stackexchange.com/questions/41828/… – Apass.Jack Nov 2 '18 at 7:44