Large Finite Random Structures

该项目研究，使用概率方法，有限随机结构的行为，因为他们的规模越来越大，集中在五个具体的主题。两个来自理论组合学：非均匀随机映射；以及最大的常见子结构，比如偏序或叶子标记的树。一个来自统计物理：无序系统的平均场模型，特别是第一通道渗透及其相关的渗透函数。另一个来自生物学：纯随机宏观进化模型，可以同时处理现存物种的系统发育树和灭绝物种的时间序列。最后一个主题是随机关联图，它试图抽象现实世界图结构的一个方面，例如人类社交网络（“小世界”）或WWW链接。从概念上讲，该项目旨在作为随机结构的抽象数学理论之间的桥梁，其重点是不切实际的简单模型的困难属性，以及复杂网络的工程类型示例（互联网的物理和超文本链接；交通网络），其模型利用特定结构的细节。希望对这五个特殊模型的研究将导致在这些更多应用领域有用的新的数学方法。

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.