The majority of this research is in the area of probabilistic combinatorics, which is comprised of the study of random combinatorial structures, randomized algorithms and probabilistic existence proofs for combinatorics (i.e. the probabilistic method). In recent years, this field has seen the development of a technique for proving that key statistics of a discrete stochastic process are likely to remain close to their expected trajectories as the process evolves. This method is known as the differential equations method for greedy algorithms and random graph processes. The investigator recently extended this technique to analyze the triangle-free process, a `controlled' random graph process that produces an interesting distribution on the space of triangle-free graphs. The investigator showed that a graph drawn from this distribution is likely to have independence number within a constant multiplicative factor of the smallest possible. In other words, the triangle-free process produces a Ramsey R(3,t) graph. The investigator shall continue the development of this method for the study of related `controlled' random processes, with an emphasis on processes that are interesting from the perspective of extremal combinatorics. Related questions are motivated by computer science. Here the investigator attempts to develop applications of the differential equations method to prove good performance of randomized algorithms without an explicit solution, or numerical approximation of the solution, of the associated differential equation (the need for such information often significantly complicates application of this method).
This research project is an investigation of discrete mathematical objects, like networks or codes, whose evolution over time is determined by a sequence of random choices. We are particularly interested in processes where there is dependence between the choices made in different rounds. While such processes can be good models for the dynamics of real-world phenomenon, like the spread of a disease in a network or phase transitions in materials, the focus of this research is on processes that generate interesting mathematical objects. Randomness has long played an important role in the construction of sophisticated combinatorial objects, just as randomness plays an a central role in many algorithms in computer science. This research is expected to have an impact in multiple domains as the investigator shall develop general tools for understanding the evolution of these systems over time.
This research project was in the area of probabilistic combinatorics, which is the study of probability spaces populated with discrete mathematical structures. These structures are usually finite, and our main interest is in asymptotic behaviors as the size of the underlying system goes to infinity. There are three main themes in probabilistic combinatorics: Probabilistic proofs of the existence of interesting combinatorial objects (the so-called probabilistic method), the study of the performance of randomized algorithms, and the study of random discrete structures as objects of interest in their own right. These three research directions are held tightly together by a common collection of sophisticated tools that developed rapidly over the course of the last few decades. The field has close connections with computer science and remains quite vibrant. There have been several major advances in the last few years. The main focus of this project was dynamic concentration phenomena in random graph processes. We aim to analysis stochastic graph processes by proving that the evolution of key random variables over the course of the process are likely to closely follow their expected trajectories. The development of methods for proving dynamic concentration has been a central theme in probabilistic combinatorics in recent years. The standard methods for establishing dynamic concentration produce estimates that loosen (i.e. become weaker) as the underlying process evolves. During this project the PI focused on some intriguing situations in which we have dynamic concentration with estimates that become sharper as the process evolves. Such estimates are now known as self-correcting estimates. This work builds on previous work of the PI and his graduate student Michael Picollelli (as well as independent work of Telcs, Wormald and Zhou). As part of this project, the PI and his co-authors used self-correcting estimates to settle two long-standing open problems in probabilistic combinatorics. Very precise analyses of the random greedy triangle packing process and the triangle free process were produced. The triangle packing work was joint work with Alan Frieze and Eyal Lubetzky. The triangle-free process work was joint work with Peter Keevash. The analysis of the triangle-free process gives an improvement on the best known lower bound on the Ramsey number R(3,t) (The latter result was independently achieved by Fiz Pontiferos, Griffiths and Morris). This work has a broader impact through the PI's development of the mathematics curriculum at Carnegie Mellon University.
