Abstract: There has recently been an explosion of activity at the interface of discrete probability, statistical physics, theoretical computer science and combinatorics. The notion of a spin-model provides a useful framework for understanding some of the problems that lie at the intersection of these disciplines.
In a spin-model, the structure of some large random system is specified by local rules. Examples include the hard-core model, in which a lattice site may or may not be occupied by a particle, the occupation rule being that adjacent sites may not be simultaneously occupied, and the q-state Potts model, in which each site is occupied by a particle of one of q different flavours, with adjacent sites occupied by particles of different flavours.
A statistical physicist might ask what the global system ``typically'' looks like on an infinite lattice. An interesting question to a discrete probabilist is whether information about the appearance of the system in one locality significantly influences probabilities in other, distant, localities. A central question in theoretical computer science is how the spatial properties of the system are connected to the dynamic properties of simple sampling algorithms.
In this talk I will introduce the notion of a spin-model, give some canonical examples, and discuss the questions asked above for these examples.
This talk will be accessible to graduate students.