pith. sign in

arxiv: 2606.09518 · v1 · pith:H4LFR7PCnew · submitted 2026-06-08 · 🧮 math.CO

Strong counterexamples to a supersaturation question of Ma-Yuan

Wanfang Chen , Long-Tu Yuan This is my paper

Pith reviewed 2026-06-27 15:54 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C35
keywords supersaturationextremal graph theorybook graphscounterexamplesh_F functionpath graphs
0
0 comments X

The pith

For graphs H_t made from paths and books, h_{H_t}(n,1) is less than c(n,H_t) for infinitely many n.

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

Ma and Yuan asked whether h_F(n,1) equals c(n,F) for every graph F containing a cycle. The paper constructs for each t greater than or equal to 6 a graph H_t by replacing each edge of a t-vertex path with a 3t-page book on disjoint vertices. It proves that for these H_t the quantity h_{H_t}(n,1) is strictly less than c(n,H_t) for infinitely many n. The ratio of the two can also be made arbitrarily small by taking t large enough.

Core claim

For each integer t at least 6, the graph H_t formed from the t-vertex path by replacing each edge with a 3t-page book using disjoint page vertices satisfies h_{H_t}(n,1) < c(n,H_t) for infinitely many n, and the ratio h_{H_t}(n,1)/c(n,H_t) can be made arbitrarily small along those n as t grows.

What carries the argument

The graph H_t obtained from a t-vertex path by replacing each edge with a 3t-page book using disjoint page vertices.

If this is right

  • The equality h_F(n,1)=c(n,F) does not hold for all cycle-containing graphs F.
  • The supersaturation function can be strictly smaller than the one-edge extremal addition for some F.
  • The ratio can be driven to zero along subsequences of n by choosing larger t.

Where Pith is reading between the lines

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

  • The construction technique of replacing edges with books may apply to other supersaturation questions.
  • It is possible that the stability condition does not rescue the equality even for q=1.
  • One could test whether similar counterexamples exist when q is fixed but greater than 1.

Load-bearing premise

The explicit counting of copies of H_t in the n-vertex graphs with ex(n,H_t) plus one edge that are not the standard one-edge addition is lower than c(n,H_t) for infinitely many n.

What would settle it

Finding a specific n for t=6 where every graph with ex(n,H_t)+1 edges has at least as many H_t copies as the minimum over one-edge additions to extremal graphs.

read the original abstract

For a graph $F$, let $h_F(n,q)$ be the minimum number of copies of $F$ in an $n$-vertex graph with $\mathrm{ex}(n,F)+q$ edges, where $\mathrm{ex}(n,F)$ is the maximum number of edges in an $n$-vertex $F$-free graph. Let $c(n,F)$ be the minimum number of copies obtained by adding one edge to an extremal $F$-free graph. Mubayi's supersaturation conjecture predicts, under a stability hypothesis, that $h_F(n,q)\ge q\,c(n,F)$. Ma and Yuan recently constructed stable graph counterexamples for every fixed $q\ge4$; they asked whether the one-edge equality $h_F(n,1)=c(n,F)$ might still hold for every graph $F$ containing a cycle. We give a negative answer to their question. For each integer $t\ge6$, let $H_t$ be obtained from the $t$-vertex path by replacing each edge with a $3t$-page book, using disjoint page vertices for different path edges. Then $h_{H_t}(n,1)<c(n,H_t)$ for infinitely many values of $n$. Moreover, by taking $t$ large, the ratio $h_{H_t}(n,1)/c(n,H_t)$ can be made arbitrarily small along infinitely many values of $n$.

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 paper constructs, for each integer t ≥ 6, a graph H_t obtained from the t-vertex path P_t by replacing each edge with a 3t-page book using disjoint page vertices for different path edges. It proves that h_{H_t}(n,1) < c(n,H_t) for infinitely many n, and that the ratio h_{H_t}(n,1)/c(n,H_t) can be made arbitrarily small for sufficiently large t along those n.

Significance. If the counting arguments hold, the result supplies explicit, stable counterexamples to Ma-Yuan's question on whether the one-edge supersaturation equality h_F(n,1) = c(n,F) holds for every cycle-containing graph F. The construction further shows that the ratio can be driven arbitrarily close to zero, providing a quantitatively strong negative answer.

major comments (2)
  1. [Proof of Theorem 1 (or equivalent main result section)] The central claim that h_{H_t}(n,1) < c(n,H_t) rests on an exhaustive case analysis of how H_t-copies arise when one extra edge is added to an extremal graph. This analysis must distinguish the added edge lying inside a single book, between books attached to the same path vertex, or across different path edges; any missed multiplicity or overlap in the disjoint-page construction would invalidate the strict inequality for the arithmetic progression of n where the construction is applied.
  2. [Section establishing the ratio bound for large t] The argument that the ratio can be made arbitrarily small for large t requires explicit asymptotic comparison of the copy counts in the two quantities as t grows. The manuscript should supply the leading-term expressions (or at least the ratio bounds) that establish this limit, rather than leaving the dependence on t implicit in the construction.
minor comments (2)
  1. [Introduction] The notation h_F(n,q) and c(n,F) is introduced in the abstract but would benefit from a brief reminder of their definitions at the start of the introduction for readers unfamiliar with the supersaturation literature.
  2. [Construction section] Figure or diagram illustrating the book-replacement construction for small t (e.g., t=6) would clarify the disjoint-page condition and the path skeleton.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying points where the exposition can be strengthened. We address each major comment below. The core counting arguments rely on the disjoint-page construction, which we believe eliminates the overlaps raised; however, we agree that explicit leading-term expressions for the ratio will improve readability.

read point-by-point responses

  1. Referee: [Proof of Theorem 1 (or equivalent main result section)] The central claim that h_{H_t}(n,1) < c(n,H_t) rests on an exhaustive case analysis of how H_t-copies arise when one extra edge is added to an extremal graph. This analysis must distinguish the added edge lying inside a single book, between books attached to the same path vertex, or across different path edges; any missed multiplicity or overlap in the disjoint-page construction would invalidate the strict inequality for the arithmetic progression of n where the construction is applied.

    Authors: The case analysis in the proof of the main theorem already partitions the possible locations of the added edge into the three categories listed (intra-book, inter-book on the same path vertex, and across distinct path edges). Because page vertices are chosen disjoint across different path edges, no copy of H_t can use pages from more than one path edge; this eliminates cross-multiplicities. We have inserted a short clarifying paragraph immediately after the case breakdown that explicitly invokes the disjointness to rule out overlaps. We therefore maintain that the strict inequality holds, but the added paragraph makes the reasoning more transparent. revision: partial

  2. Referee: [Section establishing the ratio bound for large t] The argument that the ratio can be made arbitrarily small for large t requires explicit asymptotic comparison of the copy counts in the two quantities as t grows. The manuscript should supply the leading-term expressions (or at least the ratio bounds) that establish this limit, rather than leaving the dependence on t implicit in the construction.

    Authors: We agree that the dependence on t was left implicit. In the revised version we add a short subsection that derives the leading-term asymptotics: the number of H_t-copies in the extremal graph plus one edge is Θ(n^{t} t^{O(1)}), while the minimum over all graphs with ex(n,H_t)+1 edges is o(n^{t} t^{O(1)}) when t o∞ along the chosen arithmetic progression of n. The ratio is therefore bounded above by C/t for an absolute constant C, which tends to zero. These explicit bounds are now stated as a separate lemma. revision: yes

Circularity Check

0 steps flagged

Explicit construction and direct counting yield independent counterexamples

full rationale

The derivation defines H_t by an explicit replacement rule (path edges replaced by disjoint 3t-page books) and asserts a strict inequality h_{H_t}(n,1) < c(n,H_t) via combinatorial enumeration of H_t-copies. No parameter is fitted to a data subset and then re-predicted; no self-citation supplies a uniqueness theorem or ansatz that the present argument reduces to; the comparison of copy numbers is between independently defined quantities on the same n-vertex graphs. The result is therefore self-contained and does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the explicit construction of the family H_t together with standard graph-theoretic counting; no free parameters are introduced and the only invented object is H_t itself.

axioms (1)
  • standard math Standard definitions of graphs, subgraphs, copies of F, and the extremal function ex(n,F)
    These background notions are invoked without proof throughout the argument.
invented entities (1)
  • H_t no independent evidence
    purpose: Family of graphs serving as counterexamples to the one-edge supersaturation equality
    Defined by replacing each edge of a t-vertex path with a 3t-page book using disjoint page vertices; no external falsifiable evidence is supplied.

pith-pipeline@v0.9.1-grok · 5785 in / 1501 out tokens · 30198 ms · 2026-06-27T15:54:17.765337+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Strong counterexamples to Mubayi's supersaturation conjecture in every uniformity

    math.CO 2026-06 unverdicted novelty 7.0

    Constructs counterexamples to Mubayi's supersaturation conjecture showing the conjectured lower bound fails by arbitrary factors at q=1 for r-graphs of every uniformity.

Reference graph

Works this paper leans on

14 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    C. S. Edwards. A lower bound for the largest number of triangles with a common edge. Unpublished manuscript, 1975

    1975

  2. [2]

    P. Erd˝ os. Some theorems on graphs.Riveon Lematematika, 9:13–17, 1955

    1955

  3. [3]

    P. Erd˝ os. On a theorem of Rademacher–Tur´ an.Illinois J. Math., 6:122–127, 1962

    1962

  4. [4]

    Erd˝ os and T

    P. Erd˝ os and T. Gallai. On maximal paths and circuits of graphs.Acta Math. Acad. Sci. Hungar., 10:337–356, 1959

    1959

  5. [5]

    R. J. Faudree and R. H. Schelp. Path Ramsey numbers in multicolorings.J. Combin. Theory Ser. B, 19:150–160, 1975

    1975

  6. [6]

    Khadˇ ziivanov and V

    N. Khadˇ ziivanov and V. Nikiforov. Solution of a problem of P. Erd˝ os about the maximum number of triangles with a common edge in a graph.C. R. Acad. Bulgare Sci., 32:1315–1318, 1979

    1979

  7. [7]

    G. N. Kopylov. On maximal paths and cycles in a graph.Dokl. Akad. Nauk SSSR, 234:19–21, 1977

    1977

  8. [8]

    Lov´ asz and M

    L. Lov´ asz and M. Simonovits. On the number of complete subgraphs of a graph. InProceedings of the Fifth British Combinatorial Conference (University of Aberdeen, Aberdeen, 1975), volume XV of Congr. Numer., pages 431–441, Winnipeg, 1976. Utilitas Mathematica

    1975

  9. [9]

    Lov´ asz and M

    L. Lov´ asz and M. Simonovits. On the number of complete subgraphs of a graph. II. InStudies in Pure Mathematics, pages 459–495. Birkh¨ auser, Basel, 1983

    1983

  10. [10]

    Ma and L.-T

    J. Ma and L.-T. Yuan. Supersaturation beyond color-critical graphs.Combinatorica, 45(2):Paper No. 18, 40, 2025

    2025

  11. [11]

    L. Miao, R. Liu, and E. R. van Dam. Tur´ an number of books in non-bipartite graphs.J. Graph Theory, 2026. Published online 14 April 2026, DOI: 10.1002/jgt.70039

    work page doi:10.1002/jgt.70039 2026

  12. [12]

    D. Mubayi. Counting substructures I: color critical graphs.Adv. Math., 225(5):2731–2740, 2010

    2010

  13. [13]

    D. Mubayi. Counting substructures II: hypergraphs.Combinatorica, 33:591–612, 2013

    2013

  14. [14]

    Pikhurko and Z

    O. Pikhurko and Z. B. Yilma. Supersaturation problem for color-critical graphs.J. Combin. Theory Ser. B, 123:148–185, 2017. 7

    2017