权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Probability on Combinatorial Structures

组合结构的概率

基本信息

批准号：
EP/D065755/1
负责人：
Christina Goldschmidt
金额：
$ 28.78万
依托单位：
University of Oxford
依托单位国家：
英国
项目类别：
Fellowship
财政年份：
2007
资助国家：
英国
起止时间：
2007 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FD065755%2F1
关键词：
Probability Combinatorial Structures

项目摘要

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.

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