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 listsRSLC PhD/Postdoc Seminars (Chemistry) Contemporary History Seminar Metallurgy & Materials – Tech Entrepreneurship Seminar Series## Other talksProvably Convergent Plug-and-Play Quasi-Newton Methods for Imaging Inverse Problems Signatures of structural criticality and universality in the cellular anatomy of the brain The percolating cluster is invisible to image recognition with deep learning Statistical Physics Perturbation Theory Applied to the Ising Model on the Square, Cubic and Hypercubic Lattices [Friday seminar]: Irradiated brown dwarfs in the desert |