The phase transition in random graph processes through the lens of PDE and singularity analysis

The phase transition in random graph processes through the lens of PDE and singularity analysis

Tue, 24/01/2012
14:30 		Mihyun Kang (TU Graz) Combinatorial Theory Seminar Add to calendar L3
The phase transition in random graph processes through the lens of PDE and singularity analysis
The phase transition deals with sudden global changes and is observed in many fundamental random discrete structures arising from statistical physics, mathematics and theoretical computer science, for example, Potts models, random graphs and random $ k $-SAT. The phase transition in random graphs refers to the phenomenon that there is a critical edge density, to which adding a small amount results in a drastic change of the size and structure of the largest component. In the Erdős–Rényi random graph process, which begins with an empty graph on $ n $ vertices and edges are added randomly one at a time to a graph, a phase transition takes place when the number of edges reaches $ n/2 $ and a giant component emerges. Since this seminal work of Erdős and Rényi, various random graph processes have been introduced and studied. In this talk we will discuss new approaches to study the size and structure of components near the critical point of random graph processes: key techniques are the classical ordinary differential equations method, a quasi-linear partial differential equation that tracks key statistics of the process, and singularity analysis.