Phase transitions in random graph processes
Mihyun Kang, TU Graz
The phase transition is a fascinating phenomenon observed in mathematics and natural sciences in many different contexts. It deals with a sudden change in the properties of an asymptotically large structure by altering critical parameters. The phase transition in random graphs refers to a 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"os and Re'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"0s and Re'nyi, various random graph processes have been introduced and studied. In this talk we will discuss phase transitions in several random graph processes.