Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 295 - Mathematics Colloquium

Lutz Warnke

Georgia Tech

Random Graphs: Phase Transition and Beyond

Abstract:

Random graphs play a central role across several branches of mathematics and applied sciences. The phase transition of random graphs, where the component structure suddenly changes from `many small' components to `one giant' component, is an intriguing phenomenon with rich connections to percolation theory and mathematical physics. In computer science and extremal combinatorics, random graphs also provide strong probabilistic guarantees for hard-to-answer deterministic questions, such as the construction of interesting combinatorial objects. In this talk we illustrate these two complementary aspects of random graphs, highlighting that their analysis often brings together tools and techniques from different areas (including combinatorics, probability and differential equations). \\ \\ We will first focus on Achlioptas processes, which are variants of classical Erdos-Renyi random graphs that are difficult to analyze. Settling a number of conjectures and open problems, we show that the phase transition of so-called `bounded-size' Achlioptas processes have the same key features as the Erd\"o{}s-R\'{e}nyi reference model (which in the language of mathematical physics means that they are in the same `universality class').

June 2, 2021

2:00 PM

Meeting ID: 967 7304 6297 Email asuk@ucsd.edu for password

****************************