A robust Corr\'adi--Hajnal Theorem
| Autor: | Allen, Peter, Böttcher, Julia, Corsten, Jan, Davies, Ewan, Jenssen, Matthew, Morris, Patrick, Roberts, Barnaby, Skokan, Jozef |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | For a graph $G$ and $p\in[0,1]$, we denote by $G_p$ the random sparsification of $G$ obtained by keeping each edge of $G$ independently, with probability $p$. We show that there exists a $C>0$ such that if $p\geq C(\log n)^{1/3}n^{-2/3}$ and $G$ is an $n$-vertex graph with $n\in 3\mathbb{N}$ and $\delta(G)\geq \tfrac{2n}{3}$, then with high probability $G_p$ contains a triangle factor. Both the minimum degree condition and the probability condition, up to the choice of $C$, are tight. Our result can be viewed as a common strengthening of the seminal theorems of Corr\'adi and Hajnal, which deals with the extremal minimum degree condition for containing triangle factors (corresponding to $p=1$ in our result), and Johansson, Kahn and Vu, which deals with the threshold for the appearance of a triangle factor in $G(n,p)$ (corresponding to $G=K_n$ in our result). It also implies a lower bound on the number of triangle factors in graphs with minimum degree at least $\tfrac{2n}{3}$ which gets close to the truth. Comment: 63 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|