Sparsification Preserves Triangle Factors at Tight Threshold

Triangle factors sit at the intersection of extremal graph theory and random graph thresholds: a graph must be dense enough to force disjoint triangles, but random sparsification can destroy the local structure needed to pack them across all vertices. Corrádi and Hajnal proved the deterministic minimum-degree side: an n-vertex graph with n divisible by 3 and minimum degree at least $2n/3$ contains a triangle factor. Johansson, Kahn, and Vu gave the corresponding random-graph threshold for $K_n$. This paper proves that the two phenomena are compatible under random sparsification.

The main theorem states that there is a constant $C>0$ such that, if $G$ has $n\in 3\mathbb{N}$ vertices and $\delta(G)\geq 2n/3$, then $G_p$ contains a triangle factor with high probability whenever

The authors also state that the minimum-degree condition and the probability condition are tight up to the constant $C$, so the theorem is not merely a dense-graph corollary of the complete-graph case.

Core Contribution

The contribution is a resilience theorem for triangle factors. Instead of asking whether the random graph $G(n,p)$ contains a perfect packing of triangles, the paper asks whether every deterministic host graph above the Corrádi–Hajnal degree threshold still has such a packing after each edge is independently retained with probability $p$.

That host-graph quantifier is the difficult part. A graph with minimum degree $2n/3$ may be far from complete and may have extremal structure near the threshold. The paper reduces this general setting to a tripartite regular model and then proves that random sparsification of the regular tripartite graph still contains a triangle factor at the same order of probability as the complete graph threshold, up to the logarithmic term and constant.

Technical Approach

The main technical theorem is the partite version. For every density parameter $0<d\leq 1$, the authors prove that an $(\epsilon,d^+)$-super-regular tripartite graph with three parts of size $n$ has a triangle factor in its random subgraph $\Gamma_p$ with high probability for $p\geq C(\log n)^{1/3}n^{-2/3}$. The reduction from the original graph uses the regularity method, a stability statement for the fractional Hajnal–Szemerédi theorem, and an analysis of extremal cases.

The proof then becomes a counting-and-extension argument for partial triangle factors. Proposition 3.2 shows that for all $t\leq(1-\eta)n$, the sparsified tripartite graph has roughly the expected number of embeddings of $t$ labelled disjoint triangles:

The technical center is the Local Distribution Lemma, supported by an Entropy Lemma. The authors control how embeddings of partial triangle factors are distributed around individual vertices, rather than only controlling their total number. This matters because a naive average can hide isolated vertices that cannot be extended into the final factor. The entropy argument shows that for almost all candidate vertices, the conditional distribution of the two remaining vertices in the triangle has entropy close to the benchmark $H(n,p,d)=\log((pd)^3n^2)$.

Results and Analysis

The theorem proves a high-probability triangle factor under the same minimum-degree threshold as Corrádi–Hajnal and at the same probability scale as the Johansson–Kahn–Vu threshold for triangle factors in the complete graph, up to the constant in front of $(\log n)^{1/3}n^{-2/3}$. That is the right comparison: the paper is not improving the complete-graph threshold, but showing that dense host graphs at the extremal degree boundary do not require a larger order of random retention.

Several auxiliary lemmas show how the proof handles the transition from dense structure to sparse randomness. Lemma 8.1, for example, gives triangle matchings of size at least $n/3-k$ when every large vertex subset contains at least $\mu n^3$ triangles and $p\geq Cn^{-2/3}$. Lemmas 8.3 through 8.5 handle small prescribed sets, sparse edge sets that extend to many triangles, and tripartite matching constructions using staged exposure and Janson-type bounds. These are not computational experiments; they are proof components that support the main high-probability statement.

The evidence is therefore mathematical rather than empirical. The result is convincing within its asymptotic regime, but the constants are existential and the proof depends on regularity-style reductions, so it does not give a practical algorithm or finite-size threshold for constructing triangle factors in a specific sampled graph. The paper ends by pointing toward an analogue for powers of Hamilton cycles: for every $k$, it conjectures that $p\geq Cn^{-1/k}$ and minimum degree $k n/(k+1)$ should force the $k$-th power of a Hamilton cycle in the random sparsification.