REVIEW 14 references
A subquadratic bound for generalized Tur\'an numbers of odd cycles
T0 review · reviewed 2026-08-28 · deepseek-v4-flash
Pith's one-line read For all integers l > k ≥ 2, the maximum number of (2k+1)-cycles in an n-vertex graph with no cycles of length at most 2k and no (2l+1)-cycle is O(n^{2 - 1/(k(k+1)(l-k))}).
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
The key structural fact is that forbidding all even cycles up to length 2k makes the graph locally tree-like: between any two vertices there is at most one path of length at most k. Around each vertex v, the proof looks at the set of vertices at distance exactly k. Each cycle of length 2k+1 through v picks out an edge between two such far vertices, the edge opposite v. These opposite edges form an auxiliary graph L_v, and a random partition argument shows L_v is sparse, with average degree at most 4(l-k).
The proof then counts objects called flags: a cycle together with an attached path of length l-k at one of its vertices. Every cycle generates many flags, but each flag can be charged to an ordered pair of distinct vertices. A path-counting estimate bounds how many flags can be assigned to one pair. Comparing the lower and upper bounds on the total number of flags yields the desired upper bound on the number of cycles.
Extended reading notes
Core claim
Theorem 1.2 states that ex(n, C_{2k+1}, C_{2k} ∪ {C_{2l+1}}) = O_{k,l}( n^{2 - 1/(k(k+1)(l-k))} ) for every pair of integers l > k ≥ 2. Together with the known k = 1 case, this confirms Conjecture 1.1 of Gerbner, Győri, Methuku, and Vizer.
Load-bearing premise
The proof relies on the Alon-Hoory-Linial theorem (Theorem 2.1) that C_{2k}-free graphs have at most (1/2)n^{1+1/k} + (1/2)n edges. This bound is applied at (6) to control m and again in the final substitution in the proof of Theorem 1.2; the claimed subquadratic exponent 2 - 1/(k(k+1)(l-k)) is derived directly from it. If this edge bound had a larger exponent, the argument would not yield a subquadratic result. The proof also uses the Erdős-Gallai theorem (Theorem 2.2) in Lemma 2.3. Both are standard published results, so the practical risk is low, but they are the load-bearing external inputs.
Formalized claims in Lean
-
Claim #1: Theorem 1.2 states that ex(n, C_{2k+1}, C_{2k} ∪ {C_{2l+1}}) = O_{k,l}( n^{2 - 1/(k(k+1)(l-k))} ) for every pair of integers l > k ≥ 2. Together with the known k = 1 case, this confirms Conjecture 1.1 of Gerbner, Győri, Methuku, and Vizer.
/-- @claim 1 Theorem 1.2 states that ex(n, C_{2k+1}, C_{2k} ∪ {C_{2l+1}}) = O_{k,l}( n^{2 - 1/(k(k+1)(l-k))} ) for every pair of integers l > k ≥ 2. Together with the known k = 1 case, this confirms Conjecture 1.1 of Gerbner, Győri, Methuku, and Vizer. -/ def central_claim : Prop :=
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Assumptions & free parameters
assumptions (3)
- standard math ex(n, C_{2k}) < (1/2)n^{1+1/k} + (1/2)n (Alon, Hoory, Linial, Theorem 2.1)
- standard math A graph on N vertices with no P_r has at most (r-2)N/2 edges (Erdős, Gallai, Theorem 2.2)
- domain assumption All graphs are finite and simple
Cite this review
Pith. "Pith review of A subquadratic bound for generalized Tur\'an numbers of odd cycles." pith.science (2026). https://pith.science/paper/E4BAH5Q5
@misc{pith2026260822893,
author = {Pith},
title = {Pith review of: A subquadratic bound for generalized Tur\'an numbers of odd cycles},
year = {2026},
howpublished = {\url{https://pith.science/paper/E4BAH5Q5}},
note = {Machine review of arXiv:2608.22893}
}
abstract
For a graph $H$ and a family of graphs $\mathcal F$, let $\text{ex}(n,H,\mathcal F)$ denote the maximum number of copies of $H$ in an $\mathcal F$-free graph on $n$ vertices. For every integer $i\ge 3$, let $C_i$ denote the cycle of length $i$. For $r\ge 3$, set $\mathscr {C}_r=\{C_3,C_4,\ldots,C_r\},$ and set $\mathscr {C}_2=\varnothing$. In this paper, we prove that, for all integers $l>k\ge 2$, $$ \text{ex}(n,C_{2k+1},\mathscr {C}_{2k}\cup\{C_{2l+1}\}) =O_{k,l} \left(n^{2-\frac{1}{k(k+1)(l-k)}}\ \ \right). $$ Together with the known upper bounds for the number of triangles in $C_{2l+1}$-free graphs, this confirms a conjecture of Gerbner, Gy\H{o}ri, Methuku, and Vizer.
Reference graph
Works this paper leans on
-
[1]
N. Alon, S. Hoory, and N. Linial, The Moore bound for irregular graphs,Graphs Combin.18(2002), 53–57
work page 2002
-
[2]
N. Alon and C. Shikhelman, ManyT copies inH-free graphs,J. Combin. Theory Ser. B121(2016), 146–172
work page 2016
-
[3]
C. Beke and O. Janzer, On the generalized Turán problem for odd cycles,SIAM J. Discrete Math.38(2024), 2416–2428
work page 2024
-
[4]
B. Bollobás and E. Győri, Pentagons vs. triangles,Discrete Math.308(2008), 4332– 4336
work page 2008
-
[5]
J. A. Bondy and M. Simonovits, Cycles of even length in graphs,J. Combin. Theory Ser. B16(1974), 97–105
work page 1974
-
[6]
P. Erdős, Extremal problems in graph theory, inTheory of Graphs and Its Applications, Publishing House of the Czechoslovak Academy of Sciences, Prague, 1964, 29–36
work page 1964
-
[7]
Erdős and T
P. Erdős and T. Gallai, On maximal paths and circuits of graphs,Acta Math. Acad. Sci. Hungar.10(1959), 337–356
1959
-
[8]
D. Gerbner, E. Győri, A. Methuku, and M. Vizer, Generalized Turán problems for even cycles,J. Combin. Theory Ser. B145(2020), 169–213
work page 2020
Show all 14 references
-
[9]
Gerbner and C
D. Gerbner and C. Palmer, Survey of generalized Turán problems—counting subgraphs, Electron. J. Combin., Dynamic Surveys, #DS27 (2026). 8
2026
-
[10]
Gishboliner and A
L. Gishboliner and A. Shapira, A generalized Turán problem and its applications,Int. Math. Res. Not. IMRN(2020), 3417–3452
2020
-
[11]
Grzesik and B
A. Grzesik and B. Kielak, On the maximum number of odd cycles in graphs without smaller odd cycles,J. Graph Theory99(2022), 240–246
2022
-
[12]
Győri and H
E. Győri and H. Li, The maximum number of triangles inC2k+1-free graphs,Combin. Probab. Comput.21(2012), 187–191
2012
-
[13]
Lazebnik, V
F. Lazebnik, V. A. Ustimenko, and A. J. Woldar, Polarities and2k-cycle-free graphs, Discrete Math.197/198(1999), 503–513
1999
-
[14]
A. A. Zykov, On some properties of linear complexes,Mat. Sb. (N.S.)24(66)(1949), 163–188. 9
1949
Reviewed August 28, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.