Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 05, 2011, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Henning Thomas
The evolution of the largest component has been studied intensely in a variety of random graph processes, starting in 1960 with the Erdös-Rényi process. It is well known that this process undergoes a phase transition at n/2 edges when, asymptotically almost surely, a linear-sized component appears. Moreover, this phase transition is continuous, i.e., in the limit the function f(c) denoting the fraction of vertices in the largest component in the process after c*n edge insertions is continuous. A variation of the Erdös-Rényi process are the so-called Achlioptas processes in which in every step a random pair of edges is drawn, and a fixed edge-selection rule selects one of them to be included in the graph while the other is put back. Recently, Achlioptas, D'Souza and Spencer (2009) gave strong numerical evidence that a variety of edge-selection rules exhibit a discontinuous phase transition. However, Riordan and Warnke (2011) very recently showed that all Achlioptas processes have a continuous phase transition. In this talk, I will sketch their proof and furthermore, present a class of Erdös-Rényi-like processes for which we can prove a discontinuous phase transition.
Automatic MiSe System Software Version 1.4803M | admin login