Lutz Warnke (Georgia Institute of Technology)

A dynamic view on the probabilistic method: random graph processes
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.