The H-free Process

Tom Bohman
Carnegie-Mellon University
Mathematical Sciences

Let H be a fixed graph. Consider the
random graph process given by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed.
In recent work with Peter Keevash we use the differential equations method for random graph processes to analyze the early evolution of this process (in the limit as n tends to infinity) for H strictly 2-balanced. When H is the complete graph K_s the graph produced gives a new lower bound on the Ramsey number R(s,t) for t large.
In this talk, we sketch this and related applications of the differential equations method.

Back to Workshop I: Probabilistic Techniques and Applications