Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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