# Tight upper and lower bounds for unbalanced left-regular expander graphs

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

• 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 – Mike Oct 23 '18 at 20:41