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连接在一起。一个公式被认为是可满足的，如果有一个值真或假的变量分配，使整个公式的值为真。一个极其重要的问题涉及计算复杂性：算法需要多长时间才能找到这样一个令人满意的分配，或者证明不存在？对于某些类的问题，人们认为，一个给定的公式的满意分配的集合往往具有聚类属性，而不是或多或少均匀地分布在所有分配的空间中，这种现象产生了高复杂性的问题。在这个项目中，我将把这种聚类属性与相互作用的粒子系统的行为联系起来，这些粒子系统的粒子在树状结构中占据位置，并且特别涉及这种系统的可能平衡状态的集合。这可以被视为数学，物理和计算机科学之间接口的更广泛计划的一部分，旨在为一类起源于统计物理学的非常强大但不严格的工具提供坚实的数学基础。

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.