|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 25, 2008, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Torsten Mütze
Small subgraphs in random graphs and the power of multiple choices: The online case
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.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.3392 | admin login