Pith. sign in

REVIEW 2 minor 17 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

Tuza's conjecture on triangle edge covers holds in random geometric graphs over a wide density range.

2026-06-27 15:49 UTC pith:L2LG6TP6

load-bearing objection The paper verifies Tuza's conjecture for random geometric graphs over a density range and gives almost-perfect packings for an infinite family of F, but the abstract supplies no proof details.

arxiv 2606.09736 v1 pith:L2LG6TP6 submitted 2026-06-08 math.CO cs.DM

Almost-perfect packings and Tuza's conjecture in the random geometric graph

Patrick Bennett , Ryan Cushman , Andrzej Dudek , Xavier P\'erez-Gim\'enez This is my paper
classification math.CO cs.DM
keywords Tuza conjecturerandom geometric graphstriangle packingedge coversalmost-perfect packingsgeometric graphsgraph packings
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper sets out to confirm Tuza's conjecture inside the random geometric graph model, where points are placed at random in a region and edges connect pairs within a fixed distance. Tuza's conjecture asserts that any graph has a set of at most twice the maximum number of edge-disjoint triangles that hits every triangle. Establishing the bound in this geometric random setting supplies direct evidence for the conjecture under spatial constraints. The work further shows that almost all edges can be covered by edge-disjoint copies of certain fixed graphs F, for an infinite family of such F.

Core claim

We show that Tuza's conjecture holds in the random geometric graph for a large range of densities. We also show the existence of almost-perfect packings for an infinite family of F.

What carries the argument

The random geometric graph with connection radius tuned across density regimes, together with its triangle packing number and minimum triangle edge cover.

Load-bearing premise

The connection radius must be chosen so the resulting graph sits in a density regime whose local triangle structure permits the global packing and covering bounds to apply.

What would settle it

A single random geometric graph realization at some density where the minimum triangle edge cover exceeds twice the maximum triangle packing would falsify the claim for that regime.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Tuza's bound of twice the packing number applies to triangle covers in this model across many densities.
  • Almost-perfect edge packings exist for an infinite family of fixed graphs F.
  • Negative results show that almost-perfect packings fail for certain other choices of F.

Where Pith is reading between the lines

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

  • The same methods could be tried on packings of larger cliques or other fixed subgraphs in the same model.
  • Similar verification of Tuza's conjecture might be attempted in the Erdős–Rényi random graph at comparable densities.
  • The density thresholds identified here mark natural boundaries where packing behavior may shift, inviting further analysis at the transition points.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The paper proves that Tuza's conjecture holds for the random geometric graph G(n,r) over a large range of the density parameter r, establishes the existence of almost-perfect packings by edge-disjoint copies of a fixed graph F for an infinite family of F, and provides some negative results for other F.

Significance. If the results hold, they extend Tuza's conjecture to the random geometric setting and advance packing-covering problems in geometric random graphs, which are central to both extremal combinatorics and applications in geometric probability. The work supplies explicit density regimes and an infinite family of positive packing results.

minor comments (2)
  1. The abstract states the main theorems at a high level; a brief indication of the proof strategy (e.g., the use of the geometric structure or the range of r) in the introduction would help readers assess the scope immediately.
  2. Notation for the random geometric graph G(n,r) and the packing number ν(G) is standard, but the precise definition of 'almost-perfect packing' (e.g., the o(1) fraction of uncovered edges) should be stated explicitly when first introduced.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending minor revision. The report contains no specific major comments.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper claims that Tuza's conjecture holds in random geometric graphs over a density range and that almost-perfect F-packings exist for an infinite family of F. These are existential and probabilistic statements about graph properties in a random model. No derivation step reduces a claimed prediction or theorem to a fitted parameter, self-definition, or self-citation chain by the paper's own equations. The density regime is an explicit modeling assumption rather than a circular construct. The work is self-contained against external benchmarks such as the original Tuza conjecture and standard random geometric graph theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger records the minimal domain assumptions required to state the claims.

axioms (1)
  • domain assumption Standard definition and properties of the random geometric graph model in the unit square with Euclidean distance threshold.
    The model is invoked throughout the abstract as the setting in which the claims hold.

pith-pipeline@v0.9.1-grok · 5649 in / 1092 out tokens · 27418 ms · 2026-06-27T15:49:46.057717+00:00 · methodology

0 comments
read the original abstract

The triangle packing number $\nu(G)$ of a graph $G$ is the maximum size of a set of edge-disjoint triangles in $G$. Tuza conjectured that in any graph $G$ there exists a set of at most $2\nu(G)$ edges intersecting every triangle in $G$. We show that Tuza's conjecture holds in the random geometric graph for a large range of densities. We also study the problem of covering almost all edges of the random geometric graph with edge-disjoint copies of some fixed graph $F$. In particular, we show the existence of almost-perfect packings for an infinite family of $F$, and state some negative results as well.

Figures

Figures reproduced from arXiv: 2606.09736 by Andrzej Dudek, Patrick Bennett, Ryan Cushman, Xavier P\'erez-Gim\'enez.

Figure 1
Figure 1. Figure 1: The graph of cells C for d = 2. Observe that each cell of C contains n/n0 points of X in expectation. Next, we show that we can slightly perturb X to guarantee that every cell has the same amount of points. Lemma 10. Let 0 < ε < 1 and κ2 > 0 be sufficiently large given ε. A.a.s. it is possible to alter X by adding at most 4εn points and removing at most 4εn points to form a new set of points X′ which has e… view at source ↗
Figure 2
Figure 2. Figure 2: The random experiment to generate equilateral triangles for d = 2. After choosing Y1 and Y2 there are exactly two choices for Y3. equilateral in the sense that all three edges will have similar lengths. This attempt may fail (and return T = ∅ and/or E = ∅) with some small probability that we will bound later. For each i = 1, 2, 3, let Ci be cell that contains the random point Yi . Then we choose one point … view at source ↗
Figure 3
Figure 3. Figure 3: Random triangle {W1, W2, W3} = {Y1, Y2, Y3} in T1 as on step (ii) of Random Experiment III. (iii) Generate a random triangle T of G ′ (thus an edge of H′ ) and a random edge E of G ′ (thus a vertex of H′ ) contained in T, exactly as on step (ii) of Random Experiment I. More precisely, E = {X′ 1 , X′ 2} and T = {X′ 1 , X′ 2 , X′ 3} where, for i = 1, 2, 3, Ci is the cell of C that contains Yi and X′ i is a r… view at source ↗

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

17 extracted references

  1. [1]

    Aharoni and S

    R. Aharoni and S. Zerbib. A generalization of Tuza’s conjecture.J. Graph Theory, 94(3):445–462, 2020

    2020

  2. [2]

    J. D. Baron and J. Kahn. Tuza’s conjecture is asymptotically tight for dense graphs.Combin. Probab. Comput., 25(5):645–667, 2016

    2016

  3. [3]

    Bennett, R

    P. Bennett, R. Cushman, and A. Dudek. Closing the random graph gap in Tuza’s conjecture through the online triangle packing process.SIAM J. Discrete Math., 35(3):2145–2169, 2021

    2021

  4. [4]

    Bennett, A

    P. Bennett, A. Dudek, and S. Zerbib. Large triangle packings and Tuza’s conjecture in sparse random graphs.Combin. Probab. Comput., 29(5):757–779, 2020

    2020

  5. [5]

    Burggraf and A

    L. Burggraf and A. Wesolek. personal communication, 2025. 26 PATRICK BENNETT, RYAN CUSHMAN, ANDRZEJ DUDEK, AND XAVIER P ´EREZ-GIM´ENEZ

    2025

  6. [6]

    Dubhashi and D

    D. Dubhashi and D. Ranjan. Balls and bins: A study in negative dependence.Random Structures & Algorithms, 13(2):99–124, 1998

    1998

  7. [7]

    Hajnal, L

    A. Hajnal, L. Lov´ asz, and V. T. S´ os, editors.Finite and infinite sets. Vol. I, II, volume 37 ofColloquia Mathematica Societatis J´ anos Bolyai. North-Holland Publishing Co., Amsterdam, 1984

    1984

  8. [8]

    P. E. Haxell. Packing and covering triangles in graphs.Discrete Math., 195(1-3):251–254, 1999

    1999

  9. [9]

    P. E. Haxell and V. R¨ odl. Integer and fractional packings in dense graphs.Combinatorica, 21(1):13–38, 2001

    2001

  10. [10]

    Janson, T

    S. Janson, T. L uczak, and A. Ruci´ nski.Random Graphs. Wiley Series in Discrete Mathematics and Optimization. Wiley, 2011

    2011

  11. [11]

    J. Kahn. A linear programming perspective on the Frankl-R¨ odl-Pippenger theorem.Random Structures Algorithms, 8(2):149–157, 1996

    1996

  12. [12]

    Kahn and J

    J. Kahn and J. Park. Tuza’s conjecture for random graphs.Random Structures Algorithms, 61(2):235– 249, 2022

    2022

  13. [13]

    D. Kershaw. Some extensions of W. Gautschi’s inequalities for the Gamma function.Mathematics of Computation, 41(164):607–611, 1983

    1983

  14. [14]

    Krivelevich

    M. Krivelevich. On a conjecture of Tuza about packing and covering of triangles.Discrete Math., 142(1- 3):281–286, 1995

    1995

  15. [15]

    Penrose.Random Geometric Graphs

    M. Penrose.Random Geometric Graphs. Oxford studies in probability. Oxford University Press, 2003

    2003

  16. [16]

    Z. Tuza. A conjecture on triangles of graphs.Graphs Combin., 6(4):373–380, 1990

    1990

  17. [17]

    R. Yuster. Dense graphs with a large triangle cover have a large triangle packing.Combin. Probab. Comput., 21(6):952–962, 2012. Department of Mathematics, Western Michigan University, Kalamazoo, MI, USA Email address:patrick.bennett@wmich.edu Department of Mathematics, University of Tennessee, Knoxville, Knoxville, TN, USA Email address:rcushma3@utk.edu D...

    2012