1
$\begingroup$

I am interested in finding the best expansion parameters for unbalanced left-regular expander graphs.

Specifically, fix $\delta\in(0,1/2)$, and a positive integer $d$. Let us call a bipartite graph $\mathcal{G}$ to be an $(n,m,d,\delta,\epsilon)$-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)|\geq (1-\epsilon)d|S|$. Here $\mathcal{N}(S)$ denotes the set of neighbours of $S$.

Is there a tight analysis on how large $m/n$ should grow (in the limit as $n\to\infty$) as a function of $d,\epsilon,\delta$ ? In my (limited) understanding of the literature, most papers study the case $\delta=1/2$. The problem then reduces to studying the spectral gap, and there is a whole line of work on this topic. I am interested in the case when $\delta<1/2$. If it helps, we can assume that $\delta$ is very small, i.e., $\delta<<1/2$.

An argument along the lines of Hoory, Linial and Wigderson (see section 1.2) shows that $(n,\mathcal{O}(\frac{\delta n}{\epsilon}\log \frac{1}{\delta}),\mathcal{O}(\frac{1}{\epsilon}\log\frac{1}{\delta}),\delta,\epsilon)$ expanders exist for sufficiently large $n$.

Is there a matching lower bound for the above statement? In the sense that if we demand that $\mathcal{O}(\frac{1}{\epsilon}\log\frac{1}{\delta})$, then does $m$ have to be $\Omega((\frac{\delta n}{\epsilon}\log \frac{1}{\delta}))$?

The proof of the argument mentioned above involves union bounds over subsets of left and right vertices, which could lead to a loose bound. Can the constants in $(n,\mathcal{O}(\frac{\delta n}{\epsilon}\log \frac{1}{\delta}),\mathcal{O}(\frac{1}{\epsilon}\log\frac{1}{\delta}),\delta,\epsilon)$ be improved using a different argument? What are the best constants we can hope for?

Are there any known lower bounds on the parameters for $\delta<1/2$? If it makes things easier, let us assume that $\epsilon= 1/4$.

$\endgroup$
  • $\begingroup$ I am sure one can use the probabilistic method to show that $m$ can asymptotically be as small as you wrote [relative to $n$ given $\delta$ and $\epsilon$]. I am not positive if these bounds have been established as tight. There are however explicit "loss-less" expanders by the way that come close to achieving these bounds depending on e.g., the relative values of $n/m$, $\delta$, $\epsilon$. That said the spectral gap will give you only up to $N(S) \geq d(\frac{1}{2} - \epsilon')|S|$-- see N. Kahale $\endgroup$ – Mike Oct 23 '18 at 20:41

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.