REVIEW 2 major objections 4 minor 28 references
3-uniform hypergraphs with few Berge paths of length three between any two vertices
T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper constructs $\Theta^{B}_{3,217}$-free 3-uniform hypergraphs with $\Omega(n^{4/3})$ edges.
desk verdict Clever construction with a real gap: the (1,3,1,2)-type Berge path bound is asserted in Section 3.4 without proof, so the main theorem is not yet established as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is the resultant of two polynomials in one variable: a determinant built from the coefficients that vanishes whenever the two polynomials share a common root. In the proof, every hypothetical Berge 3-path between fixed vertices translates into a system of eight polynomial equations, and eliminating the auxiliary variables by repeated resultants yields univariate polynomials whose factorizations bound the number of solutions. The construction's vertex sets $S_1, S_2$ and the small exceptional sets $T_4, T_5$ are chosen so that none of the non-zero factors in these factorizations vanish, leaving at most 4 solutions for the $(1,2,1,2)$-type, 36 for the $(1,2,3,2)$-type, and 108 for the $(1,2,3,1)$-type; the final counting section takes the remaining $(1,3,1,2)$-type to be bounded by 36, giving totals of 216 and 76. The factorizations themselves are computer algebra computations.
What would settle it
For a concrete sufficiently large prime $p$, enumerate all Berge 3-paths of the $(1,3,1,2)$ type (vertices lying in parts 1,3,1,2 in that order) between a fixed pair of vertices in different parts of $H$; if any pair has at least 177 such paths, the total with the other two types reaches at least 217 and the construction is not $\Theta^{B}_{3,217}$-free. Independently, re-computing the resultant factorizations with a verification tool would confirm whether the asserted per-type bounds are correct.
Extended reading notes
Core claim
The paper's central claim is Theorem 1.1: for sufficiently large primes $p$, the constructed 3-partite 3-uniform hypergraph $H$ has $n = 3|S_1|(p-2)^2$ vertices and at least $|S_1|^3(p-13) = \Omega(n^{4/3})$ edges, yet contains no copy of the Berge $\theta$ hypergraph $\Theta^{B}_{3,217}$. The argument counts, for each pair of vertices, the Berge 3-paths of every possible part-type; the maximum totals are claimed to be 216 for two vertices in the same part and 76 for two vertices in different parts. Since $76 < 217$, no pair can anchor the required 217 internally disjoint Berge 3-paths. Together with the earlier upper bound of $O(n^{4/3})$, this gives $\mathrm{ex}_3(n, \Theta^{B}_{3,217}) = \Theta(n^{4/3})$, and the parameter $t = 217$ is far below the roughly $3^{20}$ needed by the random algebraic construction.
Load-bearing premise
The proof's conclusion rests on the assertion, made in the final counting section without a derivation in the earlier sections, that between two vertices in different parts there are at most 36 Berge 3-paths of the type whose four vertices lie in parts 1,3,1,2; if that count were larger, the total number of such paths could reach 217 and the construction would contain the forbidden $\Theta^{B}_{3,217}$.
Editorial extensions
If this is right
- The extremal number satisfies $\mathrm{ex}_3(n, \Theta^{B}_{3,217}) = \Theta(n^{4/3})$, settling its order of magnitude.
- For $r \ge 3$ and $\ell = 3$, this provides the first asymptotically matching lower bound for a Berge theta with a small fixed number of paths.
- If the claimed per-pair path counts hold, the hypergraph is actually $\Theta^{B}_{3,t}$-free for every $t \ge 77$, stronger than the stated $t = 217$.
- The resultant-elimination approach can be aimed at other fixed $(\ell, t)$ pairs, as the paper's concluding remarks suggest.
Reading between the lines
- A direct way to complete the proof would be to run the same resultant computation for the $(1,3,1,2)$-type paths that the final counting relies on; the equations have the same algebraic shape as those in the $(1,2,3,2)$ case, so the missing bound is likely obtainable by an analogous calculation.
- If the Section 3.4 counts are correct, the threshold $t$ could be pushed well below 217, since the construction blocks any pair of vertices from having 77 or more internally disjoint Berge 3-paths; the paper itself says 217 is not believed to be best possible.
- The same finite-field-plus-resultant template suggests a route to $r$-uniform Berge thetas with $r > 3$: more variables enter the edge equations, but resultant elimination remains systematic, so explicit constructions for moderate $t$ may be feasible where random algebraic methods require astronomically large $t$.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper constructs an explicit 3-partite 3-uniform hypergraph H over finite fields with n vertices and Ω(n^{4/3}) edges, and claims that H contains no Berge theta hypergraph Θ^B_{3,217}. The proof strategy is to show that between any two vertices of H there are at most 216 Berge 3-paths, so that no 217 internally disjoint Berge 3-paths can exist. The path counts are obtained by classifying Berge 3-paths into types according to the parts visited and then using resultants of polynomials to bound the number of solutions; several factorization steps are performed with MAGMA. The conclusion is ex3(n,Θ^B_{3,217}) = Ω(n^{4/3}), which together with the upper bound of He and Tait gives Θ(n^{4/3}).
Significance. If the result is correct, it provides the first explicit algebraic construction for this Berge theta Turán problem with a relatively small parameter t=217 for length ℓ=3, substantially improving the random algebraic method's constant. The use of polynomial resultants to eliminate variables is a promising technique for hypergraph Turán constructions. The paper also contains a new proof of the known graph theta result ex(n,θ_{4,3})=Ω(n^{5/4}), and the finite-field construction has no fitted parameters. These strengths make the paper potentially valuable. However, the proof as written has a clear gap in the path count for one of the required types, and the heavy dependence on unverifiable computer algebra outputs weakens the rigor as currently presented.
major comments (2)
- [Section 3.4 (Proof of Theorem 1.1)] For a pair of vertices in different parts, say (b1,c1,d1,1) ∈ V1 and (b2,c2,d2,2) ∈ V2, the only possible Berge 3-path types are (1,2,1,2), (1,2,3,2), and (1,3,1,2). Sections 3.1 and 3.3 give upper bounds of 4 and 36 for the first two types, respectively, but no section proves any bound for the (1,3,1,2)-type. The initial reduction in Section 3 lists only the types (1,2,1,2), (1,2,3,1), and (1,2,3,2) as needing consideration 'by symmetry,' and neither the cyclic symmetry of the construction nor reversal maps (1,3,1,2) to any of these three types. The assertion in Section 3.4 that 'there are at most 76 such Berge 3-paths' therefore requires an unproved bound of at most 36 for the (1,3,1,2)-type (or a different total argument). Since the proof of Θ^B_{3,217}-freeness needs a total of at most 216 Berge 3-paths between any pair, this missing estimate is load-bearing; without it Theorem 1.1 is not established.
- [Sections 3.1-3.3 and Appendix] The bounds of 4, 108, and 36 Berge 3-paths rely on factorizations and resultant computations stated as MAGMA outputs, but the appendix supplies only the program for Lemma 3.2. For example, in Section 3.2 the factorizations h5 = y3 x2 (x2-1) h'_5, h6 = y1 x2^2 (x2-1)^2 h'_6, the coefficients t_i of the degree-24 polynomial t, and the resultants s_1,...,s_14 are asserted without code or algebraic derivations; the same is true for the factorization of t in Section 3.3 and the later computations in Section 3.1. These computations are essential for the claimed path bounds, so as written the proofs of the central lemmas are not verifiable. The authors should include the complete MAGMA code and outputs, or an independent verification, for every computational step.
minor comments (4)
- [Section 3.1] The phrase 'end core vertices' is used without definition; it should be clarified that it refers to the two endpoints of the Berge path.
- [Section 3.4] For same-part pairs, the bound of 216 for the (1,3,2,1)-type follows by reversing paths of the (1,2,3,1)-type and applying Section 3.2, but this is not stated explicitly; a one-sentence justification would improve clarity.
- [Appendix] The line 'Fac torization(h);' contains a typo; this is cosmetic but should be corrected in the final program listing.
- [Throughout] Some displayed constants in T5 appear as raw fractions (e.g., 12757/10872); the text would benefit from stating explicitly that p is chosen larger than all denominators so these are well-defined in F_p.
Circularity Check
No significant circularity: explicit algebraic construction with counting-derived parameter 217; remaining issues are expositional gaps, not circular reasoning.
full rationale
The claimed lower bound ex3(n, Theta^B_{3,217}) = Omega(n^(4/3)) is obtained from an explicit algebraic hypergraph H, with no parameter fitted to the target result. The vertex set S1 is defined as (T1 cap T3) minus (T4 cup T5), where T5 is the root set of a quintic whose coefficients coincide with factors appearing later in the resultant factorizations; this is a fixed design constraint chosen to make the path-counting proof work, not a quantity inferred from the conclusion. The parameter 217 is one more than the maximum number of Berge 3-paths between two vertices established by the counting arguments (216 in the same-part case and a claimed 76 in the different-part case), so it is a consequence of the count rather than an input. The path-counting lemmas are algebraic resultant computations, and the MAGMA factorizations are external computational evidence; even where the code is not shipped (Remark 3.3, which provides only the program for Lemma 3.2 and says the remaining programs are available on request), this is a reproducibility gap, not circular reasoning. The one notable expositional gap is Section 3.4's assertion that different-part pairs have at most 76 Berge 3-paths: the (1,3,1,2)-type bound is not given its own subsection and must be obtained from the paper's earlier 'by symmetry' reduction, which is not spelled out at that point. That is an omitted argument, not a circular one: it does not assume the conclusion, and the missing bound is neither a fitted value nor a restatement of the theorem. No load-bearing self-citations appear; the upper bound by He and Tait [17] and the Theorem 4.1 result of Verstraete and Williford [27] are independent prior work. The derivation chain is self-contained and does not reduce to its inputs.
Assumptions & free parameters
assumptions (3)
- standard math Resultant property: if two polynomials have a common root (or common factor) then their resultant is zero (Lemma 2.2).
- domain assumption MAGMA computations of polynomial factorizations and resultants are correct.
- domain assumption The rational polynomial factorizations remain valid and non-vanishing over F_p for sufficiently large primes p, with the excluded sets T4 and T5 covering all zero factors.
Cite this review
Pith. "Pith review of 3-uniform hypergraphs with few Berge paths of length three between any two vertices." pith.science (2026). https://pith.science/paper/3MDI2FJH
@misc{pith2026190801459,
author = {Pith},
title = {Pith review of: 3-uniform hypergraphs with few Berge paths of length three between any two vertices},
year = {2026},
howpublished = {\url{https://pith.science/paper/3MDI2FJH}},
note = {Machine review of arXiv:1908.01459}
}
abstract
Recently, Berge theta hypergraphs have received special attention due to the similarity with Berge even cycles. Let $r$-uniform Berge theta hypergraph $\Theta_{\ell,t}^{B}$ be the $r$-uniform hypergraph consisting of $t$ internally disjoint Berge paths of length $\ell$ with the same pair of endpoints. In this work, we determine the Tur\'{a}n number of $3$-uniform Berge theta hypergraph when $\ell=3$ and $t$ is relatively small. More precisely, we provide an explicit construction giving \begin{align*} \textup{ex}_{3}(n,\Theta_{3,217}^{B})=\Omega(n^{\frac{4}{3}}). \end{align*} This matches an earlier upper bound by He and Tait up to an absolute constant factor. The construction is algebraic, which is based on some equations over finite fields, and the parameter $t$ in our construction is much smaller than that in random algebraic construction. Our main technique is using the resultant of polynomials, which appears to be a powerful technique to eliminate variables.
Reference graph
Works this paper leans on
-
[1]
B. Bollob´ as and E. Gy˝ ori. Pentagons vs. triangles. Discrete Math. , 308(19):4332–4336, 2008
work page 2008
-
[2]
J. A. Bondy and M. Simonovits. Cycles of even length in graphs. J. Combin. Theory Ser. B, 16:97–105, 1974
work page 1974
- [3]
-
[4]
W. G. Brown. On graphs that do not contain a thomsen graph. Canadian mathematical bulletin = Bulletin canadien de mathematiques , 9(3), 1966
work page 1966
-
[5]
B. Bukh and Z. Jiang. A bound on the number of edges in graphs wit hout an even cycle. Combin. Probab. Comput. , 26(1):1–15, 2017
work page 2017
-
[6]
Tur\'an numbers of theta graphs
B. Bukh and M. Tait. Tur´ an number of theta graphs. arXiv preprint , arXiv: 1804.10014, 2018
work page Pith review arXiv 2018
-
[7]
D. Conlon. Graphs with few paths of prescribed length between a ny two vertices. arXiv preprint, arXiv: 1411.0856, 2014
work page Pith review arXiv 2014
-
[8]
P. Erd˝ os. On sequences of integers no one of which divides the p roduct of two others and on some related problems. Isvestia Nauchno-Issl. Inst. Mat. i Meh. Tomsk , 2:74–82, 1938
work page 1938
Show all 28 references
-
[9]
Erd˝ os, A
P. Erd˝ os, A. R´ enyi, and V. T. S´ os. On a problem of graph theo ry. Studia Sci. Math. Hungar., 1:215–235, 1966
1966
-
[10]
Erd˝ os and A
P. Erd˝ os and A. H. Stone. On the structure of linear graphs. Bull. Amer. Math. Soc. , 52:1087–1091, 1946
1946
-
[11]
R. J. Faudree and M. Simonovits. On a class of degenerate extr emal graph problems. Combinatorica, 3(1):83–93, 1983
1983
-
[12]
P. A. Fuhrmann. A polynomial approach to linear algebra . Universitext. Springer, New York, second edition, 2012. 17
2012
-
[13]
Gerbner, A
D. Gerbner, A. Methuku, and M. Vizer. Asymptotics for the Tu r´ an number of Berge-K2,t. J. Combin. Theory Ser. B , 137:264–290, 2019
2019
-
[14]
Gerbner and C
D. Gerbner and C. Palmer. Extremal results for Berge hyperg raphs. SIAM J. Discrete Math., 31(4):2314–2327, 2017
2017
-
[15]
E. Gy˝ ori. Triangle-free hypergraphs. Combin. Probab. Comput. , 15(1-2):185–191, 2006
2006
-
[16]
Gy˝ ori and N
E. Gy˝ ori and N. Lemons. Hypergraphs with no cycle of a given le ngth. Combin. Probab. Comput., 21(1-2):193–201, 2012
2012
-
[17]
He and M
Z. He and M. Tait. Hypergraphs with few berge paths of fixed len gth between vertices. arXiv preprint, arXiv: 1807.10177, 2018
2018 arXiv
-
[18]
Jiang and J
T. Jiang and J. Ma. Cycles of given lengths in hypergraphs. J. Combin. Theory Ser. B , 133:54–77, 2018
2018
-
[19]
Lang and A
S. Lang and A. Weil. Number of points of varieties in finite fields. Amer. J. Math. , 76:819–827, 1954
1954
-
[20]
Lazebnik, V
F. Lazebnik, V. A. Ustimenko, and A. J. Woldar. A new series of d ense graphs of high girth. Bull. Amer. Math. Soc. (N.S.) , 32(1):73–79, 1995
1995
-
[21]
Lazebnik and J
F. Lazebnik and J. Verstra¨ ete. On hypergraphs of girth five . Electron. J. Combin. , 10:R25, 2003
2003
-
[22]
W. Mantel. Problem 28. Wiskundige Opgaven , 10:60–61, 1907
1907
-
[23]
T. A. Terlep and J. Williford. Graphs from generalized Kac-Moody algebras. SIAM J. Discrete Math., 26(3):1112–1120, 2012
2012
-
[24]
C. Timmons. On r-uniform linear hypergraphs with no Berge- K2,t. Electron. J. Combin. , 24(4):Paper 4.34, 15, 2017
2017
-
[25]
P. Tur´ an. Eine extremalaufgabe aus der graphentheorie. Fiz Lapok, pages 436–452, 1941
1941
-
[26]
Verstra¨ ete
J. Verstra¨ ete. Extremal problems for cycles in graphs. In Recent trends in combinatorics , volume 159 of IMA Vol. Math. Appl. , pages 83–116. Springer, [Cham], 2016
2016
-
[27]
Verstra¨ ete and J
J. Verstra¨ ete and J. Williford. Graphs without theta subgrap hs. J. Combin. Theory Ser. B, 134:76–87, 2019
2019
-
[28]
R. Wenger. Extremal graphs with no C 4’s, C 6’s, or C 10’s. J. Combin. Theory Ser. B , 52(1):113–116, 1991. 18 Appendix Program 1. P < x 1, x2, x3, y1, y3, z2, z3, t3 >:= P olynomialRing(RationalF ield(), 8); f1 := x2 ∗ x3 − x3 ∗ x1 + t3 ∗ x1 − z2 ∗ t3 + z2 ∗ z3 − z3 ∗ y1 + y3...
1991
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.