A robust Corrádi–Hajnal theorem

Peter Allen, Julia Böttcher, Jan Corsten, Ewan Davies, Matthew Jenssen, Patrick Morris*, Barnaby Roberts, Jozef Skokan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

For a graph (Formula presented.) and (Formula presented.), we denote by (Formula presented.) the random sparsification of (Formula presented.) obtained by keeping each edge of (Formula presented.) independently, with probability (Formula presented.). We show that there exists a (Formula presented.) such that if (Formula presented.) and (Formula presented.) is an (Formula presented.) -vertex graph with (Formula presented.) and (Formula presented.), then with high probability (Formula presented.) contains a triangle factor. Both the minimum degree condition and the probability condition, up to the choice of (Formula presented.), are tight. Our result can be viewed as a common strengthening of the seminal theorems of Corrádi and Hajnal, which deals with the extremal minimum degree condition for containing triangle factors (corresponding to (Formula presented.) in our result), and Johansson, Kahn and Vu, which deals with the threshold for the appearance of a triangle factor in (Formula presented.) (corresponding to (Formula presented.) in our result). It also implies a lower bound on the number of triangle factors in graphs with minimum degree at least (Formula presented.) which gets close to the truth.

Original languageEnglish
Pages (from-to)61-130
Number of pages70
JournalRandom Structures and Algorithms
Volume65
Issue number1
DOIs
Publication statusPublished - Aug 2024

Keywords

  • clique factors
  • extremal graph theory
  • random graphs
  • robustness

Fingerprint

Dive into the research topics of 'A robust Corrádi–Hajnal theorem'. Together they form a unique fingerprint.

Cite this