BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: A major theme in both extremal and probabilistic combinatorics
is to find the appearance thresholds for certain spanning structures. Clas
sical examples of such spanning structures include perfect matchings\, Hami
lton 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 f
ocus on H -tilings in the case that H is a clique\, a natural generalisa
tion 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\, t
here 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 f
amous 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 f
ollowing question which contains the previous questions as special cases. G
iven an arbitrary graph of some fixed minimum degree\, how many random edge
s 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\, Friez
e and Martin in 2003. This is joint work with Jie Han and Andrew Treglown.
DTSTAMP:20181221T141400
DTSTART:20190204T160000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Patrick Morris (Freie Universität Berlin): Clique tilings in random
ly perturbed graphs
UID:94864056@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20190204-C-Morris.html
END:VEVENT
END:VCALENDAR