The ACO Seminar (2013–2014)

For a fixed graph H, the H-free process is the following random graph process. Starting with n isolated vertices, at each step add a new edge chosen uniformly at random from the non-edges whose addition does not create a (not necessarily induced) copy of H.  This process terminates with a maximal H-free graph with a random number M(H) of edges. For most graphs H containing a cycle, determining the likely asymptotic order of M(H) is an open problem.  For H satisfying a particular density condition (strict 2-balancedness), likely lower bounds are known which are conjectured to be optimal, and which have been shown to be for only a few special cases: K₃, K₄, and cycles of any fixed length.  But far less is known for graphs H not satisfying that density condition, with the smallest nontrivial example being the diamond graph, formed by removing an edge from K₄.  This talk will focus on the diamond-free process (for which we now know the right order of M(H)) and some of the interesting and unexpected complications that arise in its analysis.