Instructor

Will Perkins

* willp@uic.edu*

Office: SEO 626

Office Hours: Mondays and Wednesdays 11:00am-12:00pm, or by appointment

Course Information
#### Main Topics of the Course:

- Fundamentals of statistical physics: Gibbs measures, partition functions, correlations, phase transitions
- Algorithms for approximatate counting and sampling
- Phase coexistence and absence of phase transition
- Cluster expansion
- Polymer models
- Entropy methods
- Pirogov-Sinai theory
- Applications to extremal and enumerative combinatorics
- Algorthms at low temperatures
- Spin models on random graphs
- Sphere packings and the hard sphere model

References

- Friedli and Velenik, Statistical Mechanics of Lattice Systems
- Alon and Spencer, The Probabilistic Method
- Mezard and Montanari, Information, Physics, and Computation
- Levin and Peres, Markov Chains and Mixing Times

Schedule

- Jan 11What is statistical physics?
- Jan 13Gibbs measures and partition functions
- Jan 15Cumulants and derivatives of log Z
- Jan 18NO CLASS - MLK Day
- Jan 20Marginals and correlations
- Jan 22Dynamics
- Jan 25Spatial and temporal mixing
- Jan 27Extremal combintorics for regular graphs
- Jan 29worksheet
- Feb 1Entropy method
- Fev 3Occupancy method
- Feb 5Linar programming and complemnetary slackness
- Feb 8Matchings in regular graphs
- Feb 10Independent sets in triangle-free graphs
- Feb 12Infinite volume limits and phase transitions
- Feb 15Dobrushin uniqueness
- Feb 17Path coupling
- Feb 19worksheet: independent sets of a given size
- Feb 22Disagreement percolation
- Feb 24Lee-Yang theory
- Feb 26Heilmann-Lieb theorem
- Mar 1Approximate counting and sampling
- Mar 3Weitz's correlation decay method
- Mar 5worksheet
- Mar 8Computational thresholds (Sly's result)
- Mar 10Cluster expansion
- Mar 12Cluster expansion convergence
- Mar 15Probabilistic consequences of convergence
- Mar 17Series expansion algoritms
- Mar 19worksheet
- Mar 22no class - spring break
- Mar 24no class - spring break
- Mar 26no class - spring break
- Mar 29Abstract polymer models
- Mar 31Algorithms via polymer models and cluster expansion
- Apr 2BIS-hard problems on expander graphs
- Apr 5Independent sets in the hypercube
- Apr 7Independent sets in the hypercube
- Apr 9Sapozhenko's Lemma (guest lecture by Aditya Potukuchi)
- Apr 12Peierls' argument
- Apr 14Slow mixing and phase coexistence on Zd
- Apr 16worksheet
- Apr 19Pirogov-Sinai theory
- Apr 21Pirogov-Sinai theory
- Apr 23worksheet
- Apr 26Random graphs
- Apr 28Random graphs
- Apr 30Review