Combinatorics Reading Group

Birmingham, Fall 2015

  • Mondays, 3pm in Muirhead 113
  • Contact Will Perkins with any questions.
  • The theme of this term's reading group is tools from probability theory applied to combinatorial problems. In particular we will see random graphs, structures, and processes that come from computer science and statistical physics but can be used to solve problems in extremal combinatorics.
  • Goals of the reading group include learning tools that may be valuable in your research; learning about new areas and new problems; and practicing giving good mathematical talks.
  • Watch this Peter Winkler lecture for a nice overview of the links between combinatorics and statistical physics models with hard constraints.


October 12. Introduction and organization. Gibbs measures. Will Perkins.
October 26. Entropy, Shearer's Lemma, Bregman's Theorem. Three tutorial Lectures on entropy and counting, David Galvin. Wei En Tan.
November 2. Counting independent sets and graph homomorphisms. On weighted graph homomorphisms, David Galvin, Prasad Tetali. Frederik Garbe.
November 9. Lower bounds on the average size of independent sets. Independence numbers of locally sparse graphs and a Ramsey type problem, Noga Alon. Robert Hancock.
November 16. Markov chains and mixing times. Mixing, Dana Randall. Tassio Naia Dos Santos.
November 30. Matchings and Benjamini-Schramm convergence. Matchings in Benjamini-Schramm convergent graph sequences, Miklos Albert, Peter Csikvari, Peter Frenkel, Gabor Kun. Stefan Glock.
December 7. The Self-avoiding walk tree. Counting independent sets up to the tree threshold, Dror Weitz. Nicolás Sanhueza-Matamala.