pith. sign in

arxiv: 2604.25250 · v1 · submitted 2026-04-28 · 🧮 math.CO

Triangle packings in randomly perturbed graphs

Xinbu Cheng , Hong Liu , Lanchao Wang , Zhifei Yan This is my paper

Pith reviewed 2026-05-07 16:00 UTC · model grok-4.3

classification 🧮 math.CO
keywords triangle packingrandomly perturbed graphsNash-Williams conjectureregular graphsrandom graphsgraph decompositionsthreshold phenomena
0
0 comments X

The pith

A dn-regular graph unioned with random G(n,p) for p above 2d/(1+2d) admits a triangle packing covering all but o(n²) edges with high probability, and the bound is sharp for d at most 1/2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that adding random edges above a precise density threshold to any fixed regular graph enables a near-perfect covering of the edges by triangles. A sympathetic reader would care because this shows how modest randomness can achieve packings that deterministic regularity alone does not guarantee, bridging pure random-graph results with classical decomposition conjectures. The authors prove the statement for every d greater than zero and every p larger than 2d over 1 plus 2d, with the threshold optimal when d is at most one-half. Their argument rests on a fresh triangle-weighting lemma that operates on the combined edge set of the perturbed graph.

Core claim

For every d>0 and every p>2d/(1+2d), if G_d is a dn-regular graph on n vertices, then with high probability the union G_d ∪ G(n,p) contains a triangle packing covering all but o(n²) edges. Moreover, this bound on p is best possible for 0<d≤1/2. A key ingredient in the proof is a new triangle-weighting lemma for weighted complete graphs.

What carries the argument

A new triangle-weighting lemma for weighted complete graphs, used to extract a large triangle packing from the edge weights induced by the regular graph plus the random edges.

If this is right

  • The threshold for near-perfect triangle packings is fully determined when the regular part has density at most 1/2.
  • Graphs whose minimum degree lies below the Nash-Williams threshold still admit near-perfect triangle packings once supplemented by sufficiently dense random edges.
  • The packing result holds uniformly over all choices of the dn-regular graph, with the randomness coming only from the added edges.
  • The same perturbation technique yields packings that cover a (1-o(1)) fraction of the total edges rather than merely a positive fraction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The weighting approach may adapt to packings of larger cliques or other fixed subgraphs in similarly perturbed graphs.
  • For d larger than 1/2 the critical p value could be governed by different obstructions and might require separate analysis.
  • The result quantifies a form of resilience: a fixed regular graph becomes decomposable into triangles after a small random perturbation.
  • Algorithmic search for triangle packings could first handle the regular component and then use the random edges to resolve remaining obstructions.

Load-bearing premise

The triangle-weighting lemma applies directly to the edge weights arising in the union of the fixed regular graph and the independent random graph without further restrictions.

What would settle it

Exhibit a specific dn-regular graph for some d≤1/2 and a p slightly below 2d/(1+2d) such that, with positive probability, the union leaves a positive fraction of edges uncovered by any triangle packing.

Figures

Figures reproduced from arXiv: 2604.25250 by Hong Liu, Lanchao Wang, Xinbu Cheng, Zhifei Yan.

Figure 1
Figure 1. Figure 1: illustrates the currently known behaviour of pd. Our results determine pd for d ⩽ 1/2, while for 1/2 < d ⩽ 0.82733 the correct value remains unknown. d p 0 1 2 3 4 0.83 1 2 view at source ↗
read the original abstract

The longstanding Nash-Williams conjecture asserts that every $K_3$-divisible graph $G$ with $\delta(G)\ge 3n/4$ admits a triangle decomposition. In the random setting, Frankl and R\"odl showed that, with high probability, $G(n,p)$ contains a triangle packing covering all but $o(n^2p)$ edges whenever $p\ge n^{-1/2+\varepsilon}$. In this paper, we study near-perfect triangle packings in randomly perturbed graphs. We prove that for every $d>0$ and every $p>2d/(1+2d)$, if $G_d$ is a $dn$-regular graph on $n$ vertices, then with high probability the union $G_d\cup G(n,p)$ contains a triangle packing covering all but $o(n^2)$ edges. Moreover, this bound on $p$ is best possible for $0<d\le 1/2$, thereby determining the threshold in this range. A key ingredient in the proof is a new triangle-weighting lemma for weighted complete graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves that for every d > 0 and p > 2d/(1+2d), if G_d is any dn-regular graph on n vertices, then with high probability the union G_d ∪ G(n,p) contains a triangle packing covering all but o(n²) edges. The bound on p is shown to be sharp for 0 < d ≤ 1/2. The proof introduces and applies a new triangle-weighting lemma for weighted complete graphs, extending results of Frankl-Rödl on random graphs and relating to the Nash-Williams conjecture in the perturbed setting.

Significance. If the central claims hold, the result determines the precise threshold for near-perfect triangle packings in randomly perturbed regular graphs for d ≤ 1/2, providing a sharp analogue to the Frankl-Rödl theorem in the presence of a fixed dense regular graph. The new weighting lemma is a potentially reusable tool for other packing problems in weighted graphs. The sharpness construction for small d is a notable strength, as is the uniform treatment over arbitrary G_d.

major comments (2)
  1. [§3 (triangle-weighting lemma) and §4 (application to perturbed graph)] The applicability of the triangle-weighting lemma (introduced in §3) to the weight function w induced by G_d ∪ G(n,p) is not verified in sufficient detail. For arbitrary dn-regular G_d, the edge weights can exhibit local degree fluctuations of order d n that are not uniformly smoothed by G(n,p) at the threshold density; the lemma's hypotheses on minimum weighted degree and bounded discrepancy must be checked to hold with high probability uniformly over all such G_d, but no explicit error-term calculation or concentration argument addressing the worst-case G_d is supplied.
  2. [§5 (sharpness)] The sharpness claim for 0 < d ≤ 1/2 (stated in the abstract and proved in §5) relies on a specific construction of G_d that forces many edges to remain unpackable below the threshold p. However, the argument does not explicitly rule out that a different choice of G_d could require a strictly larger p, which would undermine the 'best possible' statement; the reduction to the weighting lemma in the lower-bound direction needs to be checked for completeness.
minor comments (2)
  1. [Abstract and §1] Notation for the o(n²) error term is used throughout but never made explicit in terms of the failure probability or the dependence on d and p; a short remark clarifying the whp statement would improve readability.
  2. [§3] The statement of the weighting lemma should include a precise list of its hypotheses (minimum degree, total weight, discrepancy bound) so that the reader can immediately see why they are satisfied by the perturbed weights.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable feedback on our manuscript. We are pleased that the significance of the results is recognized. Below, we provide point-by-point responses to the major comments, and we will incorporate necessary clarifications and additional details in the revised version.

read point-by-point responses

  1. Referee: [§3 (triangle-weighting lemma) and §4 (application to perturbed graph)] The applicability of the triangle-weighting lemma (introduced in §3) to the weight function w induced by G_d ∪ G(n,p) is not verified in sufficient detail. For arbitrary dn-regular G_d, the edge weights can exhibit local degree fluctuations of order d n that are not uniformly smoothed by G(n,p) at the threshold density; the lemma's hypotheses on minimum weighted degree and bounded discrepancy must be checked to hold with high probability uniformly over all such G_d, but no explicit error-term calculation or concentration argument addressing the worst-case G_d is supplied.

    Authors: We appreciate the referee highlighting this aspect. In Section 4, the application proceeds by showing that the random perturbation G(n,p) ensures the weighted graph satisfies the conditions of the triangle-weighting lemma with high probability. Specifically, the minimum weighted degree is at least (1-o(1)) times the expected value, and the discrepancy is controlled by the random edges. While the argument relies on standard concentration bounds (Chernoff and union bound over vertices), we acknowledge that explicit error terms for the worst-case G_d were not expanded. In the revision, we will include a detailed calculation of the probability bounds, verifying that for p > 2d/(1+2d), the failure probability is o(1) uniformly in G_d. This will be added as a new subsection or appendix if necessary. revision: yes

  2. Referee: [§5 (sharpness)] The sharpness claim for 0 < d ≤ 1/2 (stated in the abstract and proved in §5) relies on a specific construction of G_d that forces many edges to remain unpackable below the threshold p. However, the argument does not explicitly rule out that a different choice of G_d could require a strictly larger p, which would undermine the 'best possible' statement; the reduction to the weighting lemma in the lower-bound direction needs to be checked for completeness.

    Authors: We clarify that our main theorem establishes the result for every dn-regular graph G_d, so p > 2d/(1+2d) is sufficient for all such graphs. The construction in Section 5 demonstrates necessity for some G_d, showing that below the threshold the packing fails whp for that G_d. This establishes that the bound is best possible, as improving it would violate the theorem for that particular G_d. No other G_d can require a larger p, as the upper bound holds universally. Regarding the reduction to the weighting lemma for the lower bound, we will review and expand the details in Section 5 to make the application explicit. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external facts and a new lemma

full rationale

The abstract and reader's summary present the main result as building on the Nash-Williams conjecture, Frankl-Rödl random-graph packing theorem, and a newly introduced triangle-weighting lemma for weighted complete graphs. No equations or self-citations in the provided text reduce the threshold p > 2d/(1+2d) or the o(n²) packing guarantee to a fitted parameter or prior self-result by construction. The lemma is stated as an independent ingredient whose applicability to G_d ∪ G(n,p) weights is asserted without circular reduction to the target statement. This is the expected non-finding for a paper whose central claim extends known external tools.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Only the abstract is available, so the ledger records typical background assumptions of probabilistic combinatorics rather than paper-specific free parameters or invented objects.

axioms (2)
  • standard math Probabilistic method guarantees for 'with high probability' statements in G(n,p)
    Invoked for the existence of the triangle packing in the perturbed graph.
  • domain assumption Divisibility and degree conditions for triangle packings
    Underlying the Nash-Williams conjecture and the packing definition.

pith-pipeline@v0.9.0 · 5494 in / 1589 out tokens · 58672 ms · 2026-05-07T16:00:46.631172+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Antoniuk, N

    S. Antoniuk, N. Kam c ev, C. Reiher, and T. P. Tukara. The complete picture for clique factors in randomly perturbed graphs. arxiv:2603.22081 , 2026

    work page arXiv 2026

  2. [2]

    Bennett, A

    P. Bennett, A. Dudek, and A. Frieze. Adding random edges to create the square of a H amilton cycle. arxiv:1710.02716 , 2017

    work page arXiv 2017

  3. [3]

    Bohman, A

    T. Bohman, A. Frieze, and R. Martin. How many random edges make a dense graph H amiltonian? Random Structures Algorithms , 22(1):33--42, 2003

    work page 2003

  4. [4]

    Barber, D

    B. Barber, D. K\" u hn, A. Lo, and D. Osthus. Edge-decompositions of graphs with high minimum degree. Adv. Math. , 288:337--385, 2016

    work page 2016

  5. [5]

    B\" o ttcher, R

    J. B\" o ttcher, R. Montgomery, O. Parczyk, and Y. Person. Embedding spanning bounded degree graphs in randomly perturbed graphs. Mathematika , 66(2):422--447, 2020

    work page 2020

  6. [6]

    B\" o ttcher, O

    J. B\" o ttcher, O. Parczyk, A. Sgueglia, and J. Skokan. Triangles in randomly perturbed graphs. Combin. Probab. Comput. , 32(1):91--121, 2023

    work page 2023

  7. [7]

    Balogh, A

    J. Balogh, A. Treglown, and A. Z. Wagner. Tilings in randomly perturbed dense graphs. Combin. Probab. Comput. , 28(2):159--176, 2019

    work page 2019

  8. [8]

    D. Conlon. Extremal graph theory (lecture notes). https://www.its.caltech.edu/ dconlon/Extremal-course.html

    work page

  9. [9]

    P. J. Dukes and D. Horsley. On the minimum degree required for a triangle decomposition. SIAM J. Discrete Math. , 34(1):597--610, 2020

    work page 2020

  10. [10]

    Delcourt, C

    M. Delcourt, C. Henderson, T. Lesgourgues, and L. Postle. Beyond N ash- W illiams: Counterexamples to clique decomposition thresholds for all cliques larger than triangles. arxiv:2508.20819 , 2025

    work page arXiv 2025

  11. [11]

    Delcourt, T

    M. Delcourt, T. Kelly, and L. Postle. Clique decompositions in random graphs via refined absorption. arxiv:2402.17857 , 2024

    work page arXiv 2024

  12. [12]

    Delcourt and L

    M. Delcourt and L. Postle. Progress towards N ash- W illiams' conjecture on triangle decompositions. J. Combin. Theory Ser. B , 146:382--416, 2021

    work page 2021

  13. [13]

    F. Dross. Fractional triangle decompositions in graphs with large minimum degree. SIAM J. Discrete Math. , 30(1):36--42, 2016

    work page 2016

  14. [14]

    Das and A

    S. Das and A. Treglown. Ramsey properties of randomly perturbed graphs: cliques and cycles. Combin. Probab. Comput. , 29(6):830--867, 2020

    work page 2020

  15. [15]

    Frankl and V

    P. Frankl and V. R\" o dl. Near perfect coverings in graphs and hypergraphs. European J. Combin. , 6(4):317--326, 1985

    work page 1985

  16. [16]

    Garaschuk

    K. Garaschuk. Linear methods for rational triangle decompositions . PhD thesis, University of Victoria, 2014

    work page 2014

  17. [17]

    Gustavsson

    T. Gustavsson. Decompositions of large graphs and digraphs with high minimum degree. 1991

    work page 1991

  18. [18]

    J. Han, P. Morris, and A. Treglown. Tilings in randomly perturbed graphs: bridging the gap between H ajnal- S zemer\' e di and J ohansson- K ahn- V u. Random Structures Algorithms , 58(3):480--516, 2021

    work page 2021

  19. [19]

    P. E. Haxell and V. R\" o dl. Integer and fractional packings in dense graphs. Combinatorica , 21(1):13--38, 2001

    work page 2001

  20. [20]

    Joos and J

    F. Joos and J. Kim. Spanning trees in randomly perturbed graphs. Random Structures Algorithms , 56(1):169--219, 2020

    work page 2020

  21. [21]

    T. P. Kirkman. On a problem in combinatorics. Cambridge Dublin Math. J. , 2:191--204, 1847

    work page

  22. [22]

    Krivelevich, M

    M. Krivelevich, M. Kwan, and B. Sudakov. Bounded-degree spanning trees in randomly perturbed graphs. SIAM J. Discrete Math. , 31(1):155--171, 2017

    work page 2017

  23. [23]

    C. St. J. A. Nash-Williams. An unsolved problem concerning decomposition of graphs into triangles. pages 1179--1183, 1970

    work page 1970

  24. [24]

    R. Yuster. Combinatorial and computational aspects of graph packing and graph decomposition. Comput. Sci. Rev. , 1(1):12--26, 2007

    work page 2007