## 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)
## Abstract:

Consider the following random graph process
(G_{m})_{m∈N} on the vertex
set [n]. Let G_{0} be the empty graph and, for each m∈N, let
G_{m} be
obtained from G_{m–1} by adding a single edge, chosen uniformly from
those non-edges of G_{m–1} which do not create a triangle. The process
ends when we reach a maximal triangle-free graph; we denote by
G_{n,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(G_{n,triangle}),
very little was known about the random triangle-free
graph G_{n,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 G_{n,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.