ASGT

Remarks on Lecture 2

Advertisements

In this lecture, we generalized our setting to weighted graphs where is a positive weight function on edges. We also looked at the basic spectral theory of the normalized Laplacian, defined by

,

which operates on functions via

.

In particular, we associated with the normalized Rayleigh quotient,

,

and we showed that we can express the second-smallest eigenvalue as

.

We defined the expansion of a subset by

,

where is the characteristic function for .

Finally, we defined the expansion of a graph by

We then stated and (almost) proved the following discrete Cheeger inequality.

Theorem 1. For any weighted graph , we have

,

where .

Exercises (optional)

  1. Prove that for the normalized Laplacian, just as for the combinatorial Laplacian, the number of connected components in a graph G is precisely the multiplicity of the smallest eigenvalue.
  2. We saw the the right-hand inequality in Theorem 1 is asymptotically tight. Prove that the left-hand side is asymptotically tight for the complete graph on n nodes.
Advertisements