pith. sign in

arxiv: 2604.07642 · v2 · submitted 2026-04-08 · 🧮 math.CO

On the connected Tur\'an number of Berge paths and Berge cycles

Xiamiao Zhao , D\'aniel Gerbner , Junpeng Zhou This is my paper

Pith reviewed 2026-05-10 17:04 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C3505C65
keywords Berge pathsBerge cyclesTurán numberextremal hypergraphsconnected hypergraphsKelmans operationpath-free hypergraphs
0
0 comments X

The pith

The extremal number of edges in connected r-uniform hypergraphs without Berge paths of length k-1 equals the graph version for every k at least 2r+2.

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

The paper proves that the maximum number of hyperedges in an n-vertex connected r-uniform hypergraph with no Berge path of length k-1 is given by the classical graph extremal number for all k greater than or equal to 2r+2, and that this equality fails when k is at most 2r+1. The same threshold improves the prior bound for the maximum edges in a 2-connected r-uniform hypergraph without a Berge cycle of length at least k. This settles the minimal threshold k0 asked by Győri, Salia and Zamora. A reader cares because the result pins down exactly when hypergraph Berge problems reduce to ordinary graph problems and inherit their solutions.

Core claim

We prove that the extremal number holds for all k≥2r+2 and fails for k≤2r+1, thereby completely resolving the problem posed by Győri, Salia and Zamora. Moreover, we improve the result of Füredi, Kostochka and Luo by showing that the extremal number for 2-connected hypergraphs containing no Berge cycle of length at least k holds for all k≥2r+2 and fails for k≤2r+1. Our approach reduces Berge-Turán problems to classical extremal graph theory problems and applies recent work concerning the feasibility of graph parameters and the Kelmans operation.

What carries the argument

Reduction of Berge-Turán problems to classical extremal graph theory problems using the Kelmans operation and feasibility results for graph parameters.

If this is right

  • The exact maximum edge count is now known for connected r-uniform hypergraphs avoiding Berge paths of length k-1 whenever k is at least 2r+2.
  • The same exact count holds for 2-connected hypergraphs avoiding Berge cycles of length at least k when k is at least 2r+2.
  • The claimed count does not hold for any k at most 2r+1, so larger constructions exist in that range.
  • The minimal k0 such that the extremal number holds for all larger k is exactly 2r+2 for both the path and cycle problems.

Where Pith is reading between the lines

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

  • The same reduction may allow exact determinations for other connected Berge-forbidden structures once their graph counterparts are known.
  • The sharp failure at k=2r+1 shows that small-length cases need separate constructions that exploit hypergraph features beyond graph parameters.

Load-bearing premise

The reduction of the hypergraph Berge-Turán problem to classical extremal graph theory remains valid down to k=2r+2 with no further restrictions.

What would settle it

A connected r-uniform hypergraph on sufficiently large n vertices with strictly more edges than the classical graph extremal number yet containing no Berge path of length 2r+1 would falsify the claim for k=2r+2.

read the original abstract

Given a graph $F$, a Berge copy of $F$ (Berge-$F$ for short) is a hypergraph obtained by enlarging the edges arbitrarily. Gy\H{o}ri, Salia and Zamora determined the maximum number of hyperedges in a connected $r$-uniform hypergraph on $n$ vertices containing no Berge path of length $k-1$ for all $k\geq 2r+14$ and sufficiently large $n$, and asked for the minimum $k_0$ such that this extremal number holds for all $k\geq k_0$. In this paper, we prove that the extremal number holds for all $k\geq 2r+2$ and fails for $k\le 2r+1$, thereby completely resolving the problem posed by Gy\H{o}ri, Salia and Zamora. Moreover, we improve the result of F\"uredi, Kostochka and Luo, who determined the maximum number of hyperedges in a $2$-connected $n$-vertex $r$-uniform hypergraph containing no Berge cycle of length at least $k$ for all $k\geq 4r$ and sufficiently large $n$, by showing that this extremal number holds for all $k\geq 2r+2$ and fails for $k\le 2r+1$. Our approach reduces Berge-Tur\'an problems to classical extremal graph theory problems, and applies recent work of Ai, Lei, Ning and Shi concerning the feasibility of graph parameters and the Kelmans operation.

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 resolves the open problem of Győri, Salia and Zamora by proving that the connected r-uniform Turán number ex_conn(n, Berge-P_{k-1}, r) equals the corresponding graph extremal number for all k ≥ 2r+2 and sufficiently large n, with explicit constructions showing failure for k ≤ 2r+1. It reduces the Berge-hypergraph problem to classical extremal graph theory via the Kelmans operation and invokes the parameter-feasibility results of Ai, Lei, Ning and Shi. The paper also improves the Furedi-Kostochka-Luo bound for 2-connected r-uniform hypergraphs without long Berge cycles, lowering the threshold from k ≥ 4r to k ≥ 2r+2 with matching failure constructions for smaller k.

Significance. If the reduction holds at the new boundary, this is a substantial advance: it completely settles the posed question with a sharp threshold of 2r+2 (down from 2r+14) and supplies both the upper bound via graph-theoretic reduction and explicit lower-bound constructions. The approach of translating Berge-Turán questions into graph problems is clean and leverages independent recent work on the Kelmans operation and feasible parameters; this technique may extend to other Berge-extremal problems.

minor comments (3)
  1. [Introduction] The introduction should state the precise value of the extremal function (not merely the range of k for which it holds) when citing the main theorems.
  2. [Section 3 (reduction)] In the reduction step, explicitly verify that the Kelmans operation preserves r-uniformity and the required connectivity (connected or 2-connected) when applied to the auxiliary graph constructed from the hypergraph.
  3. [Section 4 (constructions)] The failure constructions for k = 2r+1 should include a brief check that the resulting hypergraph is indeed connected (or 2-connected) and contains no forbidden Berge structure.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our manuscript, which correctly identifies the resolution of the Győri-Salia-Zamora problem at the sharp threshold of 2r+2 and the improvement over the Füredi-Kostochka-Luo bound. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper reduces the Berge-Turán problems for paths and cycles in r-uniform hypergraphs to classical extremal graph theory via the Kelmans operation and graph parameter feasibility results from the independent (non-overlapping) work of Ai, Lei, Ning and Shi. This reduction is invoked to prove the extremal number holds for all k ≥ 2r+2 (with explicit failure constructions for k ≤ 2r+1), extending prior thresholds without any self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain is self-contained against external benchmarks and does not reduce any claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the proof relies on standard background results in extremal graph theory plus the applicability of the cited recent work on Kelmans operations; no free parameters or new entities are mentioned.

axioms (1)
  • domain assumption The Kelmans operation and feasibility results of Ai et al. apply directly to the auxiliary graphs obtained from the hypergraph reduction.
    The abstract states that the approach applies this recent work.

pith-pipeline@v0.9.0 · 5591 in / 1247 out tokens · 52350 ms · 2026-05-10T17:04:13.728280+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

26 extracted references · 26 canonical work pages

  1. [1]

    J. Ai, H. Lei, B. Ning, Y. Shi, Graph operations and a unified method for kinds of Tur´ an-type problems on paths, cycles and matchings,Canad. J. Math.(2025) 1–27. 23

    work page 2025

  2. [2]

    Balister, E

    P.N. Balister, E. Gy˝ ori, J. Lehel, R.H. Schelp, Connected graphs without long paths, Discrete Math. 308 (19) (2008) 4487–4494

    work page 2008

  3. [3]

    Berge, Hypergraphs: Combinatorics of Finite Sets,North-Holland, Amsterdam, 1989

    C. Berge, Hypergraphs: Combinatorics of Finite Sets,North-Holland, Amsterdam, 1989

    work page 1989

  4. [4]

    Cheng, D

    X. Cheng, D. Gerbner, H. Hama Karim, S. Miao, J. Zhou, The Tur´ an number of Berge paths,arXiv preprint, arXiv:2602.17946, 2026

    work page arXiv 2026

  5. [5]

    Davoodi, E

    A. Davoodi, E. Gy˝ ori, A. Methuku, C. Tompkins, An Erd˝ os-Gallai type theorem for uniform hypergraphs,European J. Combin.69(2018) 159–162

    work page 2018

  6. [6]

    Erd˝ os, T

    P. Erd˝ os, T. Gallai, On the maximal paths and cricuits of graphs, Acta Math. Acad. Sci. Hung. 10 (1959) 337–357

    work page 1959

  7. [7]

    Ergemlidze, E

    B. Ergemlidze, E. Gy˝ ori, A. Methuku, N. Salia, C. Tompkins, O. Zamora. Avoiding long Berge-cycles, the missing casesk=r+ 1 andk=r+ 2,Combinatorics, Probability and Computing(2019), 1–13

    work page 2019

  8. [8]

    F¨ uredi, A

    Z. F¨ uredi, A. Kostochka, R. Luo, Avoiding long Berge cycles,J. Comb. Theory Ser. B 137(2019) 55–64

    work page 2019

  9. [9]

    F¨ uredi, A

    Z. F¨ uredi, A. Kostochka, R. Luo, On 2-connected hypergraphs with no long cycles, Electron. J. Comb.26(4) (2019) 4–31

    work page 2019

  10. [10]

    F¨ uredi, A

    Z. F¨ uredi, A. Kostochka, R. Luo, Avoiding long Berge cycles II,J. Comb.12(2) (2021)

    work page 2021

  11. [11]

    F¨ uredi, A

    Z. F¨ uredi, A. Kostochka, and J. Verstra¨ ete, Stability in the Erd˝ os–Gallai theorems on cycles and paths,Journal of Combinatorial Theory, Series B121(2016) 197–228

    work page 2016

  12. [12]

    Gerbner, A

    D. Gerbner, A. Methuku, C. Palmer, General lemmas for Berge-Tur´ an hypergraph prob- lems,European J. Combin.86(2020) 103082

    work page 2020

  13. [13]

    Gerbner, D

    D. Gerbner, D. Nagy, B. Patk´ os, N. Salia, M. Vizer, Stability of extremal connected hypergraphs avoiding Berge-paths,European J. Combin.118(2024) 103930

    work page 2024

  14. [14]

    Gerbner, C

    D. Gerbner, C. Palmer, Extremal results for Berge hypergraphs,SIAM J. Discrete Math. 31(4) (2017) 2314–2327

    work page 2017

  15. [15]

    Gerbner, C

    D. Gerbner, C. Palmer, Counting copies of a fixed subgraph inF-free graphs,European J. Combin.82(2019) 103001

    work page 2019

  16. [16]

    Gerbner, C

    D. Gerbner, C. Palmer, Survey of generalized Tur´ an problems—counting subgraphs, Electronic J. Comb.33(1) (2026) #P1.23

    work page 2026

  17. [17]

    Gy˝ ori, G

    E. Gy˝ ori, G. Katona, N. Lemons, Hypergraph extensions of the Erd˝ os-Gallai theorem, European J. Combin.58(2016) 238–246. 24

    work page 2016

  18. [18]

    Gy˝ ori, N

    E. Gy˝ ori, N. Lemons, N. Salia, O. Zamora, The structure of hypergraphs without long Berge cycles,J. Combin. Theory Ser. B148(2021) 239–250

    work page 2021

  19. [19]

    Gy˝ ori, A

    E. Gy˝ ori, A. Methuku, N. Salia, C. Tompkins, M. Vizer, On the maximum size of connected hypergraphs without a path of given length,Discrete Math.341(9) (2018) 2602–2605

    work page 2018

  20. [20]

    Gy˝ ori, N

    E. Gy˝ ori, N. Salia, O. Zamora, Connected hypergraphs without long Berge-paths,Eu- ropean J. Combin.96(2021) 103353

    work page 2021

  21. [21]

    G. N. Kopylov, Maximal paths and cycles in a graph, Dokl. Akad. Nauk SSSR 234 (1977) 19–21

    work page 1977

  22. [22]

    Kostochka, R

    A. Kostochka, R. Luo. Onr-uniform hypergraphs with circumference less thanr.Disc. Appl. Math.,276, (2020), 69–91

    work page 2020

  23. [23]

    B. Li, B. Ning, A strengthening of Erd˝ os-Gallai Theorem and proof of Woodall’s con- jecture,Journal of Combinatorial Theory, Series B146(2021) 76–95

    work page 2021

  24. [24]

    J. Ma, B. Ning, Stability results on the circumference of a graph,Combinatorica40 (2020) 105–147

    work page 2020

  25. [25]

    Whitney, Congruent graphs and the connectivity of graphs,American Journal of Mathematics,54(1) 1932, 150–168

    H. Whitney, Congruent graphs and the connectivity of graphs,American Journal of Mathematics,54(1) 1932, 150–168

    work page 1932

  26. [26]

    X. Zhao, Z. Yang, Y. Wang, Y. Bai, J. Zhou, On Tur´ an-type problems for Berge match- ings,arXiv preprint, arXiv:2510.05422v1. 25

    work page arXiv