BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Combinatorics and Probability Seminar
SUMMARY:Tilings in randomly perturbed graphs: bridging the
gap between Hajnal--Szemer\\'edi and Johansson-
-Kahn--Vu - Patrick Morris\, University of Berlin
(FU)
DTSTART:20190429T140000Z
DTEND:20190429T150000Z
UID:TALK3689AT
URL:/talk/index/3689
DESCRIPTION:A perfect $K_r$-tiling in a graph $G$ is a collect
ion of vertex-disjoint copies of $K_r$ that togeth
er cover all the vertices in $G$. In this paper we
consider perfect $K_r$-tilings in the setting of
randomly perturbed graphs\; a model introduced by
Bohman\, Frieze and Martin where one starts with
a dense graph and then adds $m$ random edges to it
. Specifically\, given any fixed $\\alpha$ between
$0$ and $1-1/r$ we determine how many random edge
s one must add to an $n$-vertex graph $G$ of minim
um degree $\\delta (G) \\geq \\alpha n$ to ensure
that\, asymptotically almost surely\, the resultin
g graph contains a perfect $K_r$-tiling. As one in
creases $\\alpha$ we demonstrate that the number o
f random edges required `jumps' at regular interva
ls\, and within these intervals our result is best
-possible. This work therefore closes the gap betw
een the seminal work of Johansson\, Kahn and Vu (
which resolves the purely random case\, i.e.\, $\\
alpha =0$) and that of Hajnal and Szemer\\'edi (wh
ich demonstrates that for $\\alpha \\geq 1-1/r$ th
e initial graph already houses the desired perfect
$K_r$-tiling).\n\n \n\n This is joint work with J
ie Han and Andrew Treglown.\n
LOCATION:Watson LTB
CONTACT:Johannes Carmesin
END:VEVENT
END:VCALENDAR