#
Monday Lecture and Colloquium

**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**

### Joel Spencer -
Courant Institute of Mathematical Sciences, New York

### Discrete Percolation

*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**

###
Will Perkins - Courant Institute of Mathematical Sciences, New York

###
The Bohman-Frieze Process

*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.

Letzte Aktualisierung:
17.11.2010