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
Abstract:
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
Abstract:
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.