pith. sign in

arxiv: 2604.18217 · v1 · submitted 2026-04-20 · 🧮 math.CO

Generalized Tur\'an problems for Berge hypergraphs

Xiamiao Zhao , Xin Cheng , D\'aniel Gerbner This is my paper

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

classification 🧮 math.CO
keywords generalized Turán numberBerge hypergraphextremal hypergraph theoryshadow graphTurán hypergraph
0
0 comments X

The pith

For any hypergraph H and sufficiently large k, the balanced complete (k-1)-partite r-graph maximizes the number of copies of H in Berge-K_k-free r-graphs.

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

The paper studies generalized Turán numbers ex_r(n, H, Berge-F) that count the maximum copies of an r-graph H inside F-free r-graphs, where forbidden substructures are Berge copies of a graph F. It links this to the problem of counting copies of the shadow graph of H inside ordinary F-free graphs on the same vertex set. The central result is that when F is a large clique K_k, the extremal construction is always the balanced complete (k-1)-partite r-graph, independent of the choice of H. This provides an exact answer that generalizes the corresponding result from graphs to hypergraphs and includes additional inequalities and results for complete hypergraphs and Berge paths.

Core claim

For every r-uniform hypergraph H there is a number K_H such that whenever k exceeds K_H, the maximum number of copies of H in an n-vertex Berge-K_k-free r-graph equals the number of such copies in the balanced complete (k-1)-partite r-graph on n vertices.

What carries the argument

Reduction via the shadow graph of H, which turns the hypergraph copy count into a graph copy count of the shadow inside F-free graphs.

If this is right

  • The same partite construction works for all H when forbidding large Berge cliques.
  • ex_r(n, K_s^r, Berge-F) is at most the graph Turán number ex_s(n, Berge-F), with equality under sufficient conditions.
  • The connected version for Berge paths has analogous bounds.

Where Pith is reading between the lines

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

  • The result implies that hypergraph extremal problems for large forbidden cliques are determined by their underlying graph shadows.
  • One could investigate whether the same construction remains extremal for other forbidden Berge graphs beyond cliques.
  • Stability versions might follow from the graph case via the same reduction.

Load-bearing premise

That for large enough k the extremal r-graph is determined solely by the shadow graph reduction without H-dependent obstructions.

What would settle it

Finding an r-graph H, a fixed k, and an n-vertex Berge-K_k-free r-graph G with more copies of H than the balanced (k-1)-partite r-graph has.

read the original abstract

Let $\mathcal{H}$ be a hypergraph and $F$ be a graph. If there exists a bijection between the hyperedges of $\mathcal{H}$ and the edges of $F$ such that each hyperedge contains its image, then we say that $\mathcal{H}$ is a \textit{Berge copy} of $F$, and the collection of Berge copies of $F$ is denoted by Berge-$F$. Given $r$-graphs $\mathcal{F}$ and $\mathcal{H}$, the generalized hyper-Tur\'{a}n number $\text{ex}_r(n, \mathcal{H}, \mathcal{F})$ is the maximum number of copies of $\mathcal{H}$ in $n$-vertex $\mathcal{F}$-free $r$-graphs. We study $\text{ex}_r(n, \mathcal{H}, \text{Berge-}F)$. For general $\mathcal{H}$, we connect this problem to counting copies of the shadow graph of $\mathcal{H}$ in $F$-free graphs and obtain several exact results. In particular, we show that for any hypergraph $\mathcal{H}$, if $k$ is sufficiently large, then $\text{ex}_r(n, \mathcal{H}, \text{Berge-}K_k)$ is achieved by the balanced complete $(k-1)$-partite $r$-graph, generalizing a result of Morrison, Nir, Norin, Rza{\.z}ewski and Wesolek [\textit{Journal of Combinatorial Theory, Series B}, 162 (2023) 231--243] to the case of hypergraphs. We show that $\text{ex}_r(n,K_s^r,\text{Berge-}F)\le \text{ex}_s(n,\text{Berge-}F)$ and present sufficient conditions for equality. We also consider the connected generalized Tur\'{a}n number for Berge paths.

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

1 major / 2 minor

Summary. The paper defines generalized Turán numbers ex_r(n, H, Berge-F) counting copies of an r-uniform hypergraph H in Berge-F-free r-graphs. It relates this quantity to the number of copies of the shadow graph sh(H) in ordinary F-free graphs. The central result states that for any fixed hypergraph H there exists K such that for all k > K the extremal value ex_r(n, H, Berge-K_k) is attained by the balanced complete (k-1)-partite r-graph; this generalizes the 2023 graph result of Morrison-Nir-Norin-Rzazewski-Wesolek. Additional results include the inequality ex_r(n, K_s^r, Berge-F) ≤ ex_s(n, Berge-F) together with sufficient conditions for equality, and a treatment of the connected generalized Turán number for Berge paths.

Significance. If the proofs are correct, the work supplies a clean extension of Turán theory from graphs to hypergraphs via the Berge and shadow-graph formalism. The fact that the balanced (k-1)-partite construction remains extremal for every H once k is large enough is a robust statement that strengthens the link between graph and hypergraph extremal problems. The shadow-graph reduction is a reusable technique whose correctness would be a genuine contribution.

major comments (1)
  1. [Proof of the generalization theorem (main result on Berge-K_k)] Proof of the main result on ex_r(n, H, Berge-K_k) for large k: the argument reduces the hypergraph count to the graph-Turán number ex(n, sh(H), K_k) and invokes the known extremal graph. This reduction is load-bearing for the claim that the balanced complete (k-1)-partite r-graph is optimal for arbitrary H. The manuscript must explicitly verify that no Berge-K_k-free r-graph can produce more copies of H than the Turán r-graph by selecting multiple hyperedges over the same shadow edges or by concentrating hyperedges on a proper subgraph of the underlying graph while still remaining Berge-K_k-free. Without a detailed accounting of the multiplicity of the shadow map, the equality case for general H remains unconfirmed.
minor comments (2)
  1. [Abstract] The abstract states that 'several exact results' are obtained but only sketches the main Berge-K_k theorem; a one-sentence indication of the other exact statements would improve readability.
  2. [Introduction / Preliminaries] The definition of the shadow graph sh(H) should be stated explicitly in the introduction or preliminaries before it is used in the reduction arguments.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed and insightful comments on our paper. We appreciate the recognition of the significance of our results and the suggestion for improvement in the proof presentation. Below, we address the major comment point by point.

read point-by-point responses

  1. Referee: [Proof of the generalization theorem (main result on Berge-K_k)] Proof of the main result on ex_r(n, H, Berge-K_k) for large k: the argument reduces the hypergraph count to the graph-Turán number ex(n, sh(H), K_k) and invokes the known extremal graph. This reduction is load-bearing for the claim that the balanced complete (k-1)-partite r-graph is optimal for arbitrary H. The manuscript must explicitly verify that no Berge-K_k-free r-graph can produce more copies of H than the Turán r-graph by selecting multiple hyperedges over the same shadow edges or by concentrating hyperedges on a proper subgraph of the underlying graph while still remaining Berge-K_k-free. Without a detailed accounting of the multiplicity of the shadow map, the equality case for general H remains unconfirmed.

    Authors: We agree that a more explicit verification is beneficial for clarity. In our proof, the key is that the shadow of any Berge-K_k-free r-graph is a K_k-free graph, and the number of H-copies in the r-graph is bounded by the number of sh(H)-copies in the shadow graph, with equality possible when there is at most one hyperedge per shadow edge in the relevant subgraphs. However, to address the concern about multiplicities and concentration on subgraphs, we will add a new subsection or paragraph in the revised manuscript that carefully analyzes the possible multiplicities. We will show that for k large enough (depending on H), any Berge-K_k-free r-graph with multiple hyperedges on the same shadow edges cannot exceed the count in the balanced Turán r-graph, because adding such multiples would require the underlying graph to have fewer edges or violate the freeness in a way that reduces the total copies. Similarly for concentrating on proper subgraphs: since the graph extremal is unique for large k by the cited result, the hypergraph version follows. This addition will confirm the optimality for arbitrary H. revision: yes

Circularity Check

0 steps flagged

No circularity: central claim reduces to external graph Turán theorem via independent shadow-graph bijection

full rationale

The paper defines Berge copies and the generalized ex_r(n, H, Berge-F) via a bijection between hyperedges and graph edges, then connects the count of H-copies in Berge-K_k-free r-graphs to the number of shadow-graph copies of H inside ordinary K_k-free graphs. For large k it invokes the known graph-Turán theorem on the shadow graph to conclude that the balanced complete (k-1)-partite r-graph is extremal. This step is a standard combinatorial reduction, not a self-definition, fitted parameter renamed as prediction, or load-bearing self-citation; the cited 2023 result is by unrelated authors and supplies an independent graph-level fact. No equation or construction in the given text collapses the claimed extremal function to its own inputs by definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on the standard definition of Berge copies and the classical Turán theorem for graphs; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • standard math Turán's theorem for graphs and its hypergraph analogues
    Implicitly used when relating shadow counts to F-free graphs and when claiming the balanced complete multipartite construction is extremal.

pith-pipeline@v0.9.0 · 5651 in / 1280 out tokens · 56791 ms · 2026-05-10T04:29:15.267373+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

28 extracted references · 28 canonical work pages

  1. [1]

    N. Alon, C. Shikhelman, ManyTcopies inH-free graphs,J. Combin. Theory Ser. B 121(2016) 146–172

    work page 2016

  2. [2]

    Axenovich, D

    M. Axenovich, D. Gerbner, D. Liu, B. Patk´ os, Tur´ an problems for simplicial complexes, arXiv preprint arXiv:2508.12763(2025)

    work page arXiv 2025

  3. [3]

    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

  4. [4]

    ”Avoiding long Berge cycles.” Journal of Combinatorial Theory, Series B 137 (2019): 55-64

    F¨ uredi, Zolt´ an, Alexandr Kostochka, and Ruth Luo. ”Avoiding long Berge cycles.” Journal of Combinatorial Theory, Series B 137 (2019): 55-64

    work page 2019

  5. [5]

    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

  6. [6]

    F¨ uredi, M

    Z. F¨ uredi, M. Simonovits, The history of degenerate (bipartite) extremal problems. Erd˝ os Centennial, Bolyai Society Math. Studies, vol.25, Springer, 169–264, 2013

    work page 2013

  7. [7]

    Gerbner, Some stability and exact results in generalized Tur´ an problems

    D. Gerbner, Some stability and exact results in generalized Tur´ an problems. Studia Scientiarum Mathematicarum Hungarica, 60(1), (2023) 16-26

    work page 2023

  8. [8]

    Gerbner, Some Exact Results for Non-Degenerate Generalized Tur´ an Problems

    D. Gerbner, Some Exact Results for Non-Degenerate Generalized Tur´ an Problems. The Electronic Journal of Combinatorics, (2023) P4-39

    work page 2023

  9. [9]

    Gerbner, On non-degenerate Berge-Tur´ an problems, Graphs and Combinatorics, 40(2), 2024, 37

    D. Gerbner, On non-degenerate Berge-Tur´ an problems, Graphs and Combinatorics, 40(2), 2024, 37

    work page 2024

  10. [10]

    Gerbner, On the extremal graphs in generalized Tur´ an problems

    D. Gerbner, On the extremal graphs in generalized Tur´ an problems. Discrete Mathe- matics, 347(6), 114021

    work page

  11. [11]

    Gerbner, On weakly Tur´ an-good graphs

    D. Gerbner, On weakly Tur´ an-good graphs. Discussiones Mathematicae Graph Theory, 44(4), 1539-1550

    work page

  12. [12]

    Gerbner and H

    D. Gerbner and H. H. Karim. Stability from graph symmetrization arguments in gen- eralized Tur´ an problems.Journal of Graph Theory, 107(4):681–692, 2024

    work page 2024

  13. [13]

    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

  14. [14]

    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

  15. [15]

    Gerbner, Z

    D. Gerbner, Z. L. Nagy, and M. Vizer. Unified approach to the generalized Tur´ an problem and supersaturation. Discrete Mathematics, 345(3):112743, 2022. 13

    work page 2022

  16. [16]

    Gerbner, C

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

    work page 2017

  17. [17]

    Gerbner, C

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

    work page 2019

  18. [18]

    Gerbner, C

    D. Gerbner, C. Palmer, Some exact results for generalized Tur´ an problems,European Journal of Combinatorics,103(2022) 103519

    work page 2022

  19. [19]

    Gerbner and C

    D. Gerbner, C. Palmer, Survey of generalized Tur´ an problems—counting subgraphs, arXiv preprint, arXiv: 2506.03418v1

    work page arXiv

  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]

    L. Kang, Z. Ni, E. Shan, The Tur´ an number of Berge-matching in hypergraphs,Discrete Mathematics,345(8) (2022) 112901

    work page 2022

  22. [22]

    Khormali, C

    O. Khormali, C. Palmer, Tur´ an numbers for hypergraph star forests,European Journal of Combinatorics,102(2022) 103506

    work page 2022

  23. [23]

    E. L. L. Liu, J. Wang, The maximum number of cliques in hypergraphs without large matchings,arXiv preprint arXiv:2005.01080(2020)

    work page arXiv 2005

  24. [24]

    Morrison, JD Nir, S

    N. Morrison, JD Nir, S. Norin, P. Rza˙ zewski, A. Wesolek. Every graph is eventually Tur´ an-good,Journal of Combinatorial Theory, Series B,162, 231-243, 2023

    work page 2023

  25. [25]

    Mubayi, J

    D. Mubayi, J. Verstra¨ ete, A survey of Tur´ an problems for expansions,Recent Trends in Combinatorics, (2016) 117–143

    work page 2016

  26. [26]

    Tur´ an, Egy gr´ afelm´ eleti sz´ els˝ o´ ert´ ekfeladatr´ ol,Mat

    P. Tur´ an, Egy gr´ afelm´ eleti sz´ els˝ o´ ert´ ekfeladatr´ ol,Mat. Fiz. Lapok,48(1941) 436–452

    work page 1941

  27. [27]

    Y. Wang, Z. Yang, X. Zhao, Y. Bai and J. Zhou, The Tur´ an number of Berge matchings. arXiv preprint arXiv:2510.05422

    work page arXiv

  28. [28]

    J. Zhou, X. Zhao, X. Yuan, On generalized Tur´ an problems for expansions,arXiv preprint, arXiv:2601.09244 14

    work page arXiv