Let $G = (V,E)$ be an undirected graph with maximum degree $\Delta$. The isoperimetric number of $G$, denoted $i(G)$, is defined by $$i(G) = \min_{|S| \leq |V|/2} \frac{e(S,\bar{S})}{|S|},$$ where $e(S,\bar{S})$ is the number of edges between $S$ and its complement $\bar{S}$. The Cheeger inequality asserts that: $$\frac{\lambda_2}{2} \leq i(G) \leq \sqrt{\lambda_2(2\Delta-\lambda_2)},$$ where $\lambda_2$ is the second smallest eigenvalue of the Laplacian matrix $L=D-A$ (which also known as the algebraic connectivity of $G$). In general, $i(G)$ can be far from $\frac{\lambda_2(G)}{2}$. For instance, if $C_n$ is the cycle of order $n$, then $i(C_n) = \Omega(\frac{1}{n})$ and $\lambda_2(C_n) = O(\frac{1}{n^2})$. Is this possible if $i(G)$ be sufficiently large? Specifically, is it true that

if $i(G) \geq 1$, then $\lambda_2(G) \ge 1$?

Is there any known result similar to this statement?


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.