Large Finite Random Structures

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

The project studies, using probabilistic methods, the behavior of finite random structures as their size grows larger and larger, focusing on five specific topics. Two are from theoretical combinatorics: non-uniform random mappings; and largest common substructures in settings such as partial orders or leaf-labeled trees. One is from statistical physics: mean-field models of disordered systems, in particular of first-passage percolation and its associated percolation function. Another is from biology: models of purely random macroevolution which can handle simultaneously phylogenetic trees on extant species and time series of extinct species. The final topic is random affinity graphs, which seek to abstract one aspect of the structure of real world graphs such as those for human social networks (``small worlds") or WWW links. Conceptually, the project is intended as a bridge between abstract mathematical theory of random structures, which focuses on difficult properties of unrealistically simple models, and the engineering type of examples of complex networks (the physical and hypertext links of the Internet; transportation networks) whose models exploit the details of the particular structure. It is hoped that study of these five particular models will lead to novel mathematical methodology useful in these more applied areas.