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.