A dynamic view on the probabilistic method: random graph processes

School of Mathematics Colloquium
Thursday, May 7, 2020 - 11:00am for 1 hour (actually 50 minutes)
Lutz Warnke – Georgia Tech
Galyna Livshyts

 Random graphs are the basic mathematical models for large-scale disordered networks in many different fields (e.g., physics, biology, sociology).
Since many real world networks evolve over time, it is natural to study various random graph processes which arise by adding edges (or vertices) step-by-step in some random way.

The analysis of such random processes typically brings together tools and techniques from seemingly different areas (combinatorial enumeration, differential equations, discrete martingales, branching processes, etc), with connections to the analysis of randomized algorithms.
Furthermore, such processes provide a systematic way to construct graphs with "surprising" properties, leading to some of the best known bounds in extremal combinatorics (Ramsey and Turan Theory).

In this talk I shall survey several random graph processes of interest (in the context of the probabilistic method), and give a glimpse of their analysis.
If time permits, we shall also illustrate one of the main proof techniques (the "differential equation method") using a simple toy example.