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

Probability on Combinatorial Structures

组合结构的概率

基本信息

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

来源：
https://gtr.ukri.org/projects?ref=EP%2FD065755%2F2
关键词：
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.

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