Thema der Dissertation:
Clique Factors: Extremal and Probabilistic Perspectives Thema der Disputation:
Rainbow matchings and the probabilistic method
Clique Factors: Extremal and Probabilistic Perspectives Thema der Disputation:
Rainbow matchings and the probabilistic method
Abstract: A K_r-factor in a graph G is a collection of vertex-disjoint copies of K_r covering the vertex
set of G. In this talk, we investigate these fundamental objects in three settings that lie at the
intersection of extremal and probabilistic combinatorics. We explore conditions that guarantee clique
factors in pseudorandom graphs and in randomly perturbed graphs and also address robustness for
K_3-factors. In each setting, we are able to provide the complete picture in certain regimes of
parameters, in particular for K_3-factors, by giving tight results. A rainbow matching in an edge coloured (multi-)graph is a collection of vertex disjoint edges, each
having a unique colour. The study of rainbow matchings dates back to Euler's research on Latin
squares and is now a vibrant area of modern combinatorics, rich in tantalising open conjectures.
Motivated by various areas of mathematics, principally design theory, problems in the area posit that
certain edge-coloured graphs have very large rainbow matchings, using (almost) all the available
colours. Few exact results are known but in recent years there have been several breakthrough
results proving asymptotic relaxations of key conjectures. In this talk, we will present very recent work of Munh\'a Correia, Pokrovskiy and Sudakov which
introduces a new approach to these problems and can be used to obtain strong asymptotic results
from weaker versions. The method is surprisingly simple and leads to short asymptotic proofs in
several settings. Some results are new and solve open conjectures whilst others provide alternative
proofs of results that previously required much more involved arguments. The key idea is a sampling
trick and this work is testament to the power of the probabilistic method to provide elegant proofs and
insight in combinatorics.
set of G. In this talk, we investigate these fundamental objects in three settings that lie at the
intersection of extremal and probabilistic combinatorics. We explore conditions that guarantee clique
factors in pseudorandom graphs and in randomly perturbed graphs and also address robustness for
K_3-factors. In each setting, we are able to provide the complete picture in certain regimes of
parameters, in particular for K_3-factors, by giving tight results. A rainbow matching in an edge coloured (multi-)graph is a collection of vertex disjoint edges, each
having a unique colour. The study of rainbow matchings dates back to Euler's research on Latin
squares and is now a vibrant area of modern combinatorics, rich in tantalising open conjectures.
Motivated by various areas of mathematics, principally design theory, problems in the area posit that
certain edge-coloured graphs have very large rainbow matchings, using (almost) all the available
colours. Few exact results are known but in recent years there have been several breakthrough
results proving asymptotic relaxations of key conjectures. In this talk, we will present very recent work of Munh\'a Correia, Pokrovskiy and Sudakov which
introduces a new approach to these problems and can be used to obtain strong asymptotic results
from weaker versions. The method is surprisingly simple and leads to short asymptotic proofs in
several settings. Some results are new and solve open conjectures whilst others provide alternative
proofs of results that previously required much more involved arguments. The key idea is a sampling
trick and this work is testament to the power of the probabilistic method to provide elegant proofs and
insight in combinatorics.
Zeit & Ort
11.10.2021 | 17:00