Evolving Combinatorial Structures

The project studies probability models for evolving combinatorial structures, particularly partition, tree and graph-valued stochastic processes. Specific topics to be studied include representation and characterization theorems of combinatorial Markov processes, continuum tree and interval graph scaling limits, consistent systems of partition, tree and graph-valued processes, and connections to random matrices and Levy processes. The dominant theme of the research will be the effect of probabilistic symmetries, especially exchangeability, on the structural properties of evolving large combinatorial objects, as these structural properties impact various practical aspects of these processes.

As a result of this project, we should gain further understanding of models for time-varying discrete structures, especially partitions, trees and networks. Such processes arise as natural models in various disciplines, including genetics, physics, biology, computer science and statistics. In particular, understanding graph-valued processes has potentially far-reaching applications in the diverse and burgeoning field of complex networks. Effective models for real-world networks are relevant to problems in national security, public health, sociology, computer science and physical sciences. Other areas in which combinatorial models can be useful include phylogenetics, machine learning, statistics and Bayesian inference.