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<n$, 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.

  • $\begingroup$ This seems like a question for Mathematics, to me. There doesn't really seem to be any computational aspect to what you're asking. $\endgroup$ – David Richerby Oct 30 '18 at 17:33
  • 1
    $\begingroup$ Expanders come up a lot in theoretical computer science, so I think this question fits here or even on Theoretical Computer Science. $\endgroup$ – Yuval Filmus Oct 30 '18 at 18:12
  • $\begingroup$ @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. $\endgroup$ – curiousperson Oct 31 '18 at 9:10
  • $\begingroup$ @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. $\endgroup$ – David Richerby Oct 31 '18 at 9:50
  • $\begingroup$ Cross-posted by OP, cstheory.stackexchange.com/questions/41828/… $\endgroup$ – John L. Nov 2 '18 at 7:44

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.