2
$\begingroup$

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?

$\endgroup$

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.