# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# 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

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

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