University of Birmingham > Talks@bham > Analysis Seminar > Spin Systems, Phase Transitions, Sampling and Approximation Algorithms

Spin Systems, Phase Transitions, Sampling and Approximation Algorithms

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact José Cañizo.

This talk is part of the Mathematics Colloquium

A simple example of a spin system is the so-called hard-core model. This is actually a model of a gas, but it has a simple combinatorial interpretation. There is an underlying graph G, and “configurations’’ are just independent sets in G. The weight of a configuration is an (exponential) function of its size depending on a parameter lambda, and the “partition function’’ is the sum of the weights of all configurations. The Gibbs distribution (also called the Boltzmann distribution) is the distribution in which each configuration is sampled with probability proportional to its weight. It is useful to be able to sample from the Gibbs distribution and to calculate the value of the partition function, either exactly or approximately. The notion of Gibbs distribution extends to infinite graphs and a “phase transition’’ occurs when the parameter lambda is at a critical value such that, for smaller lambda there is unique Gibbs measure, whereas for larger lambda there are multiple Gibbs measures. Progress in recent years has shown that the computational complexity of the approximation problem on finite graphs is intimately connected with phase transitions, and with the question of uniqueness on infinite trees. I will give a survey of some of the results that are known, focussing especially on the special case where the Gibbs distribution is uniform.

This talk is part of the Analysis Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.