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.


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.