{"id":"85c258e6-da9b-4164-b7a5-acd3dd234fdb","arxiv_id":"2506.03418","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":2.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey of what is known about maximizing the count of one fixed subgraph in graphs that avoid another fixed subgraph.","lead":"This paper surveys the generalized Turán number ex(n,H,F): the maximum number of copies of a subgraph H in an n-vertex graph that avoids a forbidden graph F. It catalogs the theorems, methods, and open problems of a field that has grown quickly since Alon and Shikhelman systematized it in 2016.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 5.7's printed proof is internally inconsistent: with the stated constant, the deletion loss exceeds the expected H-count, so the claimed lower bound is not derived.","rationale":"The reader's candidate weakest assumption, the unproved strengthening of the supersaturation theorem in Theorem 2.8, is actually safe: the chi(H)<chi(F) condition can be dropped, because the Removal Lemma deletes o(n^2) edges to eliminate a sparse forbidden graph F, and that destroys only o(n^{|V(H)|}) copies of H. Thus the theorem survives, and that particular concern does not land. However, a different concrete defect appears in the proof sketch of Proposition 5.7, the paper's representative exposition of the probabilistic method. The printed constant c is chosen too large, making the expected loss term exceed the expected H-count; the displayed difference in the proof is negative, so the claimed lower bound is not derived as written. This is a localized correctness issue rather than a fatal one, because the proposition itself is attributed to [98] and a sufficiently small c would repair the argument. Still, it illustrates that the methods section is not yet reliable as printed, which supports the reader's conditional verdict without requiring a harsher one.","tokens_in":51779,"tokens_out":25726,"duration_ms":295407,"concrete_test":"Compute the two terms in Proposition 5.7 for H=K3 and F=K4. With p=c n^{-2/3}, expected H-copies is at least c^3 n/27, while expected destroyed H-copies is at most c^6 n. For the printed c=3^3*3+1=82, the difference is (82^3/27 - 82^6)n < 0. Then rerun the same proof with c=1/4; if the difference becomes positive and the Omega(n) bound follows, the defect is a local typo in the survey, not a false proposition. This one computation settles whether the methods section's probabilistic sketch is sound as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that this is a reliable map of the literature and methods. Section 5 presents Proposition 5.7 (restating Proposition 2.4) as the representative use of the probabilistic method. As printed, the proof cannot work. Setting H=K3 (h=3, e(H)=3) and F=K4 (f=4, e(F)=6), the proof takes p=c n^{-2/3} with c=3^3*3+1=82. The expected number of copies of H is at least (n/3)^3 p^3 = 82^3 n/27; deleting one edge from each copy of F destroys at most n^4 p^6 * n = 82^6 n copies of H. Since 82^6 is larger than 82^3/27 by a factor of 27*82^3, the subtracted term dominates and the displayed difference is negative. A correct argument would need c<3^{-1}, i.e., a constant below one. This is not a dispute with the cited result [98], which is likely true; it is a concrete defect in the survey's own derivation, and it is exactly the kind of unchecked detail the reader's reliability condition hinges on. The reader's preferred weakest assumption, the dropped chi(H)<chi(F) condition in Theorem 2.8, does not land: that strengthening follows from the Removal Lemma, since deleting o(n^2) edges to kill a sparse F destroys only o(n^{|V(H)|}) copies of H.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper is a survey of the generalized Turán number ex(n,H,F), the maximum number of copies of a fixed graph H in an n-vertex F-free graph. It covers the history of the subject, general theorems (Alon–Shikhelman, Gerbner–Palmer, supersaturation and stability), the non-degenerate and degenerate cases organized by the graph H, a methods section (regularity, probabilistic, stability, flag algebras, spectral, progressive induction, algebraic constructions), and a list of open problems. The authors state an aim of exhaustively collecting the literature and introducing unifying terminology (k-Turán-good, F-Turán-stable, t-Füredi-good).","tokens_in":51950,"tokens_out":6308,"duration_ms":69834,"significance":"If the survey is accurate, it provides a valuable and much-needed central reference for a rapidly growing area. Its systematic terminology and organization of scattered results, together with proof sketches of representative methods, make it useful both to specialists and to newcomers. The discussion of methods and open problems is a genuine contribution. However, the survey's value depends on the reliability of its statements and proofs; the proof of the probabilistic lower bound in Proposition 5.7 is incorrect as printed, and the survey incorporates results from two 'in preparation' works, which weakens the claimed exhaustiveness and verifiability.","major_comments":[{"comment":"The proof of Proposition 5.7 is mathematically invalid as written. With the stated constant c = h^h(e(F)-e(H)) + 1, the expected number of copies of H destroyed by deleting one edge per copy of F is larger than the expected number of copies of H in the random graph, so the difference displayed in the proof is negative. Explicitly, the H-count term has coefficient c^{e(H)}/h^h and the deletion term has coefficient c^{e(F)}; since c > 1 and c^{e(F)-e(H)} = (h^h(e(F)-e(H))+1)^{e(F)-e(H)} is vastly larger than h^{-h}, the bound is not derived. For the example H = K_3 and F = K_4, h=3, e(H)=3, e(F)=6, c=82, and the deletion term 82^6 n^{h - ...} dominates 82^3/27 n^{h - ...}. A correct argument would require, for instance, choosing c < h^{-h/(e(F)-e(H))}, e.g., c = 1/4 for this example. Since this proposition is presented as the representative application of the probabilistic method, this is a load-bearing defect in the survey's methodological content. The cited result [98] is likely correct, but the survey's derivation does not establish it.","section":"Section 5.2, Proposition 5.7 (also Proposition 2.4)"},{"comment":"The survey's central claim is that it provides a trustworthy and exhaustive inventory of the literature, but it incorporates results from two works marked 'in preparation' into the main text. In particular, the characterization of pairs (H,F) with ex(n,H,F) = O(1) and the linearity-versus-constancy dichotomy in Section 2.1 are attributed to [92], which is not publicly available. Similarly, several references to 'Part II' [96] describe results that do not yet exist. These items cannot be checked by the reader and should either be removed, clearly marked as private communications or announced results, or the survey should state explicitly that these claims are provisional.","section":"Sections 2.1 and 4.2/4.5 (references [92] and [96])"}],"minor_comments":[{"comment":"There is a typo in 'Removal :emma (Lemma 5.5)' — it should read 'Removal Lemma'.","section":"Section 5.3"},{"comment":"The sentence 'there are instances where there is non-vertex F-free graph' contains a typo; it should be 'there is no n-vertex F-free graph'.","section":"Section 2.1"},{"comment":"The authors claim an 'exhaustive approach to the collection literature' in the Introduction but also state that they 'will not always state all results completely or precisely'; the tension between these two statements should be resolved explicitly, for example by clarifying that the collection aims to be exhaustive while some statements are abbreviated.","section":"Throughout"},{"comment":"The comment that the condition χ(H) < χ(F) in Halfpap and Palmer [123] 'can be safely dropped' is correct and follows from the Removal Lemma: if an n-vertex graph has few copies of F, deleting o(n^2) edges destroys all copies of F while removing only o(n^{|V(H)|}) copies of H, so the claimed lower bound on N(F,G) follows by contradiction. This is not a defect.","section":"Section 2, Theorem 2.8"}],"recommendation":"major_revision","confidential_remarks":"The authors are among the principal contributors to this area, so the high rate of self-citation is expected; however, the inclusion of two 'in preparation' items as references is a verifiability problem for a survey. The proof error in Proposition 5.7 is a concrete, fixable defect, but it currently undermines the survey's stated aim of presenting reliable methods. Once the proof is corrected and the unpublished references are resolved, the survey would be suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this survey is worth having. It is a well-organized map of a fast-moving area, and the authors know the material cold. The proof sketches I checked in Section 5 (regularity, stability, progressive induction) are sound and genuinely helpful—the progressive induction examples for ex(n,P3,C5) and ex(n,C4,C5) are instructive. The open problems section is a real service. Nothing here is new, but a good survey does not need to be.\n\nThe soft spots are concentrated. First, the proof of Proposition 5.7 as printed cannot work. With H=K3, F=K4, the chosen constant c=82 makes the expected number of deleted H-copies (from destroying F copies) exceed the expected number of surviving H-copies; the displayed difference is negative. This is a genuine numerical error in the derivation. The proposition itself is Gerbner–Palmer and likely true—the fix is to choose a constant below one, or argue differently—but as written the survey's own representative probabilistic-method proof is wrong. That matters in a methods section.\n\nSecond, the reader's worry about dropping χ(H)<χ(F) in Theorem 2.8 is a non-issue: the removal lemma argument goes through without that condition, so the strengthening is fine.\n\nThird, the 'exhaustive approach' claim in the introduction sits awkwardly with their own admission that completeness is 'hopeless'. Minor, but a careful reader will notice the tension. And two references are 'in preparation'; that is tolerable in a survey but slightly risky for a would-be standard reference.\n\nBottom line: this is a useful contribution for anyone who wants a map of the field, and it deserves a serious referee. The referee should check Proposition 5.7 and ask the authors to correct that proof sketch (or cite the original derivation). With that fixed, I'd be happy to see it in a journal.","headline":"A genuinely useful survey that is let down by one incorrect proof sketch; the rest holds up.","tokens_in":52662,"tokens_out":3558,"would_cite":true,"duration_ms":38451,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C30","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A survey of generalized Turán problems claims that counting copies of a subgraph H in F-free graphs is now a mature field with a known map, a toolkit of eight methods, and a concrete open-problem list.","keywords":["generalized Turán numbers","extremal graph theory","subgraph counting","F-free graphs","Turán-good graphs","Turán-stable graphs","flag algebras","degenerate extremal problems"],"falsifier":"Test the dropped condition with $H=C_5$ and $F=K_3$: look for $n$-vertex graphs with $\\varepsilon n^5$ copies of $C_5$ but only $o(n^3)$ triangles; their existence would refute Theorem 2.8 as printed.","tokens_in":51415,"feed_emoji":"📐","tokens_out":9561,"duration_ms":100113,"temperature":0.7,"pith_summary":"The paper surveys the generalized Turán number $\\mathrm{ex}(n,H,F)$, the maximum number of copies of a subgraph $H$ in an $n$-vertex graph containing no copy of $F$. It aims to give an exhaustive inventory of what is known about this function, arguing that the field has a clear structure: a non-degenerate case governed by chromatic numbers and 'Turán-good'/'Turán-stable' graphs, and a degenerate case organized by the graph $H$ being counted. The survey traces the subject from pre-2016 results such as Zykov's 1949 theorem and Erdős's 1938 cherry bound through Alon and Shikhelman's systematic program and the subsequent boom, then catalogs eight methods and a list of open problems. A sympathetic reader would take the paper's main contribution to be the map itself: a reliable, organized reference for what is known, what methods prove it, and where the gaps are.","feed_headline":"A complete map now covers counting H-copies in F-free graphs","feed_subtitle":"From 1949 to flag algebras: exact and asymptotic results, methods, and open problems, all in one place.","key_machinery":"The central object is the function $\\mathrm{ex}(n,H,F)$, together with the dichotomy supplied by the blowup criterion: $F$ embeds in a blowup of $H$ if and only if $\\mathrm{ex}(n,H,F)=o(n^{|V(H)|})$. The named structural properties are $F$-Turán-good and $F$-Turán-stable (plus weak variants), which say respectively that the Turán graph, or some complete multipartite graph, maximizes copies of $H$ asymptotically or exactly; the survey uses stability of these properties as a machine for converting approximate structural statements into exact formulas. The method section adds the standard tools—regularity lemma, probabilistic method, stability method, flag algebras, spectral bounds, progressive induction, and algebraic constructions—as the practical machinery behind the inventory.","core_discovery":"The paper's central claim, on its own terms, is that generalized Turán numbers $\\mathrm{ex}(n,H,F)$ now form a coherent and fully surveyed field, and that this survey provides the map. The organizing classification is Proposition 2.3: $\\mathrm{ex}(n,H,F)=\\Theta(n^{|V(H)|})$ exactly when $F$ is not a subgraph of a blowup of $H$, and otherwise the function is $o(n^{|V(H)|})$. In the non-degenerate case with $\\chi(H)<\\chi(F)$, the paper highlights Turán-good and Turán-stable graphs as the properties that yield exact extremal graphs, including an extension of the Simonovits color-critical-edge theorem to counting cliques. In the degenerate case, the survey groups results by the counted graph $H$—triangles, cliques, complete multipartite graphs, cycles, stars, forests, and other graphs—and records the best-known bounds, many of which remain open. The paper also devotes a section to eight methods and closes with a list of open problems.","pith_inferences":["Beyond the paper: the survey's completeness claim is the kind of assertion that a citation-graph analysis could test, since the authors admit that results hidden inside other proofs may have been missed and the map would then need periodic revision.","Beyond the paper: the unproved strengthening of the supersaturation theorem is a natural target for a small computational search over graphs $H$ and $F$ with $\\chi(H)\\ge\\chi(F)$, since a counterexample would change Theorem 2.8 as printed.","Beyond the paper: the star-counting results connected to degree-power indices suggest that invariants studied in chemical graph theory, such as Zagreb and Randić indices, could be a source of new generalized Turán bounds and vice versa."],"forward_implications":["If the inventory is accurate, anyone working on $\\mathrm{ex}(n,H,F)$ can first locate the pair $(H,F)$ in the non-degenerate or degenerate section and find the best known bound and the right method.","The stability-to-exact pipeline shows that proving $H$ is $k$-Turán-stable automatically yields exact results for $\\mathrm{ex}(n,H,F)$ for every $k$-chromatic $F$ with a color-critical edge, so one stability proof produces infinitely many exact theorems.","Several open problems in the degenerate case are explicitly tied to classical Turán conjectures, so progress on, say, the Erdős girth conjecture or the Erdős–Sós conjecture would immediately sharpen generalized Turán bounds.","The open-problem list singles out concrete targets, including exact values of $\\mathrm{ex}(n,C_6,C_8)$ and $\\mathrm{ex}(n,P_6,P_8)$, and Conjecture 6.3 on cliques in tree-free graphs."],"supporting_citations":[{"why":"Supplies the systematic definition of $\\mathrm{ex}(n,H,F)$, the blowup characterization, and many of the initial bounds the survey organizes.","marker":"[4]"},{"why":"Establishes the first exact generalized Turán result: the Turán graph maximizes copies of $K_r$ in $K_k$-free graphs.","marker":"[215]"},{"why":"Extends the asymptotic theory to arbitrary $H$ and contributes the general lower-bound and regularity-lemma framework.","marker":"[98]"},{"why":"Gives the generalized color-critical-edge theorem and the stability theorem for cliques, underpinning the non-degenerate section.","marker":"[165]"},{"why":"Determines the order of magnitude for $\\mathrm{ex}(n,C_r,C_k)$ and introduces the partial-blowup lower-bound technique used throughout the degenerate section.","marker":"[103]"},{"why":"States the supersaturation theorem whose condition the survey strengthens without proof in Theorem 2.8.","marker":"[123]"},{"why":"Provides early results on counting subgraphs in $K_k$-free graphs and introduces the Turán-good framework.","marker":"[119]"},{"why":"Defines the classical Turán number that $\\mathrm{ex}(n,H,F)$ generalizes and serves as the baseline comparison throughout the survey.","marker":"[196]"}],"fun_headline_variants":["Complete map for counting H-copies in F-free graphs","Generalized Turán numbers: the field, now fully surveyed","Counting subgraphs in forbidden graphs: the comprehensive guide"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the survey's unsupported claim that the technical condition in the supersaturation theorem of Halfpap and Palmer—the counted graph having smaller chromatic number than the forbidden graph—can be dropped without changing the conclusion, so if that assertion fails, Theorem 2.8 as printed fails.","fun_headline_variants_meta":{"raw":{"variants":["Complete map for counting H-copies in F-free graphs","Generalized Turán numbers: the field, now fully surveyed","Counting subgraphs in forbidden graphs: the comprehensive guide"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000261,"raw_usage":{"total_tokens":1542,"prompt_tokens":846,"completion_tokens":696,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":462,"completion_tokens_details":{"reasoning_tokens":643}},"tokens_in":462,"tokens_out":696,"duration_ms":8202,"temperature":1.0,"reasoning_tokens":643,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:04:08.492328+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Test the dropped condition with $H=C_5$ and $F=K_3$: look for $n$-vertex graphs with $\\varepsilon n^5$ copies of $C_5$ but only $o(n^3)$ triangles; their existence would refute Theorem 2.8 as printed.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the first exact generalized Turán result: the Turán graph maximizes copies of $K_r$ in $K_k$-free graphs."},{"cited_title":"Ma and Y","cited_arxiv_id":null,"evidence_quote":"Gives the generalized color-critical-edge theorem and the stability theorem for cliques, underpinning the non-degenerate section."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the classical Turán number that $\\mathrm{ex}(n,H,F)$ generalizes and serves as the baseline comparison throughout the survey."}],"review_version":1}