Probability on 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.