{"id":"788ecde5-d442-4ab3-944b-a8327bcd6b08","arxiv_id":"2506.03544","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Almost every C6-free graph is the disjoint union of a stable set and the complement of a graph of girth 5; analogues for C8, C10, and longer even cycles complete the induced-cycle typical-structure picture.","lead":"Almost every graph with no induced 6-cycle can be split into an independent set plus a part whose complement has no 3- or 4-cycles, and similar certificates exist for longer even cycles. This fills the last gaps in a 35-year-old program describing the typical structure of graphs that forbid a given cycle as an induced subgraph.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 8's proof of Theorem 2 applies Claim 34 to a stable-set + complement-of-girth-5 certificate, but Claim 34 requires all non-first parts to have min degree ≥31l/32+1; neither part satisfies this, so the overcounting bound is unsupported.","rationale":"The reader's conditional verdict is right in spirit. My concern differs from the reader's Corollary 23 worry: I grant the ABBM import and still find a gap in the flagship C6 theorem. The proof skeleton for C8/C10 and longer cycles uses Claim 34 in a regime where its hypotheses do hold (all but one part are cliques), so those theorems are less affected; the C6 case is genuinely special. This is not an attack on the author's credibility; the counting strategy is plausible and the paper contains substantial correct-looking machinery (Claims 25-28, Section 6). The issue is a missing proof step, not a false statement in the abstract. I recommend the verdict stay CONDITIONAL: the theorems are likely correct but Section 8 needs either a direct overcounting bound for the stable/complement-of-girth-5 certificate or a replacement of the Claim 34 reduction.","tokens_in":31294,"tokens_out":38817,"duration_ms":424524,"concrete_test":"Determine whether the missing overcounting control can be supplied. Two checks suffice: (1) In §8, quantify α in the statements 'there is some α such that there are fewer than 2^{|X_1*||X_2*|-α n} choices'; if α≤1, the crude partition sum fails. (2) Prove or disprove that the number of good (G,P) pairs for the C6 certificate is at most 2^{o(n)} times the number of good graphs; note the local uniqueness argument of Claim 34 fails on K_n, which has 2^n such certificates, so a different argument is required. If neither check yields a bound, Theorem 2 is not proven.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Theorem 2 (Section 8) reduces the bad-graph count to a per-partition comparison by invoking 'the results of the last section'. The only such result is Claim 34, whose hypotheses require that for every i>1, every graph in F_i on l vertices have minimum degree at least 31l/32+1. For the C6 certificate (X_2* stable, X_1* complement of a graph of girth 5), neither choice of F_1,F_2 satisfies this: a stable set has minimum degree 0, and the family of complements of girth-5 graphs contains complements of stars, e.g. K_{l-1}∪K_1, with an isolated vertex. Claim 34's Θ(1) overcounting bound is also not vacuously true: K_n admits 2^n certificates X_1*=K_n-S, X_2*=S. Consequently the 'it is enough' step is unsupported: the per-partition bad bounds in §8 are of the form 2^{m-αn} for an unspecified constant α, and summing over the 2^n partitions only gives o(2^m) if α>1, which is not shown. Theorem 2 therefore lacks a complete proof as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the typical structure of graphs on n vertices that contain no induced copy of a cycle H. It develops a framework of H-freeness witnessing sequences and really canonical sequences, and states a general near-characterization result (Theorem 24) asserting that almost every H-free graph admits a witnessing partition with o(n) exceptional vertices. The main structural theorems are Theorem 2 for C6 (partition into a stable set and the complement of a graph of girth 5), Theorem 3 for C2l with l>5 (partition into l-2 cliques and the complement of a disjoint union of stars and triangles), Theorem 4 for C8, and Theorem 5 for C10. The author argues that, combined with earlier work, these results complete the characterization for all cycles and their complements. The proof is a long multistep counting argument: Section 3 derives the near-witnessing partition from results of Alon, Balogh, Bollobas, and Morris; Sections 4-6 strengthen it using atypical sets and cores; Section 7 gives a partition-counting lemma (Claim 34); Sections 8-9 apply it to certify the good graphs.","tokens_in":31455,"tokens_out":8231,"duration_ms":94860,"significance":"If the results are correct, they significantly extend a line of work by Erdos-Kleitman-Rothschild, Promel-Steger, and Balogh-Butterfield to all even cycles, providing explicit structural descriptions for almost all C_{2l}-free graphs. The general near-characterization in Theorem 24 is a strong statement of independent interest, and the paper is honest about the fact that an earlier conjecture for all H was disproved by Norine and Yuditsky. The paper contains no fitted parameters and makes falsifiable structural predictions. Its main weakness is that several load-bearing steps are only sketched or depend on an inapplicable counting lemma in Section 8; these gaps currently prevent the theorems from being considered established.","major_comments":[{"comment":"The proof of Theorem 2 invokes 'the results of the last section' to pass from counting bad graphs to comparing, for each partition, the number of bad graphs with the number of good graphs admitting that partition. The only result supplying such a Theta(1) comparison is Claim 34, whose hypothesis (2) requires that for every i>1 every graph in F_i on l vertices has minimum degree at least 31l/32 + 1. For the C6 certificate, however, one part is stable (minimum degree 0) and the other is the complement of a graph of girth 5; the latter family contains graphs such as K_{l-1} union K_1 (the complement of a star) with an isolated vertex, for arbitrarily large l. No choice of which family is F1 satisfies the hypotheses: if F1 is the stable set, then F2 fails (2); if F1 is the complement-of-girth-5 family, then F1 is neither P4-free nor of girth at least five, so it fails (1). Thus Claim 34 cannot be applied, and the stated Theta(1) comparison is unsupported. This is a load-bearing gap in the proof of Theorem 2.","section":"Section 8 (Theorem 2) and Claim 34"},{"comment":"Corollary 23 is the foundation for Theorem 24 and hence for all later sections (Claims 29, 30, and 32), but its proof is only a sketch: after saying 'We can essentially read this out of the proof of Theorem 1 in [1]', the text states 'We omit the details, simply sketching the very. very minor modifications.' This is not a complete proof. In particular, the modification replaces n^{1-alpha} by a constant c in the definition of U(P_n, alpha, k), and changes the exceptional set size, and it needs to be shown that the ABBM proof survives these changes with all constants controlled. A precise derivation, or a quotation of the exact ABBM theorem statement from which Corollary 23 follows, is needed before the later counting arguments can be considered established.","section":"Section 3, Corollary 23"},{"comment":"In the proof of (alpha), after establishing that Y1 must properly contain Xi for some i>1, the text says that condition (c) implies Xi = Y1 - v for some vertex v, and then that applying (a) to X1-v and (b) shows X1-v must lie in the same part in any partition satisfying (P*). This step is not justified in the manuscript: it is not shown why (c) forces Xi to have co-degree one in Y1, nor why the subsequent symmetric argument controls all partitions. Since (alpha) is one of the two assertions proving the Theta(1) bound, this gap matters independently of the applicability issue raised for Section 8.","section":"Section 7, Claim 34"}],"minor_comments":[{"comment":"The manuscript contains numerous typos that impede reading: 'simiiar' and 'chartacterizattion' in the abstract, 'seuqence' and 'really canoncial' in Section 1, and 'wpn(HG)' in Section 4.1.","section":"Throughout"},{"comment":"In the proof of Claim 10, the sentence 'Since any P4 free graph is either disconnected or disconnected in the complement, it follows that for any J in F> the components of J are either the union of a clique and a vertex, or a stable set of size three' contains a garbled symbol 'F>' and does not complete the claimed classification; please rewrite this passage.","section":"Claim 10 proof"},{"comment":"The phrase 'polylogarithmic in log n' should presumably read 'polylogarithmic in n'; the intended bound on |A| is stated as o((log n)^2) in item 6 of the definition of strong compatibility.","section":"Section 4.2, definition of strong compatibility"},{"comment":"In the proof of Claim 14, the text refers to 'the sum of the degrees of the vertices of D_j' in condition (iv), but D_j is a family of graphs and the intended object is the set D of vertices; please correct this notation.","section":"Claim 14 proof"}],"recommendation":"major_revision","confidential_remarks":"This is a serious contribution that fits the journal's scope, but the present version has a load-bearing gap in the proof of Theorem 2 and a merely sketched Corollary 23. The author should be asked to either prove a version of Claim 34 that covers the stable-set/complement-girth-5 certificate or supply an alternative comparison argument for Section 8, and to give a complete proof of Corollary 23. The C2l results for l>3 may be less affected by the Section 8 issue, but they all depend on Corollary 23. I would not recommend rejection because the structural statements are plausible and partially independently confirmed by Kim et al.; a major revision with complete proofs of the identified steps could make the paper acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here is my take. The genuinely new results are Theorems 2, 4, and 5: the C6, C8, and C10 cases of the Prömel–Steger typical-structure program. Theorem 3 for longer even cycles is honestly credited to Kim, Kühn, Osthus, and Townsend, and the all-H near-certificate is essentially read out of Alon–Balogh–Bollobás–Morris. So the incremental contribution is real but narrower than the title suggests. The paper does several things well: the witnessing-partition framework is applied with care, the really canonical sequences in Claims 6–10 are sensibly classified, and the author is transparent about prior work, including the Norine–Yuditsky disproof of the earlier conjecture.\n\nThere are two soft spots, one minor and one load-bearing. The minor one is editorial: the abstract has 'simiiar' and 'chartacterizattion', Claim 10 has a broken sentence, and other typos suggest the manuscript was never copyedited. The load-bearing one is the proof of Corollary 23, which underpins Theorem 24 and nearly everything after it. The text says only 'We omit the details, simply sketching the very. very minor modifications.' That is not acceptable for the keystone of the paper; the reader needs either a full proof or a precise citation to a version of ABBM that covers exactly this statement.\n\nThe stress-test on Section 8 also lands. Claim 34 requires every non-first family to have minimum degree at least 31l/32 + 1 on l-vertex graphs. The C6 certificate has a stable part, with minimum degree 0, and a complement-of-girth-5 part, which contains complements of stars and hence isolated vertices. Neither satisfies the hypothesis, so the 'it is enough' step in Theorem 2 is unsupported as written. This is a genuine gap, not a nitpick. The per-partition bad bounds are of the form 2^{m - αn} with unspecified α, and the overcounting step needs the Claim 34 machinery to work for exactly this certificate. As written, Theorem 2 is not proved.\n\nDespite the gap, this paper deserves a serious referee. The problem is central, the author is clearly thinking carefully, and the counting architecture is the right toolkit. A referee should demand two things before acceptance: a complete proof or verbatim quotation of Corollary 23, and a repair or replacement for the Section 8 argument. If those come through, the paper is a solid contribution.\n\nWho is this for? Specialists in extremal and random graph enumeration who care about induced subgraph typical structure. I would not bring it to a general reading group in its current form, but I would absolutely engage with a revised version.","headline":"Real new results for C6, C8, C10, but the paper is held together by a sketched ABBM import and Section 8 has a genuine gap in its application of Claim 34.","tokens_in":32114,"tokens_out":2719,"would_cite":false,"duration_ms":32004,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C30","05C38","05C75","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"Almost every C6-free graph has a simple two-part certificate: a stable set and the complement of a graph of girth 5.","keywords":["induced subgraphs","typical structure","C6-free graphs","even cycles","witnessing partitions","asymptotic enumeration","graph counting","hereditary properties"],"falsifier":"Look for an infinite family of C6-free graphs in which every near-witnessing partition requires either a superconstant exceptional set or a part containing the bipartite graph U(k). If such a family exists, Corollary 23—and hence Theorem 24 and Theorem 2—fails. Concretely, one can check the adapted proof of Corollary 23 by following the three-paragraph proof of Theorem 1 in reference [1] with $n^{{1−α}}$ replaced by a fixed constant c; if the size of the bad set B is forced to grow with n for some H, the counting argument breaks.","tokens_in":30995,"feed_emoji":"📐","tokens_out":7149,"duration_ms":77895,"temperature":0.7,"pith_summary":"This paper studies what almost every graph looks like when it contains no induced cycle of a given even length. Its central claim is that almost every graph with no induced 6-cycle can be certified as such by a very simple partition: one part is a stable set, and the other part is the complement of a graph of girth 5. The same kind of explicit partition certificate is obtained for every longer even cycle, and the paper shows that for every graph H, almost every H-free graph admits a near-certificate after deleting o(n) exceptional vertices. If correct, these results complete a structural characterization for all cycles and their complements, extending a line of results for triangles, 4-cycles, 5-cycles, and odd cycles.","feed_headline":"Almost every C6-free graph has a simple two-part certificate","feed_subtitle":"A new proof shows the same explicit partition certificates work for every even cycle, completing a long structural line for cycles.","key_machinery":"The central object is the witnessing partition: a partition of V(G) into wpn(H) parts, each constrained to lie in a hereditary family, so that the constraints themselves certify H-freeness. The paper works with really canonical witnessing sequences, where each family is defined by forbidding induced subgraphs of H and contains arbitrarily large cliques or stable sets. The proof first uses a near-witnessing partition theorem (Corollary 23) to show that almost every H-free graph has such a partition up to $n^{{1−γ}}$ exceptional vertices, with parts that are U(k)-free and have nearly identical neighbourhoods to a bounded set of model vertices. It then upgrades the partition in two stages: atypical sets of size at most six are removed to force strong structural restrictions on the parts—P4-free graphs, complements of girth-5 graphs, disjoint unions of stars and triangles—and strong cores inside the special part provide enough common-neighbour structure to push the exceptional set down to polylogarithmic size. The number of graph-partition pairs is finally compared with the number of good graphs, using the fact that for the relevant families almost all choices of cross-edges extend a certified partition.","core_discovery":"On the paper's own terms, the discovery is that for every even cycle length 2l with l ≥ 3, almost every C_{2l}-free graph has a completely explicit structural certificate. For C6, the certificate is a partition into a stable set and the complement of a graph of girth 5 (Theorem 2). For l > 5, almost every C_{2l}-free graph can be partitioned into l − 2 cliques and the complement of a disjoint union of stars and triangles (Theorem 3), with special statements for C8 (two cliques plus a graph whose complement is a disjoint union of joins of a clique and a stable set) and C10 (three cliques plus a graph whose complement is a disjoint union of stars and cliques). Together with earlier results for odd cycles, this means the characterization holds whenever H is a cycle or the complement of a cycle. The paper also proves a general near-witnessing theorem: for every H, almost every H-free graph has a wpn(H)-part witness after deleting o(n) exceptional vertices.","pith_inferences":["Editorial extension: The polylogarithmic exceptional sets in Claim 32 look like an artifact of the iterative cleaning process; a natural test is whether the O((log n)^6) bound can be reduced to O(1) for even cycles, which would make the certificates exact for almost every graph rather than only after deleting a small set.","Editorial extension: The near-witnessing theorem for arbitrary H suggests a general principle—every H-free graph is almost described by wpn(H) parts with bounded local structure—and the cited counterexample of Norine and Yuditsky indicates that the exact form must fail for some exotic H; the open question is the smallest exceptional-set size achievable in general.","Editorial extension: For C6, the theorem could be tested computationally on moderately large n: sample C6-free graphs, search for the stable/girth-5 partition, and check whether the fraction without such a certificate goes to zero at the rate the counting argument predicts.","Editorial extension: The distinct remainder shapes for C6, C8, C10, and longer even cycles suggest a pattern—the exceptional part is always a complement of a disjoint union of bounded-size star/clique/triangle components; unifying the cases under a single finite list would give a clean closed-form description for all even cycles."],"forward_implications":["If Theorems 2–5 are right, a typical C6-free graph on n vertices is not random-looking inside its two parts; it has a certificate with one part of bounded local structure, so the count of C6-free graphs is dominated by choices of edges between the two parts.","For every even cycle length, typical C_{2l}-free graphs are structured enough to be partitioned into cliques plus one special remainder, giving an exact asymptotic count for those families.","Since the complement of a hereditary family is hereditary, the same structural conclusions hold automatically when H is the complement of a cycle.","The near-witnessing theorem for arbitrary H says that whatever H is, almost every H-free graph can be described up to o(n) vertices by a wpn(H)-part partition; the remaining uncertainty is only how many exceptional vertices are truly needed.","The paper's question—whether the o(n) exceptional set can be shrunk, even to O(n^{1−ε}) or poly(log n)—sets a concrete target for future work on all H."],"supporting_citations":[{"why":"Supplies the near-witnessing partition theorem (Corollary 23) that is the load-bearing imported counting tool for every later claim.","marker":"[1]"},{"why":"Proves the characterization for odd cycles C_{2k+1} and for C7, which the new even-cycle results combine with.","marker":"[2]"},{"why":"Provides the base case for C3: almost every triangle-free graph is bipartite.","marker":"[6]"},{"why":"Gives an independent proof of the C_{2l} characterization for l > 5 using different techniques.","marker":"[7]"},{"why":"Supplies the counting bounds on graphs of girth 5 and on their typical edge counts, needed for the C6 remainder.","marker":"[9]"},{"why":"Disproves the conjecture that the characterization holds for all H, motivating the near-witnessing formulation with an exceptional set.","marker":"[10]"},{"why":"Introduces the witnessing-partition framework, the wpn(H) counting bounds, and the C4 and C5 structural results.","marker":"[11,12,13,14]"},{"why":"Gives the fact that every P4-free graph is disconnected or disconnected in the complement, used throughout the classification of witnessing sequences.","marker":"[15]"}],"fun_headline_variants":["Even-cycle-free graphs almost always have explicit certificates","Almost every graph avoiding an even induced cycle has a simple proof","Certificates for almost all even-cycle-free graphs are explicit","Explicit certificates exist for almost every even-cycle-free graph"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof rests on an imported counting result—that almost every H-free graph can be divided into parts that each avoid a certain fixed bipartite pattern, up to a tiny exceptional set—and this result is only sketched here; if that sketch hides a real gap, the new theorems collapse.","fun_headline_variants_meta":{"raw":{"variants":["Even-cycle-free graphs almost always have explicit certificates","Almost every graph avoiding an even induced cycle has a simple proof","Certificates for almost all even-cycle-free graphs are explicit","Explicit certificates exist for almost every even-cycle-free graph"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00068,"raw_usage":{"total_tokens":3099,"prompt_tokens":964,"completion_tokens":2135,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":2069}},"tokens_in":580,"tokens_out":2135,"duration_ms":18055,"temperature":1.0,"reasoning_tokens":2069,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:00:39.834805+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Look for an infinite family of C6-free graphs in which every near-witnessing partition requires either a superconstant exceptional set or a part containing the bipartite graph U(k). If such a family exists, Corollary 23—and hence Theorem 24 and Theorem 2—fails. Concretely, one can check the adapted proof of Corollary 23 by following the three-paragraph proof of Theorem 1 in reference [1] with $n^{{1−α}}$ replaced by a fixed constant c; if the size of the bad set B is forced to grow with n for some H, the counting argument breaks.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the near-witnessing partition theorem (Corollary 23) that is the load-bearing imported counting tool for every later claim."},{"cited_title":"Balogh and J","cited_arxiv_id":null,"evidence_quote":"Proves the characterization for odd cycles C_{2k+1} and for C7, which the new even-cycle results combine with."},{"cited_title":"Erd˝ os, D","cited_arxiv_id":null,"evidence_quote":"Provides the base case for C3: almost every triangle-free graph is bipartite."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives an independent proof of the C_{2l} characterization for l > 5 using different techniques."},{"cited_title":"Morris and D","cited_arxiv_id":null,"evidence_quote":"Supplies the counting bounds on graphs of girth 5 and on their typical edge counts, needed for the C6 remainder."},{"cited_title":"Norin and Y","cited_arxiv_id":null,"evidence_quote":"Disproves the conjecture that the characterization holds for all H, motivating the near-witnessing formulation with an exceptional set."},{"cited_title":"Seinsche On a property of the class ofn-colorable graphs","cited_arxiv_id":null,"evidence_quote":"Gives the fact that every P4-free graph is disconnected or disconnected in the complement, used throughout the classification of witnessing sequences."}],"review_version":1}