Colloquium by Patrick Morris (Freie Universität Berlin): Clique tilings in randomly perturbed graphs

Feb 04, 2019 | 04:00 PM s.t.

A major theme in both extremal and probabilistic combinatorics is to find the appearance thresholds for certain spanning structures. Classical examples of such spanning structures include perfect matchings, Hamilton cycles and H-tilings, where we look for vertex disjoint copies of H covering all the vertices of some host graph G. In this talk we will focus on H-tilings in the case that H is a clique, a natural generalisation of a perfect matching. 
On the one hand there is the extremal question, how large does the minimum degree of an n-vertex graph G have to be to guarantee the existence of a clique factor in G? On the other hand, there is the probabilistic question. How large does p need to be to almost surely ensure the appearance of a clique factor in the Erdős-Rényi random graph G(n,p)? Optimal answers to these questions were given in two famous papers. The extremal question was answered by Hajnal and Szemerédi in 1970 and the probabilistic question by Johansson, Kahn and Vu in 2008. In this talk we bridge the gap between these two results by approaching the following question which contains the previous questions as special cases. Given an arbitrary graph of some fixed minimum degree, how many random edges need to be added on the same set of vertices to ensure the existence of a clique tiling? We give optimal answers to this question in all cases. Such results are part of a recent research trend studying properties of what is known as the randomly perturbed graph model, introduced by Bohman, Frieze and Martin in 2003. 
This is joint work with Jie Han and Andrew Treglown.

Time & Location

Feb 04, 2019 | 04:00 PM s.t.

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)