9
$\begingroup$

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.

$\endgroup$

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.