2 edited tags
1

# Generalization or Improvement of Cheeger inequality on Graphs

Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. Let $A$ denote the adjacency matrix of $G$ and $D$ denote the diagonal matrix such that $D_{i,i}$ equals to the degree $d_i$ of vertex $i$. Then the Laplacian of $G$ is defined to be $L:=I-D^{-1/2}AD^{-1/2}$, which has $n$ nonnegative real eigenvalues, say, $0=\lambda_1\leq \lambda_2\leq \cdots\leq \lambda_n$.

Now for any vertex subset $S\subseteq V$, let $e(S,\bar{S})$ denote the number of edges between $S$ and its complement $\bar{S}$. Let $vol(S):=\sum_{v\in S}deg_v$ be the sum of degrees of vertices in $S$. Then the conductance (or Cheeger constant) $h_G$ of graph $G$ is defined to be $h_G:=\min_{S\subseteq V}\frac{e(S,\bar{S})}{\min {vol(S), vol({\bar{S}})}}$.

The Cheeger inequality relates the second smallest eigenvalue $\lambda_2$ of $L$ to the conductance $h_G$ as follows:

$2h_G\geq\lambda_2\geq \frac{h_G^2}{2}$.

The above inequality is known to be tight. For example, the left side of the inequlity is tight on the $d$-dimensional cube and the right side is tight on the $n$-vertex cycle. Thus, we do not hope to improve the inequality that applies to every graph.

My question is:

Is there any result which gives that for some special class of graphs, the Cheeger inequality has an improved form, say, $2h_G^{1.2}\geq\lambda_2\geq \frac{h_G^{1.5}}{2}$ for any $G\in\mathcal{C}$, where $\mathcal{C}$ is a set of graphs.

Ideally, we would hope that there is a nice tradeoff between the generality of the class $\mathcal{C}$ and the tightness of the Cheeger-type inequality. In another word, $\mathcal{C}$ contains a wide class of graphs and the upper bound is close to the lower bound.