Monday, December 6, 2010
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136, 10623 Berlin
room MA 041
Lecture - 14:15
Percolation, also called phase transition, deals with sudden macroscopic changes. These are ubiquitous in physics (freezing), sociology (tipping), network analysis (gridlock), computer science (random k-SAT) and elsewhere. In mathematics, the bedrock model is Erdos-Renyi (ER) in which edges are added randomly to a graph on n vertices which is initially empty. When the number of edges reaches n/2 there is a phase transition, and a "giant component" emerges. Here a very full mathematical understanding has been achieved, with rigorous mathematical proofs. In the Product Rule (PR) a powerful antigravity is introduced to ER that retards large components from merging. Here no theorems have been proven but we have compelling computer simulations indicating that a First Order (extremely sudden) phase transition occurs. In Bohman-Frieze (BF), ER is modified by a preference toward new edges using isolated vertices. Here some theorems have been proven, though much remains tantalizingly out of reach. (The follow-up lecture by William Perkins will discuss this in more detail.) We compare and contrast ER,PR and BF and discuss the various methodologies uses in the analyses.
Colloquium - 16:00
The Bohman-Frieze process is a random graph process that begins with an empty graph on n vertices. At each step, two potential edges are chosen uniformly at random from the edges not yet in the graph. If the first edge would join two isolated vertices, we add it; otherwise we add the second edge. This process was first proposed by Bohman and Frieze as a modification of the standard Erdos-Renyi random graph process with a bias in favor of small components. They showed that the critical point for the emergence of a giant component is later for their process than for Erdos-Renyi. Since then there have been several works studying this process and showing that much of its qualitative behavior matches that of Erdos-Renyi. We review some of these results and discuss the methods.