Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 25, 2008, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Torsten Mütze
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$.
In a 2007 paper by Krivelevich, Loh, and Sudakov, the problem of avoiding a copy of some fixed graph $F$ in $G_N$ for as long as possible is considered, and a threshold result is derived for some special cases. Moreover, the authors conjecture a general threshold formula for arbitrary graphs $F$. We disprove this conjecture and give the complete solution of the problem by deriving explicit threshold functions $N_0(F,r,n)$ for arbitrary graphs $F$ and any fixed integer $r$.
Joint work with Reto Spöhel and Henning Thomas.
Automatic MiSe System Software Version 1.4803M | admin login