Combinatorics Seminar
When: Sunday, January 8, 10am
Where: Schreiber 309
Speaker: Wojciech Samotij, University of Cambridge
Title: Stability results for random discrete structures
Abstract:
Two years ago, Conlon and Gowers, and Schacht proved general
theorems that allow one to transfer a large class of extremal
combinatorial results from the deterministic to the probabilistic
setting. Even though the two papers solve the same set of
long-standing open problems in probabilistic combinatorics,
the methods used in them vary significantly and therefore yield
results that are not comparable in certain aspects. The theorem
of Schacht can be applied in a more general setting and yields
stronger probability estimates, whereas the one of Conlon and
Gowers also implies random versions of some structural statements
such as the famous stability theorem of Erdos and Simonovits.
We bridge the gap between these two transference theorems.
Building on the approach of Schacht, we prove a general theorem
that allows one to transfer deterministic stability results to
the probabilistic setting that is somewhat more general and
stronger then the one obtained by Conlon and Gowers. We then use
this theorem to derive several new results, among them a random
version of the Erdos-Simonovits stability theorem for arbitrary
graphs.