The Global Structure of a Typical Graph Without $H$ as an Induced Subgraph when $H$ is a Cycle

Bruce Reed

REVIEW 3 major objections 4 minor 15 references

The Global Structure of a Typical Graph Without $H$ as an Induced Subgraph when $H$ is a Cycle

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

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

Pith's one-line read Almost every C6-free graph has a simple two-part certificate: a stable set and the complement of a graph of girth 5.

desk verdict 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. read the letter →

arxiv 2506.03544 v1 pith:IK64KPJI submitted 2025-06-04 math.CO

Bruce Reed This is my paper

classification math.CO MSC 05C3005C3805C7505C80

keywords inducedsubgraphstypicalstructureC6-freegraphsevencycleswitnessingpartitionsasymptoticenumerationgraphcountinghereditaryproperties

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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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

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.

There 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.

The 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.

Despite 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.

Who 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.

Referee Report

3 major / 4 minor

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.

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 (3)

[Section 8 (Theorem 2) and Claim 34] 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 3, Corollary 23] 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 7, Claim 34] 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.

minor comments (4)

[Throughout] 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.
[Claim 10 proof] 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 4.2, definition of strong compatibility] 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.
[Claim 14 proof] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the structural characterization theorems are proved by independent counting arguments; the target partitions appear only as lower-bound certificates, and the single self-citation to [8] is a non-load-bearing standard lemma.

full rationale

The paper's central claims (Theorems 2–5) are enumeration/structure theorems, not fitted predictions. The proof uses a good/bad dichotomy: graphs with the claimed certifying partition are constructed directly to give a lower bound on |Forb_n^H|, and then Claims 25–33 plus ABBM's Corollary 23 are used to show that graphs without such a certificate form a o(1)-fraction. Using the target partition in the lower-bound certificate is not circular, because that certificate is an independent construction, while the upper bound is counted per partition. The only author-self-citation is in Theorem 24, where the paper invokes "an easy, standard argument (see, for instance, the proof of Lemma 5 in [8])" to find edge-disjoint cliques; this is an auxiliary parameter-free lemma, not the target result, and the argument is sketched, so it is not load-bearing. Two genuinely flagged issues are mathematical gaps, not circularity: Corollary 23 is imported with "We omit the details, simply sketching the very. very minor modifications," and Section 8's "By the results of the last section (applied to G*" applies Claim 34 to families (stable sets and complements of girth-5 graphs) whose minimum degree need not satisfy Claim 34's hypothesis "every graph in F_i on l vertices has minimum degree at least 31l/32+1"—a stable set has min degree 0. These concerns affect completeness, but they do not make any claimed result equivalent by construction to its inputs.

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

No empirical constants are fitted. The paper introduces mathematical definitions such as witnessing partitions, really canonical sequences, atypical sets, and strong cores; these are proof machinery, not postulated entities requiring independent evidence. All substantive external inputs are published theorems (ABBM, Morris-Saxton, Seinsche, Promel-Steger).

assumptions (5)

standard math Alon-Balogh-Bollobas-Morris structure theorem for hereditary properties (Theorem 1 of [1]), adapted as Corollary 23 and Theorem 24.
Invoked in Section 3 to obtain a near-witnessing partition for almost every H-free graph; the adaptation is only sketched.
standard math Morris-Saxton bounds on graphs of girth 5: there are 2^{Theta(n^{3/2})} such graphs, and few have fewer than epsilon n^{3/2} edges (Theorems 11-12).
Used in Section 2.2 and Section 8 to bound the number of possible graphs in the C6 certificate families.
standard math Seinsche's theorem: every P4-free graph is either disconnected or has disconnected complement.
Used throughout Section 2 to classify really canonical witnessing sequences for cycles.
standard math Promel-Steger lower and upper bounds on the number of H-free graphs, of order 2^{(1+o(1))(1-1/wpn(H)){n choose 2}}.
Used in Sections 1 and 3 to set the scale separating typical and atypical graphs and to justify focusing on balanced partitions.
standard math Chernoff bounds and de Bruijn's asymptotic formula for Bell numbers.
Used in Claims 14, 15, 25-28 and Observations 18-21 for concentration and for counting set partitions with specified component sizes.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Global Structure of a Typical Graph Without $H$ as an Induced Subgraph when $H$ is a Cycle." pith.science (2026). https://pith.science/paper/IK64KPJI

@misc{pith2026250603544,
  author       = {Pith},
  title        = {Pith review of: The Global Structure of a Typical Graph Without $H$ as an Induced Subgraph when $H$ is a Cycle},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IK64KPJI}},
  note         = {Machine review of arXiv:2506.03544}
}

abstract

One way to certify that a graph does not contain an induced cycle of length six is to provide a partition of its vertex set into (i) a stable set, and (ii) a graph containing no stable set of size three and no induced matching of size two. We show that almost every graph which does not contain a cycle of length six as an induced subgraph has such a certificate. We obtain similar characterizations of the structure of almost all graphs which contain no induced cycle of length $k$ for all even $k$ exceeding six. (Similar results were obtained for $k=3$ by Erdos, Kleitman, and Rothschild in 1976, for $k =4,5$ by Promel and Steger in 1991 and for odd $k$ exceeding 5 by Balogh and Butterfield in 2009.) We prove that a simiiar theorem for all $H$ holds up to the deletion of a set of $o(|V(G)|)$ vertices and ask for which $H$ the characterization holds fully.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

N. Alon, J. Balogh, B. Bollob´ as and R. Morris, The structure of al- most all graphs in a hereditary property,J. Combin. Theory Ser. B101 (2011), 85–110

work page 2011
[2]

Balogh and J

J. Balogh and J. Butterfield. Excluding induced subgraphs: Critical graphs. Random Structures and Algorithms, 38(1-2): 100-120 (2011)

work page 2011
[3]

Brandstadt, V

A. Brandstadt, V. B. Le, and J. P. Spinrad,Graph Classes: A Survey, Philadelphia, SIAM, 1999

work page 1999
[4]

Chernoff

H. Chernoff. A note on an inequality involving the normal distribution. Ann. Probab., 9: 533-535 (1981)

work page 1981
[5]

de Bruijn, Asymptotic methods in analysis (3rd ed.), Dover, 1981

N.G. de Bruijn, Asymptotic methods in analysis (3rd ed.), Dover, 1981

work page 1981
[6]

Erd˝ os, D

P. Erd˝ os, D. J. Kleitman, B. L. Rothschild. Asymptotic enumeration ofK n-free graphs,International Colloquium on Combinatorial Theory, Atti dei Convegni Lincei17(1976), 19–27

work page 1976
[7]

J. Kim, D. K¨ uhn, D. Osthus, T. Townsend. Forbidding induced even cycles in a graph: typical structure and counting. J. Comb. Theory, Ser. B131170-219 (2018)

work page 2018
[8]

Martin Loebl, Bruce Reed, Alex Scott, Stephan Thomass´ e and Andrew Thomason, Almost allH-free graphs have the Erd˝ os-Hajnal property, inAn Irregular Mind (Szemer´ edi is 70), Bolyai Society Mathematical Studies, Springer, Berlin, 21 (2010) 405-414

work page 2010

Show all 15 references

[9]

Morris and D

R. Morris and D. Saxton, The number ofC 2l-free graphs,Advances in Mathematics, 298 (2016), 534-580

2016
[10]

Norin and Y

S. Norin and Y. Yuditsky, Typical structure of Exotic Graph Families II: Exotic Families,Random Structures and Algorithms 66: (2025). 44

2025
[11]

H. J. Pr¨ omel and A. Steger. Excluding induced subgraphs: Quadrilat- erals. Random Structures and Algorithms 2: 55-71 (1991)

1991
[12]

H. J. Pr¨ omel and A. Steger. Excluding induced subgraphs III: A general asymptotic. Random Structures and Algorithms 3(1): 19-31 (1992)

1992
[13]

H. J. Pr¨ omel and A. Steger. Almost all Berge graphs are perfect. Com- binatorics, Probability and Computing 1: 53-79 (1992)

1992
[14]

H. J. Pr¨ omel and A. Steger. Excluding induced subgraphs II: Extremal graphs. Discrete Applied Mathematics 44(1-3): 283-294 (1993)

1993
[15]

Seinsche On a property of the class ofn-colorable graphs

D. Seinsche On a property of the class ofn-colorable graphs. J. Combin. Theory Ser. B 16: 191-193 (1974). 45

1974

Pith tools

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

[1] [1]

N. Alon, J. Balogh, B. Bollob´ as and R. Morris, The structure of al- most all graphs in a hereditary property,J. Combin. Theory Ser. B101 (2011), 85–110

work page 2011

[2] [2]

Balogh and J

J. Balogh and J. Butterfield. Excluding induced subgraphs: Critical graphs. Random Structures and Algorithms, 38(1-2): 100-120 (2011)

work page 2011

[3] [3]

Brandstadt, V

A. Brandstadt, V. B. Le, and J. P. Spinrad,Graph Classes: A Survey, Philadelphia, SIAM, 1999

work page 1999

[4] [4]

Chernoff

H. Chernoff. A note on an inequality involving the normal distribution. Ann. Probab., 9: 533-535 (1981)

work page 1981

[5] [5]

de Bruijn, Asymptotic methods in analysis (3rd ed.), Dover, 1981

N.G. de Bruijn, Asymptotic methods in analysis (3rd ed.), Dover, 1981

work page 1981

[6] [6]

Erd˝ os, D

P. Erd˝ os, D. J. Kleitman, B. L. Rothschild. Asymptotic enumeration ofK n-free graphs,International Colloquium on Combinatorial Theory, Atti dei Convegni Lincei17(1976), 19–27

work page 1976

[7] [7]

J. Kim, D. K¨ uhn, D. Osthus, T. Townsend. Forbidding induced even cycles in a graph: typical structure and counting. J. Comb. Theory, Ser. B131170-219 (2018)

work page 2018

[8] [8]

Martin Loebl, Bruce Reed, Alex Scott, Stephan Thomass´ e and Andrew Thomason, Almost allH-free graphs have the Erd˝ os-Hajnal property, inAn Irregular Mind (Szemer´ edi is 70), Bolyai Society Mathematical Studies, Springer, Berlin, 21 (2010) 405-414

work page 2010