Examples of sequences of graphs with different order of Cheeger constant and spectral gap

137 Views Asked by At

According to Cheeger's inequality, the bottleneck ratio/Cheeger ratio $\Phi_*$ of a graph and the spectral gap $\lambda$ of its adjacency matrix satisfies $$\Phi_*^2/2 \leq \lambda \leq 2\Phi_*. $$ Standard examples which shows that this inequality is sharp are the hypercube $\mathbb{Z}_2^n$ for the upper bound and a circle, $\mathbb{Z}_n$, for the lower bound, i.e. if $\lambda^{(n)} $ is the spectral gap of $\mathbb{Z}_2^n$ and $\Phi_*^{(n)}$ is the bttleneck ratio of $\mathbb{Z}_2^n$, then $\lambda^{(n)} \asymp \Phi_*^{(n)}$, and if we do the analogue definitions for $\mathbb{Z}_n$, then $\lambda^{(n)} \asymp (\Phi_*^{(n)})^2$.

I would guess that if one considered other sequences of graph, then the asymptotic behaviour of $ \lambda^{(n)} $ vs. $\Phi_*^{(n)}$ should fall somewhere in between these to extreme examples, however, I do not know of any such example, which is in essence different from the two examples above, i.e. say picking $\mathbb{Z}_3^n$, or $just adding a vertex and a edge to each graph in such a sequence is cheating :)

So, are any such examples of sequences, in which the graphs are, say, regular, known?