Math 583G
Advanced methods in discrete mathematics
László Lovász and Balazs Szegedy
Spring 2005, Tuesday-Thursday 2:30-3:50
First class meeting will be Thursday, March 31.
Eigenvalues of graphs and their graph-theoretic significance. Random walks
on graphs and basic parameters: hitting times, cover time, mixing
times. Connection with the eigenvalue gap. Geometric representations:
circle representation, orthogonal representation, Colin de Verdiere number,
spectral constructions of geometric representations.
Prerequisites. The course uses only elementary linear algebra and probability, and some basic knowledge in graph theory.