Notes, MATH 262, Winter, 2015

• Week 1 :
  • Perspectives, history, combinatorial coefficients, useful combinatorial identities,
  • Polya's theorems on random walks
  • Generating functions, analytic combinatorics in two variables
  • Sources: Reading list, books 4, 5, 6; Reference 10.
• Week 2 :
  • Elementary proof of the prime number theorem
    Small primes in combinatorial coefficients
    Sources: Reading list, reference 10.
  • Several views of the combinatorial Laplacian and matrix tree theorem,
    characteristic polynomial, matrix forest theorem.
    Sources: Chapter 1 of Spectral Graph Theory.
• Week 3:
  • The normalized Laplacian,
  • Random walks on graphs and the transition probability matrix
  • Bounds for eigenvalues of the normalized Lapalcian
  • Methods of computing eigenvalues
  • The covers of graphs.
  • Sources: Chapter 1, Chapter 6 of Spectral Graph Theory.
• Week 4:
  Chapter 2 of Spectral Graph Theory covered by Sam Peng
• Week 5:
  • Several charaterizations of the Cheeger constants
  • Several proofs for the Cheeger inequality including a short proof.
• Week 6 - 7:
  • Definitions of higher Cheeger constants ---- h_k , h^*_k, rho_k, all of which generalize h_1.
  • Higher Cheeger inequalities, relating all modified higher Cheeger constants.
• Week 8:
  • Szemeredi's regularity lemma
  • Applications of the regularity lemma
• Week 9:
  • A spectral proof of the regularity lemma (by Terry Tao)
  • Kawa talked about applications of higher Cheeger constants relating to unique games conjecture.
  • Quasi-random graphs