pith. sign in

arxiv: 2606.06298 · v1 · pith:KKZZT2SEnew · submitted 2026-06-04 · 🧮 math.CO

The density of k-cacti via excluding minors

Licheng Zhang , Yuanqiu Huang This is my paper

Pith reviewed 2026-06-28 00:20 UTC · model grok-4.3

classification 🧮 math.CO
keywords k-cactusminor-closed classesextremal graph theorycycle boundsgraph minorsdensity bounds
0
0 comments X

The pith

A k-cactus excludes a large complete minor and therefore has at most O((log k / sqrt(log log k)) n) edges.

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

The paper establishes that any graph in which each edge belongs to at most k cycles must exclude a large complete graph as a minor. This property shows that the family of all k-cacti is closed under taking minors. The authors then apply known results on the maximum density of minor-closed families to conclude that every n-vertex k-cactus has O((log k / sqrt(log log k)) n) edges for all sufficiently large k. A separate construction demonstrates that the same order is tight up to a multiplicative factor of sqrt(log log k).

Core claim

Every n-vertex k-cactus has O((log k / sqrt(log log k)) n) edges for sufficiently large k, obtained by proving that the bounded number of cycles per edge forces the exclusion of a large complete minor and therefore places k-cacti inside a minor-closed class whose extremal density is already known.

What carries the argument

The implication that an upper bound of k on the number of cycles through any edge forces the graph to exclude a sufficiently large complete minor, which establishes that the class of k-cacti is minor-closed.

If this is right

  • The maximum number of edges in any n-vertex k-cactus is O((log k / sqrt(log log k)) n) for large k.
  • The class of k-cacti is minor-closed.
  • A construction achieves a matching lower bound up to a factor of sqrt(log log k).
  • The same density bound applies uniformly to all sufficiently large k.

Where Pith is reading between the lines

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

  • The same cycle-to-minor argument may extend to other graph families defined by local cycle restrictions.
  • A more precise quantification of the excluded minor size could tighten the leading constant in the density bound.
  • The result connects k-cacti to the broader theory of sparse minor-closed classes such as planar graphs or bounded-treewidth graphs.

Load-bearing premise

A bound on the number of cycles through each edge forces every k-cactus to exclude a large complete minor.

What would settle it

An n-vertex k-cactus containing more than C (log k / sqrt(log log k)) n edges for large k, or a k-cactus that contains a complete minor larger than the size implied by the cycle bound, would falsify the claim.

Figures

Figures reproduced from arXiv: 2606.06298 by Licheng Zhang, Yuanqiu Huang.

Figure 1
Figure 1. Figure 1: Lifting a cycle of 𝐻 to a cycle of 𝐺 through a minor model. 4 Proofs of Theorem 1.1 and Corollary 1.2 Lemma 4.1. If 𝐺 contains 𝐾𝑟 as a minor, then some edge of 𝐺 is contained in at least ⌊𝑒(𝑟 − 2)!⌋ − 1 cycles. Proof. By Lemma 1.7, every edge of 𝐾𝑟 lies in exactly ⌊𝑒(𝑟 − 2)!⌋ − 1 cycles. Fix one such edge ℎ and apply the cycle-lifting Proposition 3.1 with 𝐻 = 𝐾𝑟 : there is an edge bℎ ∈ 𝐸(𝐺) with 𝑐𝐺 (bℎ) ≥ … view at source ↗
read the original abstract

A \emph{$k$-cactus} generalizes forests and cacti by allowing each edge to lie on at most $k$ cycles. The maximum number of edges is classical for forests and cacti, but for $k$-cacti was known only for $k\le 4$. In this note we treat general $k$. The key idea is that bounding the cycles through each edge forces a $k$-cactus to exclude a large complete minor; in particular, the class of $k$-cacti is minor-closed. From this we prove that every $n$-vertex $k$-cactus has $O\!\left(\frac{\log k}{\sqrt{\log\log k}}\,n\right)$ edges for all sufficiently large $k$, and a construction shows this is optimal up to a factor of $\sqrt{\log\log k}$.

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

1 major / 0 minor

Summary. The paper defines a k-cactus as a graph in which every edge lies on at most k cycles. It asserts that this class is minor-closed (because the per-edge cycle bound forces exclusion of large complete minors) and therefore, by the known extremal function for K_r-minor-free graphs, every n-vertex k-cactus has O((log k / sqrt(log log k)) n) edges for all sufficiently large k. A construction is given showing that the bound is optimal up to a sqrt(log log k) factor.

Significance. If the minor-closed claim is established, the result supplies the first general upper bound on the density of k-cacti for arbitrary k, extending the classical cases k=0,1 and linking the problem to the extremal theory of minor-closed families. The explicit construction achieving the matching lower bound (up to the stated factor) is a concrete strength.

major comments (1)
  1. [Abstract] Abstract (and the central argument): the reduction to the O(r sqrt(log r) n) bound for K_r-minor-free graphs requires that the class of k-cacti is minor-closed. While the manuscript correctly notes that edge/vertex deletion cannot increase the number of cycles through any edge, no argument, lemma, or verification is supplied showing that edge contraction preserves the property (i.e., that identifying vertices cannot create additional cycles through a remaining edge f and push its cycle count above k). This step is load-bearing for the entire density claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the missing verification that k-cacti are closed under contraction. We agree that the current manuscript only treats deletions explicitly and will add a complete argument for the minor-closed property.

read point-by-point responses

  1. Referee: [Abstract] Abstract (and the central argument): the reduction to the O(r sqrt(log r) n) bound for K_r-minor-free graphs requires that the class of k-cacti is minor-closed. While the manuscript correctly notes that edge/vertex deletion cannot increase the number of cycles through any edge, no argument, lemma, or verification is supplied showing that edge contraction preserves the property (i.e., that identifying vertices cannot create additional cycles through a remaining edge f and push its cycle count above k). This step is load-bearing for the entire density claim.

    Authors: We acknowledge the gap: the manuscript notes the effect of deletions but supplies no separate argument or lemma for contractions. The property is nevertheless preserved. Any cycle through a remaining edge f in a contraction of G corresponds to (the image of) a cycle through f in G itself, since the contraction homomorphism maps closed walks to closed walks and cycles to cycles. Hence the number of cycles through f cannot increase. We will insert a short new lemma (with proof) establishing that the class of k-cacti is minor-closed; the revised manuscript will therefore justify the appeal to the extremal function for K_r-minor-free graphs. revision: yes

Circularity Check

0 steps flagged

No significant circularity; external theorems invoked as independent input

full rationale

The derivation defines k-cacti via the per-edge cycle bound, asserts that this forces exclusion of large complete minors (hence minor-closed), and invokes the known O(r sqrt(log r) n) edge bound for K_r-minor-free graphs to obtain the stated density. No self-citation chain, no parameter fitted to a subset then renamed as prediction, no ansatz smuggled via prior work, and no definitional loop appear. The minor-closed claim is presented as a direct consequence of the cycle bound rather than presupposing the target density result. Reliance on standard external minor-density theorems constitutes normal use of independent benchmarks, not circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The argument rests on the minor-closed property of k-cacti together with known extremal functions for minor-closed families; no free parameters or new entities are introduced in the abstract.

axioms (2)
  • domain assumption The class of k-cacti is minor-closed.
    Explicitly stated as the key idea in the abstract.
  • standard math Standard density bounds for minor-closed graph classes apply directly.
    Used to obtain the O((log k / sqrt(log log k)) n) upper bound.

pith-pipeline@v0.9.1-grok · 5669 in / 1188 out tokens · 25470 ms · 2026-06-28T00:20:27.264147+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

13 extracted references · 9 canonical work pages

  1. [1]

    Diestel,Graph theory, 6th ed., Graduate Texts in Mathematics, vol

    R. Diestel,Graph theory, 6th ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, [2025]©2025. MR4874150

    2025

  2. [2]

    El-Mallah and C

    E. El-Mallah and C. J. Colbourn,The complexity of some edge deletion problems, IEEE Transactions on Circuits and Systems35(1988), no. 3, 354–362, DOI 10.1109/31.1748

    work page doi:10.1109/31.1748 1988

  3. [3]

    Geniet and U

    C. Geniet and U. Giocanti,Basis number of graphs excluding minors, posted on 2026, DOI 10.48550/arXiv.2601.05195, available at2601.05195

    work page doi:10.48550/arxiv.2601.05195 2026

  4. [4]

    A. V. Kostochka,Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica4 (1984), no. 4, 307–316, DOI 10.1007/BF02579141. MR779891

    work page doi:10.1007/bf02579141 1984

  5. [5]

    Mac Lane,A structural characterization of planar combinatorial graphs, Duke Math

    S. Mac Lane,A structural characterization of planar combinatorial graphs, Duke Math. J.3(1937), no. 3, 460–472, DOI 10.1215/S0012-7094-37-00336-3. MR1546002

    work page doi:10.1215/s0012-7094-37-00336-3 1937

  6. [6]

    Mader,Homomorphiesätze für Graphen, Math

    W. Mader,Homomorphiesätze für Graphen, Math. Ann.178(1968), 154–168, DOI 10.1007/BF01350657 (German). MR0229550

    work page doi:10.1007/bf01350657 1968

  7. [7]

    Thomason,An extremal function for contractions of graphs, Math

    A. Thomason,An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc.95(1984), no. 2, 261–265, DOI 10.1017/S0305004100061521. MR735367

    work page doi:10.1017/s0305004100061521 1984

  8. [8]

    MR1814910

    A.Thomason,Theextremalfunctionforcompleteminors,J.Combin.TheorySer.B81(2001),no.2,318–338, DOI 10.1006/jctb.2000.2013. MR1814910

    work page doi:10.1006/jctb.2000.2013 2001

  9. [9]

    MR0332580

    S.Toida,PropertiesofaEulergraph,J.FranklinInst.295(1973),343–345,DOI10.1016/0016-0032(73)90046- X. MR0332580

    1973

  10. [10]

    V.A.Voblyi,EnumerationoflabeledEulerian 3-cacti,J.Math.Sci.293(2025),673–677,DOI10.1007/s10958- 025-08041-3

    2025

  11. [11]

    D. B. West,Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, NJ, 2001. MR1367739

    2001

  12. [12]

    Z. Wu, H. Chen, and J. Li,Maximizing the spectral radius of generalized cactus graphs, RAIRO Oper. Res.60 (2026), no. 3, 1407–1418, DOI 10.1051/ro/2026035

    work page doi:10.1051/ro/2026035 2026

  13. [13]

    Zhang and Y

    L. Zhang and Y. Huang,On the sizes of generalized cactus graphs, Discrete Appl. Math.348(2024), 184–191, DOI 10.1016/j.dam.2024.01.043. MR4700794 9

    work page doi:10.1016/j.dam.2024.01.043 2024