pith. sign in

arxiv: 2606.26735 · v1 · pith:OWN25KCSnew · submitted 2026-06-25 · 🧮 math.CO

Strong counterexamples to Mubayi's supersaturation conjecture in every uniformity

Heng Li , Hong Liu , Xizhi Liu , Jing Wang This is my paper

Pith reviewed 2026-06-26 04:25 UTC · model grok-4.3

classification 🧮 math.CO
keywords supersaturationMubayi's conjecturehypergraphsextremal graph theorycounterexamplesstabilityuniform hypergraphsTurán problem
0
0 comments X

The pith

For every uniformity r and factor K, there exist stable non-r-partite r-graphs where adding q edges creates at most K^{-1} q times the minimum expected copies of the forbidden subgraph.

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

The paper establishes that Mubayi's conjecture fails in a strong way across all uniformities. The authors produce, for any r at least 2 and any K greater than 1, a stable non-r-partite r-graph F such that graphs with ex(n,F) plus q edges can contain far fewer than the conjectured q c(n,F) copies of F, for q ranging up to a linear fraction of n. This means the lower bound on supersaturation can be violated even by a single extra edge and by an arbitrarily large constant factor. A sympathetic reader cares because the result shows that the transition from extremal to supersaturated hypergraphs can behave much more weakly than previously expected in every uniformity.

Core claim

The authors construct, for every r ≥ 2 and every K > 1, a stable non-r-partite r-graph F with the following property: for all sufficiently large n and every integer q with 1 ≤ q ≤ δn, there is an n-vertex r-graph with ex(n,F) + q edges and at most K^{-1} q c(n,F) copies of F. Thus Mubayi's conjectured lower bound can already fail at q=1, and the failure can be by an arbitrarily large constant factor in every uniformity.

What carries the argument

Stable non-r-partite r-graphs F whose extremal examples permit constructions that add multiple edges while producing sublinear numbers of new F-copies relative to the single-edge minimum c(n,F).

If this is right

  • Mubayi's conjectured lower bound on the number of copies fails already when q equals 1.
  • The actual minimum can be smaller than the conjectured value by any fixed positive constant factor.
  • Such counterexamples exist for every uniformity r ≥ 2.
  • The separation between the conjectured bound and the actual supersaturation holds for q up to a positive fraction of the number of vertices.

Where Pith is reading between the lines

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

  • Stability of the forbidden subgraph may not be sufficient to guarantee the conjectured supersaturation rate in hypergraph extremal problems.
  • The constructions suggest that the correct supersaturation threshold could depend on additional structural properties beyond stability and non-partiteness.
  • Similar weak-supersaturation behavior might appear in other extremal problems once the right family of forbidden subgraphs is identified.

Load-bearing premise

There exist stable non-r-partite r-graphs for each r and K whose extremal constructions allow adding several edges while creating proportionally fewer copies than the one-edge supersaturation predicts.

What would settle it

A proof that for some fixed r ≥ 2 and K > 1, every stable non-r-partite r-graph F satisfies at least q c(n,F) copies of F in every n-vertex r-graph with ex(n,F) + q edges when 1 ≤ q ≤ δn.

Figures

Figures reproduced from arXiv: 2606.26735 by Heng Li, Hong Liu, Jing Wang, Xizhi Liu.

Figure 2.1
Figure 2.1. Figure 2.1: The fan F3 and the semi-blowup fan F3,3. In the drawing of F3,3, the dashed region denotes the complete tripartite 3-graph K (3) 3,3,3 on the transversal vertices, whose three partite classes are indicated by the three colors. We first recall the definition of the fan that appears in the Mubayi–Pikhurko generalization of Mantel’s theorem to hypergraphs [18]. Definition 2.1. For r ≥ 2, the fan Fr is the r… view at source ↗
read the original abstract

The classical supersaturation problem, originating in classical results of Rademacher and Erd\H{o}s on complete graphs, asks for the minimum number of copies of an $r$-graph $\mathcal{F}$ in an $n$-vertex $r$-graph with $\ex(n,\mathcal{F})+q$ edges. Mubayi conjectured that, for every stable non-$r$-partite $r$-graph $\mathcal{F}$, this minimum is at least $q c(n,\mathcal{F})$, where $c(n,\mathcal{F})$ is the minimum number of copies created by adding one edge to the $n$-vertex extremal $\mathcal{F}$-free $r$-graph. Ma and Yuan recently constructed infinitely many graph counterexamples, with arbitrary chromatic number at least four. We construct, for every $r\ge 2$ and every $K>1$, a stable non-$r$-partite $r$-graph $\mathcal{F}$ with the following property: for all sufficiently large $n$ and every integer $q$ with $1\le q\le \delta n$, there is an $n$-vertex $r$-graph with $\ex(n,\mathcal{F})+q$ edges and at most $K^{-1}q c(n,\mathcal{F})$ copies of $\mathcal{F}$. Thus Mubayi's conjectured lower bound can already fail at $q=1$, and the failure can be by an arbitrarily large constant factor in every uniformi

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

0 major / 3 minor

Summary. The manuscript constructs, for every r ≥ 2 and every K > 1, a stable non-r-partite r-graph F via an explicit recursive procedure. For this F, the supersaturation function satisfies that for all sufficiently large n and all 1 ≤ q ≤ δn there exists an n-vertex r-graph with ex(n,F) + q edges containing at most K^{-1} q c(n,F) copies of F. This yields strong counterexamples to Mubayi's conjecture that already fail the conjectured lower bound by an arbitrary constant factor at q = 1, in every uniformity.

Significance. If the constructions and counting arguments are correct, the result supplies the first strong counterexamples in every uniformity r, extending the graph (r=2) counterexamples of Ma and Yuan to arbitrary r while achieving arbitrarily large constant-factor violations. The explicit recursive constructions, direct verification of stability and non-r-partiteness from the definition, and the counting argument that tracks only new copies created by the added edges are concrete strengths that make the counterexamples falsifiable and checkable.

minor comments (3)
  1. The abstract sentence is truncated at 'in every uniformi'; the corresponding statement in the introduction should be checked for completeness.
  2. Notation for the stability parameter δ and the constant K should be introduced with explicit dependence on F in §2 before the main theorem statement.
  3. The recursive construction of F in §3 would benefit from a small illustrative example for r=2 and K=2 to aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report, detailed summary of our results, and recommendation to accept the manuscript. We are gratified that the referee views the explicit recursive constructions, stability verification, and counting arguments as concrete strengths that render the counterexamples falsifiable and checkable.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper supplies explicit recursive constructions of stable non-r-partite r-graphs F (for arbitrary r and K) whose Turán graphs and one-edge supersaturation counts are controlled so that adding q edges produces at most K^{-1} q c(n,F) copies. Stability and non-partiteness are verified directly from the definition, and the supersaturation bound is obtained by a counting argument that tracks only the new copies created by the added edges. No hidden assumption about boundedness, asymptotic regime, or uniformity is required beyond what is stated. The derivation is self-contained; it does not reduce any claimed prediction or uniqueness result to a fitted input, self-citation chain, or definitional equivalence.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review; no specific free parameters, axioms beyond standard definitions, or invented entities are described.

axioms (1)
  • standard math Standard definitions of ex(n,F) and c(n,F) from extremal graph theory.
    The claim is stated in terms of these classical quantities.

pith-pipeline@v0.9.1-grok · 5797 in / 1119 out tokens · 47494 ms · 2026-06-26T04:25:05.390359+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

23 extracted references · 2 linked inside Pith

  1. [1]

    Chen and L.-T

    W. Chen and L.-T. Yuan. Strong counterexamples to a supersaturation question of Ma–Yuan. arXiv preprint arXiv:2606.09518, 2026

    Pith/arXiv arXiv 2026

  2. [2]

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

    1955

  3. [3]

    P. Erdős. On a theorem of Rademacher–Turán.Illinois J. Math., 6:122–127, 1962

    1962

  4. [4]

    P. Erdős. On extremal problems of graphs and generalized graphs.Israel J. Math., 2:183–190, 1964

    1964

  5. [5]

    Erdős and T

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

    1959

  6. [6]

    Erdős and M

    P. Erdős and M. Simonovits. A limit theorem in graph theory.Studia Sci. Math. Hungar., 1:51–57, 1966

    1966

  7. [7]

    Erdős and M

    P. Erdős and M. Simonovits. Supersaturated graphs and hypergraphs.Combinatorica, 3:181–192, 1983

    1983

  8. [8]

    W. T. Gowers. Hypergraph regularity and the multidimensional Szemerédi theorem.Ann. of Math., 166:897–946, 2007. 29

    2007

  9. [9]

    J. Hou, H. Li, X. Liu, L.-T. Yuan, and Y. Zhang. A step towards a general density Corrádi–Hajnal theorem.Canad. J. Math., pages 1–36, 2025

    2025

  10. [10]

    Komlós and M

    J. Komlós and M. Simonovits. Szemerédi’s regularity lemma and its applications in graph theory. InCombinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pages 295–352. János Bolyai Math. Soc., Budapest, 1996

    1993

  11. [11]

    Lovász and M

    L. Lovász and M. Simonovits. On the number of complete subgraphs of a graph. In Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), Congr. Numer. 15, pages 431–441. Utilitas Math., Winnipeg, MB, 1976

    1975

  12. [12]

    Lovász and M

    L. Lovász and M. Simonovits. On the number of complete subgraphs of a graph II. In Studies in Pure Mathematics, pages 459–495. Birkhäuser, Basel, 1983

    1983

  13. [13]

    Ma and L.-T

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

    2025

  14. [14]

    W. Mantel. Problem 28.Wisk. Opgaven, 10:60–61, 1907

    1907

  15. [15]

    D. Mubayi. Counting substructures III: quadruple systems. arXiv preprint arXiv:0905.4735, 2009

    Pith/arXiv arXiv 2009

  16. [16]

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

    2010

  17. [17]

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

    2013

  18. [18]

    Mubayi and O

    D. Mubayi and O. Pikhurko. A new generalization of Mantel’s theorem tok-graphs.J. Combin. Theory Ser. B, 97(4):669–678, 2007

    2007

  19. [19]

    Nagle, V

    B. Nagle, V. Rödl, and M. Schacht. The counting lemma for regulark-uniform hypergraphs. Random Struct. Alg., 28(2):113–179, 2006

    2006

  20. [20]

    Rödl and J

    V. Rödl and J. Skokan. Applications of the regularity lemma for uniform hypergraphs. Random Struct. Alg., 28(2):180–194, 2006

    2006

  21. [21]

    Simonovits

    M. Simonovits. A method for solving extremal problems in graph theory, stability problems. InTheory of Graphs (Proc. Colloq., Tihany, 1966), pages 279–319. Academic Press, New York, 1968

    1966

  22. [22]

    T. Tao. A variant of the hypergraph removal lemma.J. Combin. Theory Ser. A, 113(7):1257– 1280, 2006

    2006

  23. [23]

    P. Turán. On an extremal problem in graph theory.Mat. Fiz. Lapok, 48:436–452, 1941. 30

    1941