Tur\'an numbers of cycles plus a general graph

Chunyang Dou; Fu-Tao Hu; Xing Peng

REVIEW 3 major objections 4 minor 1 cited by

Tur\'an numbers of cycles plus a general graph

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper determines the Turán number of the family $C_{\ge k}\cup\{F\}$ up to an additive constant for any 2-connected $F$ with $p(F)\ge \lfloor (k-1)/2\rfloor+1$, extending the clique case.

desk verdict A solid extension of the clique case to general 2-connected F; the k>=6 results look right, but the k=4 case in Theorem 6 has a false claim that needs fixing. read the letter →

arxiv 2411.17322 v2 pith:ZANDASPW submitted 2024-11-26 math.CO

Chunyang Dou , Fu-tao Hu , Xing Peng This is my paper · ORCID

classification math.CO MSC 05C3505C3805C40

keywords Turánnumberextremalgraphcycle2-connectedbipartitevertexcoverErdős-Gallaitheoremcircumference

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper determines, up to an additive constant, the maximum number of edges in an $n$-vertex graph that contains neither a cycle of length at least $k$ nor a copy of a fixed 2-connected graph $F$, for all sufficiently large $n$. The answer is governed by the larger of two densities: the edge density imposed by the cycle restriction alone, and the edge density of the best $(k-1)$-vertex graph with no copy of $F$. For odd $k$ the first density always dominates, and for even $k$ both compete. The result holds when $F$ is nonbipartite or when $F$ is bipartite with a vertex-cover colour class parameter $p(F)\ge \lfloor (k-1)/2\rfloor+1$, and it extends an earlier exact result for $F$ being a clique. A sympathetic reader should care because it turns a two-constraint extremal problem into a comparison of two simple quantities for a broad class of forbidden graphs.

What carries the argument

The load-bearing technical object is a strengthened classical inequality for longest cycles (Lemma 3): if $C$ is a longest cycle of length $c$ in a 2-connected graph $G$, and $A$ is the set of vertices outside $C$ having $\lfloor c/2\rfloor$ neighbours on $C$, then $e(G-C)+e(G-C,C)\le \lfloor c/2\rfloor|A|+(\lfloor c/2\rfloor-\frac12)(n-c-|A|)$. This is proved from a two-case bound from the authors' earlier work and from the assertion that $G-A$ remains 2-connected. The second ingredient (Lemma 4) caps the edges inside the cycle: once $|A|$ is large enough, the neighbour set $L$ of a vertex in $A$ must be $H$-free, where $H$ is the family of subgraphs of $F$ induced by vertex covers, giving $e(G[C])\le \mathrm{ex}(t,H)+t^2$ for even $c$ and $e(G[C])\le \mathrm{ex}(t,H)+t(t+1)+1$ for odd $c$, with $t=\lfloor (k-1)/2\rfloor$; in the odd case the inequality is strict when every extremal $t$-vertex $H$-free graph contains one of the graphs $H'=\{F-\{u,v\}:uv\in E(F)\}$. For Theorem 6 the remaining work is a block decomposition: every block has longest cycle at most $k-1$, and each block is charged either at density $\frac{k-2}{2}$ per vertex or at density $\frac{\mathrm{ex}(k-1,F)}{k-2}$, so the maximum of the two densities bounds the whole graph.

What would settle it

Take any 2-connected graph $G$ with a longest cycle $C$ of length $c$ ($4\le c\le n-1$) and let $A$ be the set of vertices outside $C$ with $\lfloor c/2\rfloor$ neighbours on $C$; if $e(G-C)+e(G-C,C)>\lfloor c/2\rfloor|A|+(\lfloor c/2\rfloor-\frac12)(n-c-|A|)$, or if $G-A$ is not 2-connected, then Lemma 3 fails and with it the upper-bound proofs of Theorems 4, 5 and 6.

Watch

Extended reading notes

Core claim

Let $C_{\ge k}$ be the family of cycles of length at least $k$, and let $F$ be a 2-connected graph with $p(F)\ge \lfloor (k-1)/2\rfloor+1$, where $p(F)$ is the smallest possible colour class size in a proper 2-colouring of $F[S]$ as $S$ ranges over vertex covers of $F$, and $p(F)=\infty$ for nonbipartite $F$. Writing $\mathrm{ex}(n,\{C_{\ge k},F\})$ for the maximum number of edges in an $n$-vertex graph with no such cycle and no copy of $F$, the paper proves that for sufficiently large $n$, $\mathrm{ex}(n,\{C_{\ge k},F\})=\frac{k-1}{2}n+O_k(1)$ when $k$ is odd, and $\mathrm{ex}(n,\{C_{\ge k},F\})=n\max\{\frac{k-2}{2},\frac{\mathrm{ex}(k-1,F)}{k-2}\}+O_k(1)$ when $k$ is even. The proof first solves the 2-connected version: $\mathrm{ex}_{2\text{-conn}}(n,\{C_{\ge k},F\})=\mathrm{ex}(t,H)+t(n-t)$ for odd $k$, and the same plus an integer $\ell\in\{0,1\}$ for even $k$, where $t=\lfloor (k-1)/2\rfloor$ and $H$ is the family of induced subgraphs of $F$ on vertex covers. The even-$k$ formula then follows by decomposing an extremal graph into blocks and charging each block against one of the two densities.

Load-bearing premise

The proofs of Theorems 4 and 5 rest on the inequality in Lemma 3, which is inherited from a previous two-case bound and on the claim that deleting the set $A$ of outside vertices with the most neighbours on a longest cycle leaves a 2-connected graph; if either the transferred inequality or the 2-connectivity claim fails, the main upper bounds collapse.

Editorial extensions

If this is right

For every 2-connected nonbipartite $F$ and every even $k\ge 6$, forbidding all cycles of length at least $k$ and copies of $F$ costs exactly $n\max\{\frac{k-2}{2},\frac{\mathrm{ex}(k-1,F)}{k-2}\}+O(1)$ edges, so the extremal density is one of two explicit numbers.
For odd $k$, the cycle constraint alone is decisive: $\mathrm{ex}(n,\{C_{\ge k},F\})=\frac{k-1}{2}n+O(1)$ for every $F$ satisfying the $p(F)$ condition.
The 2-connected version of the problem is solved almost exactly: $\mathrm{ex}_{2\text{-conn}}(n,F)=\mathrm{ex}(t,H)+t(n-t)+\ell$ with $\ell\in\{0,1\}$, and $\ell=0$ whenever every extremal $t$-vertex $H$-free graph contains a member of $H'$.
The upper bound in Theorem 6 does not actually require $F$ to be 2-connected, so the displayed upper bound holds for all graphs $F$, while the lower bound needs 2-connectivity.
The result extends the earlier exact determination for $F=K_r$ to a general 2-connected $F$ under the $p(F)$ balance condition, so the same comparison-of-densities phenomenon is universal.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The authors leave implicit a stability statement: near-extremal graphs for even $k$ should be either split-like graphs $T \vee I_{n-t}$ with $T \in \mathrm{EX}(t,H)$ or windmills of $(k-1)$-vertex $F$-free blocks joined at a cut vertex; proving this would turn the asymptotic formula into a structural one.
For non-2-connected $F$, the paper leaves a gap between the general upper bound and the windmill lower bound when $\frac{\mathrm{ex}(k-1,F)}{k-2}>\frac{k-2}{2}$; a natural test is whether the windmill construction still attains the lower bound for such $F$.
The $p(F)$ condition is deployed only through the cycle-edge lemma, so any weakening of that lemma would automatically enlarge the family of bipartite graphs for which the exact asymptotic formula holds.
One could probe the sharpness of the $O(1)$ term by computing the even-$k$ additive constant $\ell$ in the 2-connected theorem for small parameters; the paper leaves open whether $\ell=1$ ever occurs.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The short version: this paper generalizes the known ex(n,{C>=k,K_r}) results to ex(n,{C>=k,F}) for any 2-connected F with p(F) >= floor((k-1)/2)+1, up to O_k(1). For odd k the answer is boring (t n + O(1)); for even k you get the two-term max formula involving ex(k-1,F). The framework via H and p(F) is a clean way to package the reduction, and the main upper-bound machinery is a direct but competent extension of Dou-Ning-Peng [5]. I checked the chain of inequalities in Theorems 4-6 for k>=6 and they hold. Lemma 3, which the paper leans on, is fine: the recent stress-test worry about a dropped e(G[A]) does not land, because the proof first establishes N_{G1}(u)=0 for every u in A, which forces A to be independent and to have no edges to G'-C; the identity is then exact. The assertion that G' stays 2-connected is terse but true.

The real flaw is in the k=4 case of Theorem 6. The proof says a friendship graph is F-free; that is false when F=K3, which is an allowed F. The formula still holds (for F=K3 the max is 1 and a star gives the lower bound), so the error is localized and repairable, but as written the proof of that case does not establish the claim. A referee should ask for a corrected lower-bound argument for triangle-containing F.

Minor issues: a typo in the proof of Theorem 6 where ex(k-1,H) should be ex(k-1,F), and a garbled line "t = floor((k-1)/2) = t-2/2". Also the self-citation to Lemma 2 from [5] is not circular; they prove a strengthening here.

Who is this for? Extremal graph theorists working on generalized Turán problems. It is a useful, expected generalization rather than a breakthrough, but it clears up a natural open case and the reduction to finite ex values is elegant. I would send it to a competent referee. The k=4 fix should be requested, and the exposition around Lemma 3 could be expanded, but neither issue undermines the k>=6 theorems.

My recommendation: engage with it; accept for review with a request for a corrected k=4 argument.

Referee Report

3 major / 4 minor

Summary. The paper studies the Turán number ex(n,{C_{\ge k},F}) for a fixed 2-connected graph F with p(F) \ge \lfloor(k-1)/2\rfloor+1. The main results are Theorem 4 (odd k, 2-connected extremal number equals ex(t,H)+t(n-t)), Theorem 5 (even k, same formula up to an additive 0/1 term), and Theorem 6 (general asymptotic ex(n,{C_{\ge k},F}) = n\max\{(k-2)/2, ex(k-1,F)/(k-2)\} + O_k(1)). The proofs rely on a strengthening of Bondy's lemma (Lemma 3), a structural estimate on the edges of a longest cycle (Lemma 4), and a block decomposition argument. The paper also discusses extensions and relations to the path-plus-clique problem.

Significance. If the proofs are completed, this is a substantial extension of the earlier clique case of Dou--Ning--Peng [5] to a general 2-connected graph F. The asymptotic formula is clean and parameter-free, and the paper supplies explicit extremal constructions, including a block-based upper bound that reduces the problem to the finite quantity ex(k-1,F). The main weaknesses are localized gaps: Lemma 3 omits an edge-count term, the k=4 case of Theorem 6 contains a false assertion about friendship graphs, and the connectivity reduction in Theorem 6 is not justified as written. These issues appear repairable, but they currently affect load-bearing parts of the argument.

major comments (3)

[Section 2, Lemma 3] After proving N_{G-C}(u)=0 for each u\in A, the proof sets G'=G-A and asserts e(G-C)+e(G-C,C)=t|A|+e(G'-C)+e(G'-C,C). This equality is not justified: the left side also contains e(G[A]), which has not been shown to vanish. If A is not independent, the claimed upper bound fails by e(A). The subsequent assertion that G' is 2-connected also needs a real proof, since deleting all vertices of A could expose a cut vertex on C even though each vertex of A has no neighbors in G-C. Lemma 3 is used in Lemma 5 and in the upper-bound proofs of Theorems 4-6, so this gap is load-bearing for all main results.
[Section 4, proof of Theorem 6, k=4 case] The statement 'a friendship graph is F-free' is false when F=K3, because the friendship graph contains triangles; K3 is 2-connected and nonbipartite, hence p(F)=\infty and satisfies the hypothesis. The lower bound for K3 can be recovered from a tree, which is both triangle-free and C_{\ge4}-free, but the printed justification is wrong and must be replaced. The same sentence should also clarify for which F the friendship construction is actually valid.
[Section 4, Theorem 6 upper bound] The sentence 'As both F and C_{\ge k} are 2-connected, we may assume G is connected' is not a valid statement about the family C_{\ge k}. The connectivity reduction is in fact true for the intended reason (adding one edge between two components creates neither a copy of the 2-connected F nor a cycle), but this needs to be argued explicitly. The identity \sum_{i=1}^w (b_i-1)=n-1 used later depends on connectedness, so as written the upper-bound proof has a gap for disconnected graphs.

minor comments (4)

[Section 4, proof of Theorem 6] The first line contains a typo: 't = \lfloor(k-1)/2\rfloor = t-2/2' should read 't = (k-2)/2' in the even-k case.
[Section 4, upper-bound estimate] In the case split, one occurrence reads 'ex(k-1,H)' where the surrounding formula uses 'ex(k-1,F)'; this should be corrected to ex(k-1,F).
[Section 3, proof of Theorem 5] There is a duplicated inequality sign '\le\le' in the displayed estimate for c=k-2; this is a typographical error.
[Section 2, Lemma 4(2)] The strictness argument says 'Otherwise, the subgraph of G induced by L\cup\{v_2,v_3\} contains F as a subgraph'; this only follows under the equality conditions (G[L] in EX(t,H), complete bipartite between L and R, and v_2v_3 present), so the sentence should be rephrased to make the equality case explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main Turán bounds are derived from independent technical lemmas and explicit constructions, not from the target formula.

full rationale

The paper's main upper bounds rely on Lemma 3, which invokes Lemma 2 from Dou-Ning-Peng (arXiv:2410.06449), a paper sharing two authors with this one. This is a genuine self-citation, but it is not circular: Lemma 2 is a distinct, parameter-free bound on e(G-C)+e(G-C,C) for 2-connected graphs whose assumptions do not include the target ex(n,{C>=k,F}) formula, and the current paper states a strengthening (Lemma 3) rather than identifying its result with the cited lemma. The definitions H and p(F) are structural parameters used to state the theorems; no fitted constant is later relabelled as a prediction. In Theorem 6, the term ex(k-1,F) is the ordinary Turán number of F on k-1 vertices appearing in the block-sum lower and upper estimates; it is an input to the formula, not an output obtained from the same derivation. Lower-bound constructions are explicit (T∨I and block-sharing copies of F1), and the upper bounds are compared against those constructions, so the formula is not true by definition. The most serious issue found is a technical gap in the proof of Lemma 3, where the equality after 'Therefore' appears to omit e(G[A]) when passing from G to G' = G - A; this is a correctness defect in the manuscript, not a circularity. Consequently, no circular step can be identified.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted constants or new entities. The parameter p(F) and the graph families H and H' are definitions, not empirical inputs. All assumptions are standard graph-theoretic theorems or prior lemmas; the most load-bearing is Lemma 2 from the authors' own [5].

assumptions (4)

standard math Erdos-Gallai Theorem: ex(n,C>=k) <= (k-1)(n-1)/2
Used as the baseline upper bound throughout, cited as Theorem 1.
standard math Bondy's Lemma: e(G-C)+e(G-C,C) <= floor(c/2)(n-c)
Used in Lemma 1 and as a base for the strengthened Lemma 3.
domain assumption Lemma 2 from [5] (stability version for 2-connected graphs)
Inherited from the authors' earlier work on {C>=k,K_r}; the current Lemma 3 strengthens it and the upper bounds rely on it.
standard math Fact 1: vertices outside a longest cycle have at most floor(c/2) neighbors on the cycle
Used to define A_{floor(c/2)} and in the proof of Lemma 4.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tur\'an numbers of cycles plus a general graph." pith.science (2026). https://pith.science/paper/ZANDASPW

@misc{pith2026241117322,
  author       = {Pith},
  title        = {Pith review of: Tur\'an numbers of cycles plus a general graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZANDASPW}},
  note         = {Machine review of arXiv:2411.17322}
}

abstract

For a family of graphs $\cal F$, a graph $G$ is $\cal F$-free if it does not contain a member of $\cal F$ as a subgraph. The Tur\'an number $\textrm{ex}(n,{\cal F})$ is the maximum number of edges in an $n$-vertex graph which is $\cal F$-free. Let ${\cal C}_{\geq k}$ be the set of cycles with length at least $k$. In this paper, we investigate the Tur\'an number of $\{{\cal C}_{\geq k}, F\}$ for a general graph $F$. To be precise, we determine $\textrm{ex}(n, \{{\cal C}_{\geq k}, F\})$ apart from a constant additive term, where $F$ either is a 2-connected nonbipartite graph or is a 2-connected bipartite graph under some conditions. This is an extension of a previous result on the Tur\'an number of $\{{\cal C}_{\geq k}, K_r\}$ by the first author, Ning, and the third author.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Spectral extremal problems for degenerate graphs
math.CO 2025-07 conditional novelty 7.0 of 10

For finite degenerate graph families with linear ex(n,F), the spectral extremal graph is characterized by the independent covering number β'(F) and the induced family H(F).

Reference graph

Works this paper leans on

19 extracted references · 15 canonical work pages · cited by 1 Pith paper

[5]

C. Dou, B. Ning, and X. Peng, The number of edges in graphs with b ounded clique number and circumference, arXiv:2410.06449. 10

arXiv
[1]

Abbott, D

H. Abbott, D. Hanson, and H. Sauer, Intersection theorems f or systems of sets, J. Com- bin. Theory Ser. A, 12 (1972), 381–389

work page 1972
[2]

Alon and F

N. Alon and F. Frankl, Tur´ an graphs with bounded matching numb er, J. Combin. The- ory Ser. B, 165 (2024), 223–229

work page 2024
[3]

Bondy, Large cycles in graphs, Discrete Math., 1(2) 1971/72, 121–132

J. Bondy, Large cycles in graphs, Discrete Math., 1(2) 1971/72, 121–132

work page 1971
[4]

Chv´ atal and D

V. Chv´ atal and D. Hanson, Degrees and matchings, J. Combin. Theory Ser. B, 20 (1976), 128–138

work page 1976
[6]

Erd˝ os and T

P. Erd˝ os and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Hungar., 10 (1959), 337–356

work page 1959
[7]

Erd˝ os and M

P. Erd˝ os and M. Simonovits, A limit theorem in graph theory,Studia Sci. Math Hungar., 1 (1966), 51–57

work page 1966
[8]

Erd˝ os and A

P. Erd˝ os and A. Stone, On the structure of linear graphs, Bull. Amer. Math., 52 (1946), 1089–1091

work page 1946

Show all 19 references

[9]

X. Fang, X. Zhu, and Y. Chen, Generalized Tur´ an problem for a p ath and a clique, arxiv: 2409.10129

arXiv
[10]

D. Gerbner. On Tur´ an problems with bounded matching number . J. Graph Theory , 106(1), 23–29, 2024

2024
[11]

G. O. H Katona and C. Xiao, Extremal graphs without long paths and large cliques, European J. Combin., 119 (2024), No. 103807

2024
[12]

Liu and L

Y. Liu and L. Kang, Extremal graphs without long paths and a giv en graph, Discrete Math., 347(7) (2024), No.113988, 11 pp

2024
[13]

Y. Lu, Y. Liu, and L. Kang, Extremal problems for star forest s and cliques, arXiv:2404.05942
[14]

Ma and B

J. Ma and B. Ning, Stability results on the circumference of a gra ph, Combinatorica, 40(1) (2020), 105–147

2020
[15]

Y. Ma, X. Hou, and Z. Yin, Generalized Tur´ an problem with boune d matching number, arXiv:2301.05625

arXiv
[16]

Tur´ an, On an extremal problem in graph theory (in Hungrarian), Mat

P. Tur´ an, On an extremal problem in graph theory (in Hungrarian), Mat. es Fiz. Lapok., 48 (1941), 436–452

1941
[17]

H. Wang, X. Hou, and Y. Ma, Spectral extrema of graphs with b ounded clique number and matching number, Linear Algebra Appl., 669 (2023), 125–135

2023
[18]

Xue and L

Y. Xue and L. Kang, On generalized Tur´ an problems with bounde d matching number, arXiv:2410.12338

arXiv
[19]

Zhu and Y

X. Zhu and Y. Chen, Extremal problems for a matching and any o ther graph, arxiv: 2307.11983. 11

arXiv

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [5]

C. Dou, B. Ning, and X. Peng, The number of edges in graphs with b ounded clique number and circumference, arXiv:2410.06449. 10

arXiv

[2] [1]

Abbott, D

H. Abbott, D. Hanson, and H. Sauer, Intersection theorems f or systems of sets, J. Com- bin. Theory Ser. A, 12 (1972), 381–389

work page 1972

[3] [2]

Alon and F

N. Alon and F. Frankl, Tur´ an graphs with bounded matching numb er, J. Combin. The- ory Ser. B, 165 (2024), 223–229

work page 2024

[4] [3]

Bondy, Large cycles in graphs, Discrete Math., 1(2) 1971/72, 121–132

J. Bondy, Large cycles in graphs, Discrete Math., 1(2) 1971/72, 121–132

work page 1971

[5] [4]

Chv´ atal and D

V. Chv´ atal and D. Hanson, Degrees and matchings, J. Combin. Theory Ser. B, 20 (1976), 128–138

work page 1976

[6] [6]

Erd˝ os and T

P. Erd˝ os and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Hungar., 10 (1959), 337–356

work page 1959

[7] [7]

Erd˝ os and M

P. Erd˝ os and M. Simonovits, A limit theorem in graph theory,Studia Sci. Math Hungar., 1 (1966), 51–57

work page 1966

[8] [8]

Erd˝ os and A

P. Erd˝ os and A. Stone, On the structure of linear graphs, Bull. Amer. Math., 52 (1946), 1089–1091

work page 1946