University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Tilings in randomly perturbed graphs: bridging the gap between Hajnal--Szemer\'edi and Johansson--Kahn--Vu

## Tilings in randomly perturbed graphs: bridging the gap between Hajnal--Szemer\'edi and Johansson--Kahn--VuAdd to your list(s) Download to your calendar using vCal - Patrick Morris, University of Berlin (FU)
- Monday 29 April 2019, 15:00-16:00
- Watson LTB.
If you have a question about this talk, please contact Johannes Carmesin. A perfect $K_r$-tiling in a graph $G$ is a collection of vertex-disjoint copies of $K_r$ that together 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 edges one must add to an $n$-vertex graph $G$ of minimum degree $\delta (G) \geq \alpha n$ to ensure that, asymptotically almost surely, the resulting graph contains a perfect $K_r$-tiling. As one increases $\alpha$ we demonstrate that the number of random edges required `jumps’ at regular intervals, and within these intervals our result is best-possible. This work therefore closes the gap between 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 (which demonstrates that for $\alpha \geq 1-1/r$ the initial graph already houses the desired perfect $K_r$-tiling).
This talk is part of the Combinatorics and Probability Seminar series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsTheoretical Physics Journal Club and Group Meeting Virtual Harmonic Analysis Seminar Reading Group in Combinatorics and Probability## Other talksThe imprint of their explosions: Using supernova remnants to understand stellar death The highwater algebra Discrete models of cellular mechanics |