Theory of Combinatorial Algorithms
Prof. Emo Welzl

 People Activity Report Previous Reports Research Mittagsseminar Teaching Workshops Social Activities Topics for Master / Bachelor Theses CGAL Geometric Algorithms Library
Mittagsseminar (in cooperation with A. Steger)

 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.

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