ACO The ACO Seminar (2013–2014)

Mar. 27, 3:30pm, Wean 8220
Mike Picollelli, Carnegie Mellon University
The diamond-free process


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: K3, K4, 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 K4.  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.

Back to the ACO home page