Consider the following random process. At each round, one is presented with two random edges from the edge set of the complete graph on n vertices, and is asked to choose one of them. The selected edges are collected into a graph, which thus grows at the rate of one edge per round. This is known in the literature as an Achlioptas process, and has been studied by many researchers, mainly in the context of delaying or accelerating the appearance of the giant component.In our work, we investigate the classical small subgraph problem for Achlioptas processes. That is, given a fixed graph $H$, we study whether there is a deterministic online algorithm that substantially delays or accelerates a typical appearance of $H$, compared to its threshold of appearance in the random graph $G(n,M)$. It is easy to see that one cannot accelerate the appearance of any fixed graph by more than a factor of 2, so we concentrate on the task of avoiding $H$. We determine thresholds for the avoidance of all cycles $C_t$, cliques $K_t$, and complete bipartite graphs $K_{t,t}$.
Joint work with Michael Krivelevich and Benny Sudakov.