2022/09/02 by Peter J. Allen, Peter Allen, Allen, Peter +14 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.2209.01116
openalex publication_date 2022/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G and p∈[0,1], we denote by Gp 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≥ C(log n)1/3n-2/3 and G is an n-vertex graph with n∈ 3ℕ and δ(G)≥ \tfrac2n3, then with high probability Gp 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ádi 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=Kn in our result). It also implies a lower bound on the number of triangle factors in graphs with minimum degree at least \tfrac2n3 which gets close to the truth.