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

许多现象都可以用集群的生长来描述，集群根据其边界上的随机相互作用而进化：晶体的生长，生物种群在一个地区的传播，熟人群体中的谣言传播或互联网上的病毒传播。考虑以下增长模型的简单示例。一组场地按照方形网格组织，最初占用一个场地。一旦一个站点的任何邻居被占用，在该站点被占用之前会经过一段随机的时间。被占用的站点集群随着时间的推移而增长。有许多不同的有趣的问题，例如：当集群变大时，它是否具有相当可预测的形状？星团的边界有多平滑？两个不同的站点加入集群的时间之间的相关性是什么？这如何依赖于它们之间的距离？对于这类问题，已知的极其精确的答案是某些非常具体的增长模型。然而，人们普遍认为，行为的许多方面不应强烈依赖于增长规则的确切性质。该项目的一个主要目的是通过使用概率论的工具，找到普适性的严格数学证明来证明这一信念。它们与所谓的相互作用粒子系统有着密切的关系。例如，考虑一个系统，其中粒子位于一条线上的位置，该位置由集合{…，-3,-2,-1,0,1,2,3，…}中的数字给出。粒子试图随机地向右跳跃；如果右边的位置没有被另一个粒子占据，则跳跃成功。这个非常简单的系统被证明具有丰富的行为，并被广泛应用于统计物理中作为不可逆流动的基本模型。这种类型的某些相互作用的粒子系统实际上相当于生长模型（例如，可以想象，当粒子n跃迁到粒子系统中的k位置时，生长模型中坐标为（n,k）的点加入了被占据的簇）。同样的普遍性问题也出现了：我们感兴趣的量（比如平均流速，或者不同粒子位置之间的相关性）在多大程度上依赖于跳跃的随机性和粒子间局部相互作用规则的精确性质？项目的第二部分涉及组合优化或约束满足问题。计算机科学中的各种各样的问题都可以用简单的公式抽象地表示出来，这些公式包括取True或False值的变量，并通过AND和or运算符连接在一起。如果将值True或False赋值给变量，使得整个公式的值为True，则称公式是可满足的。一个极其重要的问题与计算复杂性有关：算法需要多长时间才能找到这样一个令人满意的分配，或者证明不存在这样一个分配？对于某些类型的问题，人们认为，给定公式的令人满意的赋值集倾向于具有聚类性质，而不是或多或少均匀地分布在所有赋值的空间中，这种现象产生了具有高复杂性的问题。在这个项目中，我将把这种聚类特性与相互作用的粒子系统的行为联系起来，这些粒子系统的粒子在树状结构中占据位置，特别是与这种系统的可能平衡状态集联系起来。这可以看作是数学、物理和计算机科学之间的一个更广泛的项目的一部分，旨在为源自统计物理学的一类非常强大但不严格的工具提供一个健全的数学基础。

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.