Math 582CA
Statistical Physics Expansion Methods in Combinatorics and Probability
Christian Borgs
Winter 2004, Monday & Wednesday 10:30-12:00
Statistical Physics Expansion Methods in Combinatorics and Probability
This course is an expanded version of a series of 10 lectures given as
a CBMS series (see http://www.cbmsweb.org/NSF/index.htm)
in Memphis this summer. In the course, I will review a set of techniques
that were originally developed by mathematical physicists to study models
of statistical physics and phase transitions in these models, and show how
they can be applied to problems of interest in combinatorics, probability
theory and theoretical computer science, including the following.
- General coloring problems (graph homomorphism)
- Zeros of graph polynomials
- Phase Transitions and Phase Coexistence
- Mixing of Monte Carlo Markov Chains
Prerequisites:
Since I expect a mixed audience of combinatorialists, probabilists and
theoretical computer scientists, I will not assume much background:
concepts like Gibbs measures, graph homomorphism, independent sets, etc.
will be introduced as they are needed, and are not a prerequisite for the
course, which only assumes basic knowledge of probability theory and
essentially no knowledge of graph theory, except for very simple concepts,
like the concept of a tree.