Mathematical Sciences: Topics in Discrete Probability and Algorithms

点击翻译按钮获取中文摘要

Aldous A general methodology for the study of size-asymptotics of random finite structures is to seek to establish, via the techniques of weak convergence theory, existence of a limiting continuous-space structure. In this spirit, one part of the proposal is to develop a new approach to the emergence of the giant component in random graph theory, by representing limit component sizes as excursion lengths in a Brownian-type process. This representation opens up a relation between two well-studied but hitherto apparently unrelated areas of probability theory. Other parts of the proposal include foundational work relating to mixing times for Markov chains, and analysis of specific randomized algorithms. As background, the study of matter aggregating into clusters is of interest in many areas of science: polymers in physical chemistry, condensation of raindrops in clouds, and formation of galaxies in the early universe, to name just three examples. Models of clustering incorporating the effects of randomness received some attention from physicists in the early and mid 1980s, but faded out when the mathematical tools then available had been used to their limits. The main part of this proposal concerns detailed study of one particular model of this kind via sophisticated modern mathematical tools. It is hoped that new tools to be developed under this proposal will be useful in at least some of these scientific areas.