Small Subgraphs in the Achlioptas Process

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 recent 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 Torsten Mütze and Henning Thomas.