# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

__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

## 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: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 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.4803M | admin login