Hypergraph Tur\'an problem of the generalized triangle with bounded matching number

Jian Wang; Weihua Yang; Wenbin Wang

REVIEW 2 major objections 3 minor 17 references

Hypergraph Tur\'an problem of the generalized triangle with bounded matching number

T0 review · 2 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper determines the exact Turán number of the generalized triangle $F_5$ among 3-graphs with bounded matching number, and proves a 2-colored Mantel theorem as the key tool.

desk verdict New result and a nice 2-colored Mantel lemma, but the main upper bound for s≥3 currently has a load-bearing algebraic gap in Case 2 of Theorem 1.6 that needs fixing. read the letter →

arxiv 2507.04579 v2 pith:IH6B33DU submitted 2025-07-06 math.CO

Jian Wang , Wenbin Wang , Weihua Yang This is my paper · ORCID

classification math.CO MSC 05C3505C6505D05

keywords TuránnumbergeneralizedtriangleF5-freehypergraphmatching2-coloredManteltheoremextremallinkgraphproblem

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper determines the exact maximum number of edges in a 3-uniform hypergraph on $n$ vertices that contains no copy of the generalized triangle $F_5$ and no matching of size $s+1$. For $n \geq 30(s+1)$, the maximum is $\binom{n-1}{2}$ when $s=1,2$, attained only by the full star at one vertex, and $s\lfloor (n-s)^2/4 \rfloor$ when $s \geq 3$, attained only by the complete 3-partite hypergraph $H_3(n,s)$ with part sizes $s$, $\lfloor (n-s)/2 \rfloor$, and $\lceil (n-s)/2 \rceil$. The proof rests on a new 2-colored version of Mantel's theorem: $p$ graphs on the same $n$ vertices with no triangle colored with two edges of one color and one of another have at most $p\lfloor n^2/4 \rfloor$ edges in total. This matters because $F_5$ has chromatic number 2 yet positive Turán density, so the bounded-matching problem is not covered by the known result for hypergraphs of chromatic number greater than 2.

What carries the argument

The central objects are the generalized triangle $F_5$, the 3-graph on five vertices with edges $abc, abd, cde$, and the extremal candidate $H_3(n,s)$, the complete 3-partite 3-graph with part sizes $s$, $\lfloor (n-s)/2 \rfloor$, and $\lceil (n-s)/2 \rceil$. The main tool is the 2-colored Mantel theorem (Theorem 1.8), proved by induction on $n$ via a degree-sum inequality and an equality analysis. The $F_5$-free condition makes the link graphs $L(v,\bar S)$ for $v$ in a selected $s$-set jointly 2-colored triangle-free, so Theorem 1.8 bounds their total contribution; its equality case forces all those links to be the same balanced complete bipartite graph, which is what singles out $H_3(n,s)$. Lemma 3.3 is the structural reduction that selects the set $S$ and decomposes the edge count into link contributions and small error terms.

What would settle it

Substitute $s=3$, $n=120$, and $i=1$ into the displayed inequality in Case 2 of Theorem 1.6's proof: the left-hand side contains $\tfrac{1}{2}s(s-1)n=360$ while the printed right-hand side uses $s(s-1)=6$, so the claimed inequality is false ($-2222.25$ is not at most $-2575.25$); this one substitution refutes the proof step, so the theorem's upper bound is not proved by the argument as written unless the step is corrected.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.6: for $n \geq 30(s+1)$, every $F_5$-free 3-graph with matching number at most $s$ has at most $\binom{n-1}{2}$ edges when $s=1,2$ and at most $s\lfloor (n-s)^2/4 \rfloor$ edges when $s \geq 3$, with equality only for the full star in the first case and only for $H_3(n,s)$ in the second. The engine is Theorem 1.8, the 2-colored Mantel theorem: if $G_1,\ldots,G_p$ are graphs on a common $n$-set and no triangle uses two edges of one color and a third edge of another color, then $\sum_i e(G_i) \leq p\lfloor n^2/4 \rfloor$, and equality forces $G_1=\cdots=G_p=K_{\lfloor n/2 \rfloor,\lceil n/2 \rceil}$. Applying this to the link graphs of vertices outside a carefully chosen $s$-set bounds the total edge count and, through the equality case, identifies the extremal hypergraph.

Load-bearing premise

The entire $s \geq 3$ case depends on one algebraic inequality in Case 2 of the proof of Theorem 1.6; as printed, it replaces a term proportional to $n$ by a constant, and if that step cannot be repaired the upper bound is not established.

Editorial extensions

If this is right

For every admissible $n$ and $s \geq 3$, the construction from the ordinary $F_5$ Turán problem, the complete 3-partite hypergraph $H_3(n,s)$, is the unique maximizer once the matching number is capped at $s$.
The 2-colored Mantel theorem extends the classical Mantel theorem: taking all $p$ graphs identical recovers Mantel's bound, so the new theorem is a genuine common generalization.
Corollary 1.9 is immediate: if $G_1,\ldots,G_p$ are pairwise 2-colored triangle-free on the same $n$ vertices, then $\prod_i e(G_i) \leq \lfloor n^2/4 \rfloor^p$, with equality only in the balanced bipartite case.
The result adds $F_5$ to the small family of forbidden hypergraphs with chromatic number 2 and positive Turán density for which the bounded-matching Turán number is known exactly.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same scheme—select an $s$-set, pass to link graphs, and apply a colored Mantel bound—should transfer to other 3-graphs whose forbidden configurations make link graphs colored-triangle-free; a natural test case is the analogue of $F_5$ for other 2-chromatic, positive-density hypergraphs.
The $n \geq 30(s+1)$ hypothesis is probably larger than needed; the authors' Conjecture 5.1 asks for $n \geq 3(s+1)$, and exhaustive search for small pairs such as $s=3$ and $n=12,\ldots,30$ could test that range before a full proof.
A stability version of Theorem 1.8—near-equality forcing each graph to be close to the same balanced complete bipartite graph—would turn the uniqueness argument into a stability theorem for $H_3(n,s)$, with consequences for approximate counting of extremal hypergraphs.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Three things to know up front. The main result is genuinely new: ex_3(n,{F5,M^3_{s+1}}) = binom(n−1,2) for s=1,2 and s floor((n−s)^2/4) for s≥3 when n≥30(s+1), with the expected unique extremal hypergraphs. The paper also proves a 2-colored Mantel theorem (Theorem 1.8) that looks correct and is a useful standalone lemma. But there is a load-bearing algebraic error in Case 2 of Theorem 1.6. As written, the chain from (4.1) to the definition of f(n,s,i) drops a factor of n in two positive terms: 1/2 s(s−1)n becomes s(s−1), and (13/2)i^2 n becomes 13i^2. The right-hand side is smaller than the left, so the asserted inequality is false. The subsequent convexity argument for f(n,s,i) rests on this step, so the upper bound for s≥3 is not established as written.

The good news: this looks like a typo rather than a conceptual failure. The surrounding structure is coherent. Lemma 3.3 is a solid degree-ordering tool, the reduction to link graphs and 2-colored triangle-free graphs is natural, and the s≤2 case goes through cleanly. The equality statement in Theorem 1.8 has a small omitted derivation—when a triangle in G_i contradicts (2.1), you need to invoke the equality condition deg_Gi(x)+deg_Gi(y)=n and deg_Gj(x)+deg_Gj(y)=n to get 2n, which is one line. That's minor.

The paper is worth refereeing. The result resolves a concrete open case in a recent research program, and the 2-colored Mantel theorem is a reusable tool. The gap is confined to one display and should be fixable; the authors need to supply a valid bound, probably by keeping the n-dependent terms and showing their maximum is negative under the n≥30(s+1) hypothesis. I would send it to a serious referee with a request for a corrected Case 2.

Referee Report

2 major / 3 minor

Summary. The paper studies the hypergraph Turán problem for the generalized triangle F5 (a 3-graph on five vertices with edges abc, abd, cde) under an upper bound on the matching number. The main result (Theorem 1.6) states that for n ≥ 30(s+1), an F5-free 3-graph on n vertices with matching number at most s has at most s⌊(n−s)^2/4⌋ edges for s ≥ 3, and at most binom(n−1,2) edges for s = 1,2, with the full star (s=1,2) and the complete 3-partite graph H3(n,s) (s≥3) as the unique extremal hypergraphs. The proof introduces a 2-colored version of Mantel's theorem (Theorem 1.8) as a key tool, applies a structural lemma (Lemma 3.3) that bounds the hypergraph in terms of link degrees, and then proceeds by case analysis on a parameter i. The paper also proposes two conjectures in the concluding remarks.

Significance. If correct, the result is a meaningful addition to the growing literature on hypergraph Turán problems with bounded matching number, extending the graph-theoretic Alon–Frankl theorem and the hypergraph results of Gerbner, Tompkins, and Zhou. The 2-colored Mantel theorem (Theorem 1.8) is a natural and potentially reusable extremal statement about edge-colored graphs, and its proof is attempted from first principles via induction. The paper is self-contained and the high-level proof strategy is coherent, but as discussed below a load-bearing algebraic step in the case analysis of Theorem 1.6 is invalid, and the equality case of Theorem 1.8 is not fully justified. These issues need to be addressed before the main theorem can be considered proven.

major comments (2)

[Section 4, Case 2] The displayed chain of inequalities after applying Theorem 1.8 claims that |H| ≤ s⌊(n−s)^2/4⌋ + 1/2 s(s−1)n + i(13/2 i n + n/2 − ⌊(n−s)^2/4⌋) is at most s⌊(n−s)^2/4⌋ + s(s−1) + 13i^2 + i/2 n − i(n−s)^2/4 + i. This second inequality is false: it replaces the positive terms 1/2 s(s−1)n and 13/2 i^2 n by s(s−1) and 13i^2, respectively, losing a factor n. For the stated range n ≥ 30(s+1) and s ≥ 3, the term 1/2 s(s−1)n is already much larger than s(s−1), so the right-hand side is smaller, not larger, than the expression on the left. The subsequent definition of f(n,s,i) and the estimates f(n,s,s−2) < 0 and f(n,s,s/2) < 0 rely on this invalid bound. Because this is the only estimate in Case 2 that forces |H| below s⌊(n−s)^2/4⌋, the upper bound in Theorem 1.6 for s ≥ 3 is not established as written.
[Section 2, proof of Theorem 1.8] In the equality analysis of Case 1, the paper states that if a triangle xyz exists in G_i, then by (2.1) one obtains deg_{G_i}(x)+deg_{G_i}(y)+deg_{G_j}(x)+deg_{G_j}(y) ≤ 2n−2 for j ≠ i, and calls this 'a contradiction'. However, (2.1) only yields deg_{G_j}(x)+deg_{G_j}(y) ≤ n−2, and since xy is not known to be an edge of G_j, this does not conflict with the equality condition deg_{G_j}(u)+deg_{G_j}(v)=n for edges uv of G_j. No contradiction is apparent without an additional argument. The equality characterization in Theorem 1.8 is therefore not proven, and this gap propagates to the uniqueness part of Theorem 1.6. Please supply the missing derivation or revise the argument.

minor comments (3)

[Section 4, Case 1] The proof refers to 'by Claim 4' when bounding deg(1, ¯S), but Claim 4 appears only inside Proposition 3.4; the claim should be restated or its location clarified in Section 4 to avoid confusion.
[Section 1 and Abstract] There are minor language issues: 'we showed' in the abstract is informal, and 'an 2-colored' in the abstract should be 'a 2-colored'; a careful proofread of the English would improve the presentation.
[Section 4, Case 2] In the same display as the major error, the coefficient of i n/2 appears to have the wrong sign relative to the expansion of binom(s−i,2)n; the algebraic manipulation should be revisited and corrected consistently, including the factor-n issue noted in the major comment.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the main bound is derived from a newly proved 2-colored Mantel theorem and standard extremal results.

full rationale

The central result, Theorem 1.6, is not circular. The lower bound is supplied by the explicit construction H3(n,s), whose size equals s floor((n-s)^2/4) by definition, but the upper bound is derived independently. The key ingredient, the 2-colored Mantel theorem (Theorem 1.8), is proved from scratch by induction, with no appeal to Theorem 1.6 or to the authors' prior work. The application of Theorem 1.8 to the link graphs L(v, bar S) is a genuine reduction: the F5-free hypothesis is what makes those link graphs 2-colored triangle-free, and the equality case is a derived consequence, not an input assumption. Lemma 3.3 is also proved within the paper using standard tools (Erdos-Gallai, Akiyama-Frankl, and degree arguments), and it does not presume the desired bound. The only self-citation is the remark after Theorem 1.3 that the case n > 3s of Alon and Frankl's graph theorem 'was also obtained in [9]'; that citation is not load-bearing because the paper relies on the external theorem [2], and [9] is mentioned only as a historical aside. There is no fitted parameter renamed as a prediction, no uniqueness theorem imported from the authors' own earlier work, and no ansatz smuggled in via citation. The proof does contain a likely algebraic error in Case 2 of Theorem 1.6, where positive terms of order n appear to be replaced by order-1 terms; however, an invalid inequality is a correctness risk, not a circularity, and it does not make the argument depend on its own conclusion. Overall, the derivation chain is self-contained against the stated external theorems, so no circular step is identified.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no free parameters or invented entities. It relies on standard prior extremal results used as black boxes. The new 2-colored Mantel theorem is proved from first principles via induction and Jensen's inequality.

assumptions (4)

standard math Exact Erdős-Ko-Rado theorem and Hilton-Milner theorem
Used in Proposition 3.4 to bound intersecting and non-star intersecting families in the s=1,2 cases.
standard math Erdős-Gallai theorem and Akiyama-Frankl matching lemma
Used in Lemma 3.3 to construct matchings and bound matching numbers.
standard math Frankl-Füredi theorem for ex_3(n,F5)
Cited for context on F5 Turan density; not directly used in the proof of the main theorem.
standard math Mantel's theorem and the convexity inequality (2.2)
Used in the proof of Theorem 1.8 and Theorem 2.2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Hypergraph Tur\'an problem of the generalized triangle with bounded matching number." pith.science (2026). https://pith.science/paper/IH6B33DU

@misc{pith2026250704579,
  author       = {Pith},
  title        = {Pith review of: Hypergraph Tur\'an problem of the generalized triangle with bounded matching number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IH6B33DU}},
  note         = {Machine review of arXiv:2507.04579}
}

abstract

Let $\mathcal{H}$ be a 3-graph on $n$ vertices. The matching number $\nu(\mathcal{H})$ is defined as the maximum number of disjoint edges in $\mathcal{H}$. The generalized triangle $F_5$ is a 3-graph on the vertex set $\{a,b,c,d,e\}$ with the edge set $\{abc, abd,cde\}$. In this paper, we showed that an $F_5$-free 3-graph $\mathcal{H}$ with matching number at most $s$ has at most $s\lfloor (n-s)^2/4\rfloor$ edges for $n\geq 30(s+1)$ and $s\geq 3$. For the proof, we establish a 2-colored version of Mantel's theorem, which may be of independent interests.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 15 canonical work pages

[1]

Akiyama and P

J. Akiyama and P. Frankl, On the size of graphs with complete-factors, J. Graph Theory, 9 (1985), 197–201

work page 1985
[2]

Alon and P

N. Alon and P. Frankl, Tur´ an graphs with bounded matching number, J. Combin. Theory Ser. B, 165 (2024), 223–229

work page 2024
[3]

Erd˝ os and T

P. Erd˝ os and T. Gallai, On maximal paths and circuits of graphs, Acta. Math. Hung, 10 (1959), 337–356

work page 1959
[4]

Erd˝ os, C

P. Erd˝ os, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. 12 (1961), 313–320

work page 1961
[5]

Frankl, Graphs without rainbow triangles, arXiv:2203.07768v1, (2022)

P. Frankl, Graphs without rainbow triangles, arXiv:2203.07768v1, (2022)

arXiv 2022
[6]

Frankl, The Erd˝ os-Ko-Rado theorem is true forn = ckt, Coll

P. Frankl, The Erd˝ os-Ko-Rado theorem is true forn = ckt, Coll. Math. Soc. J. Bolyai, 18 (1978), 365–375

work page 1978
[7]

Extremal results for graphs avoiding a rainbow subgraph

P. Frankl, E. Gy˝ ori, Z. He, Z. Lv, N. Salia, C. Tompkins, K. Varga, X. Zhu, Some remarks on graphs without rainbow triangles, arXiv:2204.07567, (2022)

work page Pith review arXiv 2022
[8]

Frankl and Z

P. Frankl and Z. F¨ uredi, A new generalization of the Erd˝ os–Ko–Rado theorem, Com- binatorica, 3 (1983), 341–349

work page 1983

Show all 17 references

[9]

L. Fu, J. Wang, and W. Yang, The maximum number of edges in a{Kr+1, Mk+1}-free graph, Discuss. Math. Graph Theory, 44 (2024), 1617–1629

2024
[10]

Gerbner, C

D. Gerbner, C. Tompkins, and J. Zhou, On hypergraph Tur´ an problems with bounded matching number, Eur. J. Combin. 127 (2024), 104155

2024
[11]

Hilton and E.C

A.J.W. Hilton and E.C. Milner, Some intersection theorems for systems of finite sets, Quart.J.Math. Oxford Ser, 18 (1967), 369–384

1967
[12]

X. Li, J. Ma, and Z. Zheng, On the multicolor Tur´ an conjecture for color-critical graphs, arXiv:2407.14905, (2024). 17

2024
[13]

Keevash and D

P. Keevash and D. Mubayi, Stability theorems for cancellative hypergraphs, J. Com- bin. Theory Ser. B, 92 (2004), 163–175

2004
[14]

Keevash, M

P. Keevash, M. Saks, B. Sudakov and J. Verstraete, Multicolour Tur´ an problems, Advances in Applied Mathematics, 33 (2004), 238–262

2004
[15]

Ma and X

Y. Ma and X. M. Hou, Graphs without rainbow cliques of orders four and five, arXiv:2306.12222v1, (2023)

2023 arXiv
[16]

Tur´ an, Eine Extremalaufgabe aus der Graphentheorie, Mat

P. Tur´ an, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, 48 (1941), 436–452

1941
[17]

R. M. Wilson, The exact bound in the Erd˝ os-Ko-Rado theorem, Combinatorica 4 (1984), 247–257. 18

1984

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Akiyama and P

J. Akiyama and P. Frankl, On the size of graphs with complete-factors, J. Graph Theory, 9 (1985), 197–201

work page 1985

[2] [2]

Alon and P

N. Alon and P. Frankl, Tur´ an graphs with bounded matching number, J. Combin. Theory Ser. B, 165 (2024), 223–229

work page 2024

[3] [3]

Erd˝ os and T

P. Erd˝ os and T. Gallai, On maximal paths and circuits of graphs, Acta. Math. Hung, 10 (1959), 337–356

work page 1959

[4] [4]

Erd˝ os, C

P. Erd˝ os, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. 12 (1961), 313–320

work page 1961

[5] [5]

Frankl, Graphs without rainbow triangles, arXiv:2203.07768v1, (2022)

P. Frankl, Graphs without rainbow triangles, arXiv:2203.07768v1, (2022)

arXiv 2022

[6] [6]

Frankl, The Erd˝ os-Ko-Rado theorem is true forn = ckt, Coll

P. Frankl, The Erd˝ os-Ko-Rado theorem is true forn = ckt, Coll. Math. Soc. J. Bolyai, 18 (1978), 365–375

work page 1978

[7] [7]

Extremal results for graphs avoiding a rainbow subgraph

P. Frankl, E. Gy˝ ori, Z. He, Z. Lv, N. Salia, C. Tompkins, K. Varga, X. Zhu, Some remarks on graphs without rainbow triangles, arXiv:2204.07567, (2022)

work page Pith review arXiv 2022

[8] [8]

Frankl and Z

P. Frankl and Z. F¨ uredi, A new generalization of the Erd˝ os–Ko–Rado theorem, Com- binatorica, 3 (1983), 341–349

work page 1983