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
partners


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