Probability on Combinatorial Structures

这个项目有两条线索。第一个涉及合并(或凝聚)和破碎的过程。本质上，我们有一个粒子系统，随着时间的推移，这些粒子随机地粘在一起或碎成碎片。这些过程发生在许多不同的科学背景中：聚合、气溶胶、天文结构的形成和种群遗传学，仅举几例。直观地说，凝聚和碎裂是双重现象，从某种意义上说，在碎裂中逆转时间会产生类似于聚合体的东西。然而，为了给出合理的过程，我们应该施加各种自然的数学约束，一旦我们这样做了，对偶性就不再那么明显了。有几个漂亮的例子是已知的，但没有普遍的理论。我的目的之一是更好地理解这一重要现象。文献中研究较多的一类特定的碎片化过程是自相似碎片化。它们的性质是，所有的块都以相同的方式和速度分裂，这仅仅取决于它们的质量。在某些情况下(所谓的自相似指数为负值)，较小的块比较大的块碎片更快。小块的碎裂速度越来越快，因此在有限的时间内整个初始质量消失了。我将在一切都变成“尘埃”的时候调查这些过程的行为。我特别感兴趣的是现有质量的衰减率和它消失时随机时间的分布。人口遗传学是聚合的一个非常重要的应用领域，长期以来一直是数学理论发展的推动力。一种特殊的融合过程，称为金曼融合，是描述大种群系谱的核心。然而，很难将选择和重组这两个重要现象纳入现有框架。看来，同时包括合并和破碎的模型在这里会更合适。这样的模型存在于数学文献中，但目前并不具备这些应用程序所需的所有几何结构；这是我打算解决的问题。一个特别的目标是找到方法来区分在真实种群中检测到的遗传多样性减少的可能来源。这个项目的第二个方面涉及随机可满足性问题。计算机科学中各种各样的问题可以归结为表面上简单的公式，这些公式涉及的变量可以取值为True或False，并由AND和OR连接。如果存在一种将变量设置为True或False以使整个表达式为True的方法，则称这样的公式是可满足的。这个问题的一个重要版本是K-SAT，其中公式由K个变量的子句组成，这些子句通过OR连接在一起；然后使用AND将这些子句组合在一起。如果变量是从大小为N的集合中随机选择的，那么我们就得到了随机K-SAT问题。这个问题展示了令人着迷的相变现象，即一个系统的基本参数的微小变化会导致定性行为的巨大变化。这里，如果N很大，而子句数相对于N很小，则随机公式可满足的概率接近1。增加每个变量的子句数，存在一个阈值，超过该阈值，随机公式可满足的概率接近于0。随机K-SAT问题也引起了统计物理学家的兴趣，他们使用自己的方法取得了重要进展。然而，他们的许多结果虽然被广泛认为，但在数学证明的层面上还没有得到严格的证明。这是我打算参加的一个重要项目。

This project has two strands. The first concerns processes of coalescence (or coagulation) and fragmentation. In essence, we have a system of particles which, over the course of time, randomly stick together or break into pieces. These processes occur in many different scientific contexts: polymerization, aerosols, the formation of astronomical structures and population genetics, to name just a few. Intuitively, coagulation and fragmentation are dual phenomena, in the sense that reversing time in a fragmentation gives something which resembles a coalescent. However, there are various natural mathematical constraints which we should impose to give reasonable processes, and once we have done this, the duality property is no longer so clear. Several beautiful examples where it does hold are known, but there is no general theory. One of my aims is to understand this important phenomenon better.A specific class of fragmentation processes which are much studied in the literature is the self-similar fragmentations. These have the property that the blocks all split in the same way and at rates which depend simply on their masses. In certain cases (where the so-called index of self-similarity is negative), smaller blocks fragment faster than larger ones. The small blocks fragment faster and faster, so that in finite time the whole initial mass disappears. I will investigate the behaviour of these processes near the point when everything turns to ``dust''. In particular, I am interested in the rate of decay of the existing mass and the distribution of the random time when it disappears.Population genetics is a very important area of application for coalescence and has long been a driving force behind the development of the mathematical theory. A particular coalescent process, called Kingman's coalescent, is central to the description of the genealogy of large populations. However, it is difficult to incorporate two important phenomena, selection and recombination, into the existing framework. It appears that models which include both coalescence and fragmentation will be more appropriate here. Such models exist in the mathematical literature but do not currently possess all of the geometrical structure needed for these applications; this is a problem on which I intend to work. A particular aim is to find ways to distinguish possible sources of reduced genetic diversity detected in real populations.The second strand of this project concerns random satisfiability problems. A huge variety of problems in computer science can be reduced to ostensibly simple formulae involving variables which can take the values True or False, joined by AND and OR. Such a formula is said to be satisfiable if there exists a way of setting the variables to True or False so that the whole expression holds true. An important version of this problem is K-SAT, where the formula consists of clauses of K variables which are joined together by OR; these clauses are then put together using AND. If the variables are chosen randomly from a set of size N then we obtain the random K-SAT problem. This problem demonstrates the fascinating phenomenon of phase transition, whereby a small change in an underlying parameter of a system leads to a large change in the qualitative behaviour. Here, if N is very large and the number of clauses is small relative to N, then the probability that a random formula will be satisfiable is close to 1. Increasing the number of clauses per variable, there is a threshold value above which the probability that a random formula is satisfiable is close to 0. The random K-SAT problem is also of interest to statistical physicists, who have made important progress using their methods. However, many of their results, while widely believed, have not yet been made rigorous at the level of mathematical proof. This is an important programme in which I intend to take part.