Is the upper Cheeger Inequality tight?

383 Views Asked by At

The (upper) Cheeger Inequality says:

Let $G$ be an unweighted, undirected, regular graph of degree $d$. Let $\lambda_2$ be the second eigenvalue of the Laplacian matrix of $G$, and let $\phi(G)$ denote the value of its edge expansion (that is, $\min_{S \subset V, |S| \le \frac{1}{2}|V|} \, \frac{E(S, V-S)}{d|S|}$). Then $\phi(G) \le \sqrt{2\lambda_2}$.

I am reading lecture notes that prove that this inequality is tight up to a constant (by considering the special case of Cayley Graphs). This leads me to wonder: is there...

(1) A more complicated family of graphs that prove the Cheeger Inequality exactly tight?

(2) A more complicated inequality of the form $f(\phi(G)) \le g(\lambda_2)$ that is known to be exactly tight?

(3) Is this still an open question? If so, is it an open question that anyone really cares about?