Combinatorics Seminar

When: Sunday, January 10, 10am
Where: Schreiber 309
Speaker: Gonzalo Fiz Pontiveros, Hebrew University
Title: The triangle-free process and R(3,k)


Consider the following random graph process (Gm)m∈N on the vertex set [n]. Let G0 be the empty graph and, for each m∈N, let Gm be obtained from Gm–1 by adding a single edge, chosen uniformly from those non-edges of Gm–1 which do not create a triangle. The process ends when we reach a maximal triangle-free graph; we denote by Gn,triangle this (random) final graph. This "triangle-free process" was suggested by Bollobás and Erdős in 1990 as a possible method of producing good Ramsey graphs, but until Bohman's breakthrough paper in 2009, which determined the order of magnitude of e(Gn,triangle), very little was known about the random triangle-free graph Gn,triangle it produces.

A technique which has proved extremely useful in the study of random graph processes is the so-called differential equations method, which was introduced by Wormald in the late 1990s. In this method, the idea is to track a collection of graph parameters, by showing that (with high probability) they closely follow the solution of a corresponding family of differential equations.

The aim of this talk is to give an overview of this method and to discuss a recent refinement of Bohman's result, which determines asymptotically the number of edges in Gn,triangle, and moreover shows that it shares many properties with the Erdős-Rényi random graph G(n,m) of the same density. As an application, we improve Kim's lower bound on the Ramsey number R(3,k), obtaining a bound within a factor of four of Shearer's upper bound.

This is joint work with Simon Griffiths and Rob Morris. Similar results were obtained independently by Tom Bohman and Peter Keevash.