A single 3-graph with infinite stability number
Pith reviewed 2026-05-22 05:18 UTC · model grok-4.3
The pith
A single explicit 3-graph has infinite stability number, so no finite list of structures approximates all its near-extremal constructions.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors construct a simple explicit 3-graph whose stability number is infinite. This establishes that even a single forbidden 3-graph can require infinitely many distinct structures to approximate all large near-extremal constructions that avoid it, extending the infinite-stability result from finite families to the single-forbidden case.
What carries the argument
The explicit 3-graph whose construction forces any approximating family of structures to be infinite.
If this is right
- Infinite stability extends from finite forbidden families to single forbidden 3-graphs.
- No finite collection of model structures can describe all large constructions avoiding the constructed 3-graph.
- The single-3-graph setting admits both infinite stability and exponentially many exact extremal constructions.
Where Pith is reading between the lines
- Similar explicit constructions may exist for 4-graphs or higher-uniformity hypergraphs.
- The result suggests examining whether infinite stability appears in other forbidden-subgraph problems outside 3-graphs.
- One could test the construction computationally on small vertex counts to check for early signs of requiring many structures.
Load-bearing premise
The explicit 3-graph defined in the paper indeed has infinite stability number, meaning the proof that no finite list of structures approximates all its near-extremal constructions holds without gaps.
What would settle it
Exhibiting a finite list of structures that approximates every near-extremal construction avoiding the given 3-graph would falsify the claim.
read the original abstract
The stability number of a forbidden family measures how many different structures are needed to approximate all near-extremal constructions avoiding it. An infinite stability number means that no finite list of structures suffices. We construct a simple explicit $3$-graph whose stability number is infinite. This extends the infinite-stability phenomenon for finite forbidden families, established by Hou--Li--Liu--Mubayi--Zhang, to the single-forbidden setting, and further develops the single-$3$-graph direction of Balogh--Clemen--Luo, in which exponentially many exact extremal constructions coexist with stability.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript constructs a single explicit 3-uniform hypergraph H whose stability number is infinite. This means that for the forbidden family consisting of this one 3-graph, no finite collection of approximating structures suffices to capture all near-extremal H-free constructions. The result extends the infinite-stability phenomenon previously shown for finite forbidden families (Hou--Li--Liu--Mubayi--Zhang) to the single-forbidden 3-graph case, while relating to the coexistence of exponentially many extremal constructions in Balogh--Clemen--Luo.
Significance. If the explicit construction and its proof hold, the result is significant for extremal hypergraph theory: it demonstrates that infinite stability can occur even when only one 3-graph is forbidden, rather than requiring a finite family. The explicitness of the construction is a positive feature, as it allows direct verification and avoids reliance on non-constructive arguments.
minor comments (2)
- [Introduction] The introduction would benefit from a short high-level sketch of the 3-graph construction (e.g., its vertex set and edge rule) before the formal definition, to help readers follow the subsequent stability argument.
- [Section 2] Notation for the approximating structures and the stability number could be made more uniform across sections; currently the same symbol appears to be reused for both the hypergraph and a related parameter.
Simulated Author's Rebuttal
We thank the referee for the positive assessment of our manuscript, the recognition of its significance in extending infinite stability to the single-forbidden 3-graph setting, and the recommendation for minor revision. As no specific major comments were raised in the report, we have no points requiring detailed rebuttal or clarification at this stage.
Circularity Check
No significant circularity; explicit construction stands independently
full rationale
The paper's core contribution is an explicit construction of a single 3-graph H together with a direct proof that its stability number is infinite. This is presented as a combinatorial argument establishing the property for the defined object, without any reduction to fitted parameters, self-referential definitions, or load-bearing self-citations that would make the result equivalent to its inputs by construction. Prior results on finite forbidden families are cited for context and extension, but the new single-graph case is developed separately and remains externally verifiable through the explicit definition and stability analysis.
Axiom & Free-Parameter Ledger
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We construct a simple explicit 3-graph F = K−4 × F⋆ … rank-two cut template R× … dist(Gα(n), Gβ(n)) = Ωα,β(n³) … ξ(F)=∞
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
The cut template R(U,C) … cut-rank := dim F2 ⟨C⟩ … rank(C)≤2 implies F↛R(U,C)
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
- [1]
-
[2]
J. Balogh and D. Mubayi. Almost all triangle-free triple systems are tripartite.Combinatorica, 32(2):143–169, 2012
work page 2012
- [3]
-
[4]
W. G. Brown. On an open problem of Paul Turán concerning3-graphs. InStudies in pure mathematics, pages 91–93. Birkhäuser, Basel, 1983
work page 1983
-
[5]
W. G. Brown and M. Simonovits. Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures.Discrete Math., 48(2-3):147–162, 1984
work page 1984
-
[6]
W. Dörfler and D. A. Waller. A category-theoretical approach to hypergraphs.Arch. Math. (Basel), 34(2):185–192, 1980
work page 1980
-
[7]
P. Erdős and M. Simonovits. A limit theorem in graph theory.Studia Sci. Math. Hungar., 1:51–57, 1966
work page 1966
-
[8]
P. Erdős and A. H. Stone. On the structure of linear graphs.Bull. Amer. Math. Soc., 52:1087–1091, 1946
work page 1946
-
[9]
P. Frankl and Z. Füredi. A new generalization of the Erdős–Ko–Rado theorem.Combinatorica, 3(3-4):341–349, 1983
work page 1983
- [10]
-
[11]
M. Hellmuth, L. Ostermeier, and P. F. Stadler. A survey on hypergraph products.Math. Comput. Sci., 6(1):1–32, 2012
work page 2012
-
[12]
J. Hou, H. Li, X. Liu, D. Mubayi, and Y. Zhang. Hypergraphs with infinitely many extremal constructions.Discrete Anal., 2023. Paper No. 18, 34 pp. 10
work page 2023
-
[13]
P. Keevash. Hypergraph Turán problems. InSurveys in combinatorics 2011, volume 392 ofLondon Math. Soc. Lecture Note Ser., pages 83–139. Cambridge Univ. Press, Cambridge, 2011
work page 2011
-
[14]
P. Keevash and D. Mubayi. Stability theorems for cancellative hypergraphs.J. Combin. Theory Ser. B, 92(1):163–175, 2004
work page 2004
-
[15]
A. V. Kostochka. A class of constructions for Turán’s(3,4)-problem.Combinatorica, 2(2):187–192, 1982
work page 1982
- [16]
- [17]
- [18]
-
[19]
X. Liu, D. Mubayi, and C. Reiher. A unified approach to hypergraph stability.J. Combin. Theory Ser. B, 158(part 2):36–62, 2023
work page 2023
-
[20]
X. Liu, D. Mubayi, and C. Reiher. Hypergraphs with many extremal configurations.Israel J. Math., 271(1):1–38, 2026
work page 2026
- [21]
-
[22]
D. Mubayi. Structure and stability of triangle-free set systems.Trans. Amer. Math. Soc., 359(1):275–291, 2007
work page 2007
- [23]
-
[24]
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- London, 1968
work page 1966
-
[25]
P. Turán. Eine Extremalaufgabe aus der Graphentheorie.Mat. Fiz. Lapok, 48:436–452, 1941
work page 1941
-
[26]
K. Čulík. Zur Theorie der Graphen.Časopis Pěst. Mat., 83:133–155, 1958
work page 1958
-
[27]
P. M. Weichsel. The Kronecker product of graphs.Proc. Amer. Math. Soc., 13:47–52, 1962
work page 1962
- [28]
-
[29]
A. A. Zykov. On some properties of linear complexes.Mat. Sbornik N.S., 24(66):163–188, 1949. 11
work page 1949
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.