Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Just because an inequality is tight doesn't mean it can't be improved. It just means that if there is an improvement then it must share the same equality cases. –  Qiaochu Yuan Apr 3 '11 at 0:21

3 Answers 3

There is a lot known on the relations between the Cheeger constant $h_{G}$ and $\lambda_{2}$ and more general on the whole spectrum of the normalized Laplacian for the following families of graphs:

  • Random Trees (branching processes) Lyons and Peres book is an excellent reference.

  • Random Geometric graphs, Penrose's book is an good reference.

  • As previously mentioned the $G_{n,p}$ random model of Erdos and Renyi.

  • Random regular graphs where you can find information in the fundamentals papers of McKay.

  • Regular planar tessellations of hyperbolic space.

I hope it helps!

share|improve this answer
    
Thanks for your help. However, I do not think the results you mentioned above give the answers I wanted. The above results almost all fall into the following case: For a given class of graphs, estimate the conductance (or expansion) using the (random) structure of the class; then 1) use the Cheeger inequality to give bound on the second eigenvalue or 2) relates the conductance with other quantities, e.g., diameters. Such results do not give any \direct improvement on the relationship between $\lambda_2$ and $h_G$, which implies better upper or lower bound compared with Cheeger inequality. –  Pan Peng Apr 3 '11 at 8:17

There other classes of graphs such as generalizations of the $G(n,p)$ model with a given degree distribution. See for example Chung and Vu's paper on the spectrum of these graphs. In particular, they analyzed the case when the graph has a power law degree distribution.

share|improve this answer

One place to look might be random graphs $G(n,p)$. This might either give you a wide class of graphs for which an improvement holds, or else show you a limit to what you might hope for.

For Cheeger constant see: MR2371054 (2008j:05316) Benjamini, Itai; Haber, Simi; Krivelevich, Michael; Lubetzky, Eyal The isoperimetric constant of the random graph process. Random Structures Algorithms 32 (2008), no. 1, 101–114.

For spectral gap see: MR0637828 (83e:15010) Füredi, Z.; Komlós, J. The eigenvalues of random symmetric matrices. Combinatorica 1 (1981), no. 3, 233–241.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.