|
2 |
edited tags
|
||
|
1 |
|
||
Generalization or Improvement of Cheeger inequality on GraphsLet $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:
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.
|
||||

