I asked this question on MO, but no answer. 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 example, 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})$. Can this be occurred if $i(G)$ be sufficiently large? Specifically, is this 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.