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
(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.