Copy of Probability and statistical physics: interacting particle systems, growth models and percolation

Many phenomena can be described in terms of the growth of a cluster which evolves according to random interactions at its boundary: the growth of a crystal, the spread of a biological population across an area, the spread of a rumour in a group of acquaintances or of a virus on the internet.Consider the following simple example of a growth model. A set of sites is organised according to a square grid, and initially a single site is occupied. Once any neighbour of a site is occupied, a random amount of time passes before that site becomes occupied itself.The cluster of occupied sites grows over time. There are many different questions of interest, for example: as the cluster becomes large, does it have a fairly predictable shape? How smooth is the boundary of the cluster? What is the correlation between the times at which two different sites join the cluster, and how does this depend on the distance between them?Extremely precise answers to questions of this kind are known for certain very specific growth models. However, it is widely believed that many aspects of the behaviour should not depend strongly on the exact nature of the growth rules. A major aim of this project is to justify this belief by finding rigorous mathematical proofs of universality properties, using the tools of probability theory.There are close relations to so-called interacting particle systems . For example, consider a system in which particles are located at positions on a line, given by numbers in the set {...,-3,-2,-1,0,1,2,3,...}. Particles try to jump to their right at random times; the jump succeeds if the position to the right is not already occupied by another particle. This very simple system turns out to possess rich behaviour, and is widely used in statistical physics as a basic model of non-reversible flow. Certain interacting particle systems of this type are in fact equivalent to growth models (for example, one can imagine that the point in the growth model with co-ordinates (n,k) joins the occupied cluster at the time when particle n jumps to position k in the particle system). The same universality questions arise: to what extent do quantities of interest (such as average rates of flow, or correlations between the positions of different particles) depend on the precise nature of the randomness of the jumps and the rules of the local interaction between particles?A second strand of the project concerns combinatorial optimisation or constraint satisfaction problems. A huge variety of problems in computer science can be represented in an abstract way by simple formulae involving variables which take the values True or False, joined together by the operators AND and OR. A formula is said to be satisfiable if there is an assignment of the values True or False to the variables so that the overall formula has the value True. An extremely important question concerns computational complexity: how long does it take for an algorithm to find such a satisfying assignment, or to prove that none exists? For certain classes of problem, it is believed that the set of satisfying assignments for a given formula tends to have clustering properties, rather than being more or less evenly spread out across the space of all assignments, and that this phenomenon creates problems with high complexity.In this project I will relate such clustering properties to the behaviour of interacting particle systems whose particles take positions in a tree-like structure, and in particular to the set of possible equilibrium states for such a system. This can be seen as part of a much broader programme at the interface between mathematics, physics and computer science, aiming to give a sound mathematical footing to a class of very powerful but non-rigorous tools which originate in statistical physics.