Mar. 27, 3:30pm, Wean 8220

Mike Picollelli, Carnegie Mellon University

The diamond-free process

Mike Picollelli, Carnegie Mellon University

The diamond-free process

Abstract:

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*_{3}, *K*_{4}, 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*_{4}. 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.