Lecture by Shagnik Das (Freie Universität Berlin): Randomly perturbed Ramsey problems

Dec 17, 2018 | 02:15 PM

The combinatorial properties much-loved Erdős-Rényi random graph G(n,p), which has n vertices and whose edges are present independently with probability p, have been comprehensively studied in the decades since its introduction.  In recent years, much research has been devoted to the randomly perturbed graph model, introduced in 2003 by Bohman, Frieze and Martin.  In this talk we shall present and motivate this new model of random graphs, and then focus on the Ramsey properties of these randomly perturbed graphs.  More precisely, given a pair of graphs (F,H), we ask how many random edges must be added to a dense graph G to ensure that any two-colouring of the edges of the perturbed graph has either a red copy of F or a blue copy of G.  This question was first studied in 2006 by Krivelevich, Sudakov and Tetali, who answered it in the case of F being a triangle and H being a clique.  We generalise these results, considering pairs of larger cliques, and, should the audience be willing (but even otherwise), shall take a quick look at some of the ideas required in our proofs.

This is joint work with Andrew Treglown (Birmingham).

Time & Location

Dec 17, 2018 | 02:15 PM

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)