8
$\begingroup$

It is known how to construct "lossless" unbalanced bipartite expanders with the following properties: the bipartite graph has $n$ left vertices, $m$ right vertices, left-degree $D$, and for all left-sets $S$ of size up to $\gamma n$, the neighbor set $\Gamma(S)$ has size at least $(1 - \epsilon)D|S|$, and this is achieved for any $m \leq n, \epsilon > 0$, and $D = \Theta(\log(n/m)/\epsilon)$, $\gamma = \Theta(\frac{\epsilon m}{Dn})$. The construction due to Capalbo, et al. achieves these parameters.

It's clear that $\gamma \leq m/(Dn)$, but how large can $\gamma$ be? In particular, I'm wondering if it's possible to make $\gamma$ very close to $1/4$, say; this would essentially require one to make $m = n$ and $D = 4$ for any hope of accomplishing this -- $\epsilon$ hasn't even been considered yet! However, does anyone familiar with expander constructions have a sense of what hidden constants lay within the $\Theta$'s?

$\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.