pith. sign in

arxiv: 2604.06357 · v1 · submitted 2026-04-07 · 🧮 math.CO

Helly Theorems for Generalized Tur\'an Problems

Sean English , Sam Spiro This is my paper

Pith reviewed 2026-05-10 18:40 UTC · model grok-4.3

classification 🧮 math.CO
keywords generalized Turán numbersHelly theoremextremal graph theorytreesforbidden subgraphsdichotomycopy counting
0
0 comments X

The pith

For any tree T and forbidden family F, the maximum number of T-copies in an F-free n-vertex graph is either at least order n to the k+1 or at most order of the ordinary ex(n,F) to the k.

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

The paper proves a dichotomy theorem for generalized Turán numbers when the target graph is a tree. Given any tree T, any family F of graphs to avoid, and any positive integer k, the quantity ex(n,T,F) is either at least on the order of n raised to k+1 or at most on the order of the ordinary Turán number ex(n,F) raised to the k. The argument proceeds by establishing new intersection theorems of Helly type that hold specifically for trees and then using those theorems to control how copies of T can be distributed in F-free graphs. A reader would care because the result supplies a uniform way to decide the asymptotic growth rate of ex(n,T,F) across many different choices of T and F instead of treating each pair separately. The work also marks the first use of Helly-type theorems inside Turán-type extremal problems.

Core claim

We prove a general theorem which states that for any tree T, any family F, and any integer k, either ex(n,T,F) is at least Ω(n^{k+1}) or at most O(ex(n,F)^k). Our proofs rely on new variants of the classical Helly Theorem for trees which may be of independent interest.

What carries the argument

New variants of the Helly theorem that hold for trees, used to establish the stated dichotomy for the generalized Turán function ex(n,T,F).

If this is right

  • For every tree T and family F the growth rate of ex(n,T,F) is forced into one of two sharply separated regimes determined by the ordinary Turán number ex(n,F).
  • Many concrete generalized Turán problems for tree targets can be resolved by checking which side of the dichotomy holds rather than computing the extremal function directly.
  • The Helly-type theorems for trees supply a new tool that can be applied to other counting problems in extremal graph theory involving tree embeddings.

Where Pith is reading between the lines

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

  • If analogous Helly theorems exist for other graph classes such as bipartite graphs with bounded degree, the same style of dichotomy might hold beyond trees.
  • The result suggests a way to obtain asymptotic classification for hypergraph Turán numbers when the target is a tree-like structure.
  • One could test whether the constants hidden in the O and Ω notations can be made explicit for small k.

Load-bearing premise

The dichotomy applies only when the target graph T is a tree, because the new Helly-type theorems are proved for trees.

What would settle it

A single counterexample consisting of one tree T, one family F, and one integer k for which the extremal value ex(n,T,F) grows asymptotically faster than any constant multiple of ex(n,F)^k yet slower than any positive multiple of n^{k+1}.

Figures

Figures reproduced from arXiv: 2604.06357 by Sam Spiro, Sean English.

Figure 1
Figure 1. Figure 1: An example of the graph H4 R from Definition 1 when H is the path on 6 vertices and R consists of the set of red vertices in Figure 1a. H4 R is a member of the family F 4 H,3 since H − R has (at least) three connected components. Theorem 1.4. Let T be a tree and F a family with ex(n, F) = O(n 1+ϵ ). If ex(n, T, F) > 0 for all sufficiently large n, then there exists an integer k such that ex(n, T, F) = Ω(n … view at source ↗
Figure 2
Figure 2. Figure 2: A depiction of (P5) 3 {xˆ3,xˆ4} . Observe that each copy of P5 in this graph can be identified by specifying which edges plays the role of ˆx1xˆ2 and ˆx4xˆ5. In the proof above, it is critical that we specify the edge of G playing the role of ˆx4xˆ5, as even if we specify every other edge of a copy of P5, there would still exist n ways to extend these specified edges into distinct copies of P5 in G. More g… view at source ↗
Figure 3
Figure 3. Figure 3: Finding a copy of F q Pt,k+1 in Case 1 of Lemma 5.11. The graph-image of one ϕ (p) is shown in blue. We emphasize this last step is well-defined since r2k−1 = t − 2 implies t − 2 ∈ [ℓ2k−1, r2k−1] = V (T2k−1) and hence lies in the domain of ψ (q+p) 2k−1 . Since Φt−1 is distinguishing and by our choices of the ψ (p) i ’s, the collection {ϕ (p) | p ∈ [q]} consists of monomorphisms of Pt into G such that each … view at source ↗
Figure 4
Figure 4. Figure 4: Finding a copy of F q Pt,k+1 in Case 2 of Lemma 5.11. The graph-image of one ϕ (p) is shown in blue. non-empty subgraph of T2k which in particular includes ℓ2k = r2k−1 + 1. Thus, the union of the graph-images of the ϕ (p) ’s constitutes a copy of F q Pt,k+1 in G. See [PITH_FULL_IMAGE:figures/full_fig_p028_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Finding a copy of F q Pt,k+1 in Lemma 5.12. The graph-image of one ϕ (p) is shown in blue. by T2s for s ∈ [m], and k − m given by T2s+1) for s ∈ [k − 1] \ [m − 1]. Taken together the graph-images of the ϕ (p) ’s yield a copy of F q Pt,k+1 in G. See [PITH_FULL_IMAGE:figures/full_fig_p029_5.png] view at source ↗
read the original abstract

Given a graph $T$ and a family of graphs $\mathcal{F}$, the generalized Tur\'an number $\mathrm{ex}(n,T,\mathcal{F})$ is the maximum number of copies of $T$ in an $n$-vertex $\mathcal{F}$-free graph. We prove a general theorem which states that for any tree $T$, any family $\mathcal{F}$, and any integer $k$, either $\mathrm{ex}(n,T,\mathcal{F})$ is at least $\Omega(n^{k+1})$ or at most $O(\mathrm{ex}(n,\mathcal{F})^{k})$, from which we derive a number of consequences. Our proofs rely on new variants of the classical Helly Theorem for trees which may be of independent interest. As far as we are aware, this is the first known application of Helly theorems for Tur\'an type problems.

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 / 2 minor

Summary. The manuscript proves a general dichotomy theorem for generalized Turán numbers: for any tree T, any family of graphs F, and any positive integer k, either ex(n,T,F) is at least Ω(n^{k+1}) or at most O(ex(n,F)^k). The proof relies on new Helly-type intersection theorems specialized to trees that control the distribution of T-copies inside F-free graphs. Several consequences are derived from the main result, and the authors note that this constitutes the first application of Helly theorems to Turán-type problems.

Significance. If the central claim holds, the result supplies a clean, parameter-light classification of growth rates for the number of copies of a tree T in F-free graphs. The new tree-specific Helly variants are of potential independent interest and represent a novel proof technique in extremal graph theory. The dichotomy is falsifiable and applies uniformly across all families F, which strengthens its utility as a general tool.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'a number of consequences' is used without naming them; listing the principal corollaries (even briefly) would improve the abstract's informativeness.
  2. [Introduction] The manuscript should clarify in the introduction whether the Helly variants require T to be a tree only for the intersection property or also for the counting argument that yields the Ω(n^{k+1}) lower bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation for minor revision. No specific major comments appear in the report, so we have no individual points to address point by point. We will incorporate any minor suggestions into the revised version.

Circularity Check

0 steps flagged

No significant circularity; proof-based theorem with new Helly variants

full rationale

The paper claims a dichotomy for ex(n,T,F) when T is any tree: either Ω(n^{k+1}) or O(ex(n,F)^k). This is derived from newly proved Helly-type intersection theorems specialized to trees, which are presented as original contributions of independent interest rather than imported or fitted. No equations, parameter fits, self-citations as load-bearing premises, or renamings of known results appear in the abstract or description that would reduce the central claim to its inputs by construction. The tree restriction is explicit in the hypothesis. The derivation chain is self-contained as a standard mathematical proof.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Insufficient information from abstract only; no free parameters, axioms, or invented entities are detailed.

pith-pipeline@v0.9.0 · 5435 in / 1012 out tokens · 34147 ms · 2026-05-10T18:40:58.701340+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

25 extracted references · 25 canonical work pages

  1. [1]

    Alon and C

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

    work page 2016

  2. [2]

    Alweiss, S

    R. Alweiss, S. Lovett, K. Wu, and J. Zhang,Improved bounds for the sunflower lemma, Ann. of Math. (2)194(2021), no. 3, 795–815

    work page 2021

  3. [3]

    Hans-J¨ urgen Bandelt and Erich Prisner,Clique graphs and Helly graphs, J. Comb. Theory, Ser. B51(1991), no. 1, 34–45

    work page 1991

  4. [4]

    Imre B´ ar´ any and Gil Kalai,Helly-type problems, Bull. Am. Math. Soc., New Ser.59(2022), no. 4, 471–502

    work page 2022

  5. [5]

    Imre B´ ar´ any, Meir Katchalski, and Janos Pach,Quantitative Helly-type theorems, Proc. Am. Math. Soc.86(1982), 109–114

    work page 1982

  6. [6]

    Math.174(2003), no

    Imre B´ ar´ any and Jiˇ r´ ı Matouˇ sek,A fractional Helly theorem for convex lattice sets, Adv. Math.174(2003), no. 2, 227–235

    work page 2003

  7. [7]

    Bondy and M

    J. Bondy and M. Simonovits,Cycles of even length in graphs, J. Comb. Theory, Ser. B16 (1974), 97–105

    work page 1974

  8. [8]

    Bukh and D

    B. Bukh and D. Conlon,Rational exponents in extremal graph theory, J. Eur. Math. Soc. (JEMS)20(2018), no. 7, 1747–1757

    work page 2018

  9. [9]

    Cambie, R

    S. Cambie, R. de Joannis de Verclos, and R. Kang,Regular Tur´ an numbers and some Gan-Loh-Sudakov-type problems, J. Graph Theory102(2023), no. 1, 67–85

    work page 2023

  10. [10]

    Z. Dong, J. Gao, and H. Liu,Bipartite Tur´ an problems via graph gluing, Bull. Lond. Math. Soc.57(2025), no. 12, 3783–3796

    work page 2025

  11. [11]

    F¨ uredi and A

    Z. F¨ uredi and A. K¨ undgen,Moments of graphs in monotone families, J. Graph Theory51 (2006), no. 1, 37–48

    work page 2006

  12. [12]

    F¨ uredi and M

    Z. F¨ uredi and M. Simonovits,The history of degenerate (bipartite) extremal graph problems, Erd¨ os centennial, Bolyai Soc. Math. Stud., vol. 25, J´ anos Bolyai Math. Soc., Budapest, 2013, pp. 169–264

    work page 2013

  13. [13]

    Gerbner,Generalized Tur´ an problems forK 2,t, Electron

    D. Gerbner,Generalized Tur´ an problems forK 2,t, Electron. J. Combin.30(2023), no. 1, Paper No. 1.34, 9

    work page 2023

  14. [14]

    Gerbner, E

    D. Gerbner, E. Gy˝ ori, A. Methuku, and M. Vizer,Generalized Tur´ an problems for even cycles, J. Combin. Theory Ser. B145(2020), 169–213

    work page 2020

  15. [15]

    Gerbner and C

    D. Gerbner and C. Palmer,Survey of generalized tur´ an problems – counting subgraphs, arXiv:2506.03418 (2025)

    work page arXiv 2025

  16. [16]

    Gerbner and B

    D. Gerbner and B. Patk´ os,Generalized Tur´ an problems for complete bipartite graphs, Graphs Combin.38(2022), no. 5, Paper No. 164, 20. 31

    work page 2022

  17. [17]

    Halfpap and C

    A. Halfpap and C. Palmer,On supersaturation and stability for generalized Tur´ an problems, J. Graph Theory97(2021), no. 2, 232–240

    work page 2021

  18. [18]

    Helly, ¨Uber Mengen konvexer K¨ orper mit gemeinschaftlichen Punkten., Jahresber

    Ed. Helly, ¨Uber Mengen konvexer K¨ orper mit gemeinschaftlichen Punkten., Jahresber. Dtsch. Math.-Ver.32(1923), 175–176 (German)

    work page 1923

  19. [19]

    Math.191(2005), no

    Gil Kalai and Roy Meshulam,A topological colorful Helly theorem, Adv. Math.191(2005), no. 2, 305–311

    work page 2005

  20. [20]

    Lesniak,On longest paths in connected graphs, Fundam

    L. Lesniak,On longest paths in connected graphs, Fundam. Math.86(1975), 283–286

    work page 1975

  21. [21]

    Letzter,Many H-copies in graphs with a forbidden tree, SIAM J

    S. Letzter,Many H-copies in graphs with a forbidden tree, SIAM J. Discrete Math.33 (2019), no. 4, 2360–2368

    work page 2019

  22. [22]

    J. Ma, X. Yuan, and M. Zhang,Some extremal results on complete degenerate hypergraphs, J. Combin. Theory Ser. A154(2018), 598–609

    work page 2018

  23. [23]

    Erd˝ os and R

    P. Erd˝ os and R. Rado,Intersection theorems for systems of sets, J. London Math. Soc.35 (1960), 85–90

    work page 1960

  24. [24]

    Spiro,Random polynomial graphs for random Tur´ an problems, J

    S. Spiro,Random polynomial graphs for random Tur´ an problems, J. Graph Theory105 (2024), no. 2, 192–208

    work page 2024

  25. [25]

    X. Zhu, E. Gy˝ ori, Z. He, Z. Lv, N. Salia, and C. Xiao,Stability version of Dirac’s theorem and its applications for generalized Tur´ an problems, Bull. Lond. Math. Soc.55(2023), no. 4, 1857–1873. A Tightness for Paths In this appendix we verify that Theorems 1.3 and 1.10 are tight for paths of certain lengths. More generally, we show the following in th...

    work page 2023