Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, January 20, 2011, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Reto Spöhel (MPI Saarbrücken)
The standard paradigm for online power of two choices problems in random graphs is the Achlioptas process. Here we consider the following natural generalization: Starting with $G_0$ as the empty graph on $n$ vertices, in every step a set of $r$ edges is drawn uniformly at random from all edges that have not been drawn in previous steps. From these, one edge has to be selected, and the remaining $r-1$ edges are discarded. Thus after $N$ steps, we have seen $rN$ edges, and selected exactly $N$ out of these to create a graph $G_N$.
The problem of avoiding copies of some given fixed graph $F$ for as long as possible in this process (with $r$= const.) was first studied by Krivelevich, Loh, and Sudakov (2009), and solved completely by Torsten Mütze, Henning Thomas, and myself.
In this talk we consider the opposite problem of creating a copy of $F$ as quickly as possible. As we shall see, this problem behaves quite differently - in particular, it is only interesting if $r$ is assumed to be a growing function of $n$. We give general bounds on the threshold of this problem, and derive exact thresholds for trees and cycles of arbitrary size, and for $F=K_4$.
Joint work with Michael Krivelevich (Tel Aviv University).
Automatic MiSe System Software Version 1.4803M | admin login