Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Halfway to induced saturation for even cycles

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 The edge-deletion half of induced saturation holds for every even cycle of length at least 8.

desk verdict New and likely correct edge-deletion construction for all even cycles of length at least 8, but Observation 6.1 needs a proof and Lemma 6.2 has a fixable exponent typo. read the letter →

arxiv 2505.24100 v2 pith:7VNMXLL4 submitted 2025-05-30 math.CO

Xinyue Fan , Sahab Hajebi , Sepehr Hajebi , Sophie Spirkl This is my paper
classification math.CO MSC 05C3505C3805C75
keywords inducedsaturationevencyclescycle-freegraphsedgedeletioncanonicalterritorieshigh-girthHamiltonian3-regular
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 asks whether even cycles can be "half" induced-saturated: a graph with at least one edge that contains no induced copy of a given even cycle, yet deleting any edge produces one. The main theorem answers yes for every even cycle of length at least 8. The proof builds a large host graph from a high-girth 3-regular graph with a Hamiltonian cycle, attaches special cycle-with-boundary gadgets, and shows that any induced copy of the forbidden long cycle would project to a short cycle in the host, contradicting its girth. A reader should care because full induced saturation for even cycles has been open for all lengths beyond 10, and this settles the deletion half in full generality.

What carries the argument

The central objects are territories and their expansions. A territory is a graph with a distinguished induced boundary cycle; an expansion replaces a chosen stable set of boundary vertices with paths of prescribed lengths, lengthening the boundary by a controlled linear amount. A canonical territory is one built from a base t-cycle by repeatedly subdividing boundary edges and gluing t-cycles along the boundary, then expanding; these territories are $C_{2t-2}$-free and satisfy a distance bound (closeness in the territory implies closeness along the boundary). The global graph $G_t$ pieces canonical territories over the cycle boundaries of the three 2-factors of $\Gamma$, so that any potential induced $C_{2t-2}$ has to cross territories; the crossing pattern is forced to yield a cycle in $\Gamma$ of length below the girth threshold $t^{5t}$, a contradiction.

What would settle it

For a fixed small value such as $t=5$, instantiate the construction with an explicit 3-regular Hamiltonian graph of girth at least $5^{25}$ and exhaustively test, for every edge $e$ of the resulting $G_5$, whether $G_5-e$ has an induced $C_8$; finding one edge where no induced $C_8$ appears would refute Theorem 1.6. A cheaper check is to search the construction for any induced $C_8$ in $G_5$ itself, which would contradict Theorem 4.4.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that the edge-deletion half of induced saturation holds for every even cycle. Theorem 1.6 states that for every integer $t \ge 5$ there is a graph $G_t$, with at least one edge, which is $C_{2t-2}$-free but has an induced $C_{2t-2}$ somewhere after deleting any individual edge. The proof is constructive: $G_t$ is assembled from "canonical territories" whose boundaries are the cycles of three perfect-matchings-deleted 2-factors of a high-girth 3-regular graph $\Gamma$ with a Hamiltonian cycle. The two closing theorems show $G_t$ contains no induced $C_{2t-2}$ at all, while removing any edge destroys the obstruction and creates such a cycle; the former is proved by projecting a hypothetical induced cycle into a short cycle in $\Gamma$.

Load-bearing premise

The construction depends on the existence of a 3-regular graph with a Hamiltonian cycle and girth at least $t^{5t}$; if no such graph existed for some $t$, there would be no host $\Gamma$ to build $G_t$ on, and the proof would collapse.

Editorial extensions

If this is right

  • For every integer $t \geq 5$, there is a $C_{2t-2}$-free graph $G_t$ such that $G_t - e$ contains an induced $C_{2t-2}$ for every edge $e$ of $G_t$.
  • Combined with the known full induced-saturated graphs for $C_4$, $C_6$, $C_8$, and $C_{10}$, the only remaining gap for even cycles is the edge-addition half for cycles of length at least $12$.
  • If the edge-addition half (Question 1.7) is also proved, the two halves together would yield induced-saturated graphs for every even cycle.
  • The construction uses a number of vertices that is doubly exponential in $t$; the paper leaves open whether a polynomial-size construction exists (Question 1.8).

Reading between the lines

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

  • A natural next step is to try to mirror the construction in the complement to get the edge-addition half; if that worked, the two halves would combine into full induced-saturated graphs for every even cycle.
  • The girth requirement $t^{5t}$ is probably not optimal; smaller explicit high-girth graphs with Hamiltonian cycles would immediately shrink the doubly exponential vertex count and make the construction testable for small $t$.
  • The "territory with boundary" device may transfer to other induced-subgraph problems where a high-girth host lets local forbidden subgraphs be projected to short 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.

Referee Report

3 major / 4 minor

Summary. The paper proves Theorem 1.6: for every integer t ≥ 5, there is a graph G_t with at least one edge such that G_t is C_{2t−2}-free, yet deleting any edge of G_t creates an induced C_{2t−2}. This is the edge-deletion half of induced saturation for all even cycles of length at least 8. The proof constructs G_t by gluing ``canonical territories'' along the cycles of a 3-regular graph of very large girth, using the Linial-Simkin existence theorem as an external ingredient. Section 5 establishes C_{2t−2}-freeness via a projection argument to short paths in the high-girth graph, and Section 6 establishes edge-criticality via local t-cycles inside territories and a distance lemma.

Significance. If the proof is made fully rigorous, this is a substantial first step on a question that has been open for all even cycles beyond C_4: it shows that the edge-deletion half of induced saturation is achievable for every sufficiently long even cycle. The construction is explicit and parameter-free apart from the cited existence of a Hamiltonian high-girth cubic graph, and the high-girth machinery is used in a genuinely non-circular way. The paper also gives small induced-saturated graphs for C_4, C_6, C_8, and computer-verified C_10. The main weakness is that several load-bearing ``observations'' in Sections 5 and 6 are stated without proof, and one displayed inequality in Lemma 6.2 is mathematically false as printed. These issues appear fixable, but they must be addressed before the central theorem can be considered established.

major comments (3)
  1. [Section 6, Observation 6.1] Observation 6.1 is stated without proof, yet it is load-bearing: part (a) is used directly at the start of the proof of Theorem 4.5 for every edge outside E(Γ), and part (b) supplies the induced t-cycles H_i for every boundary edge. The expansion operation creates boundary segments of length 2t−6 or 3t−10, and the claimed existence of an induced (2t−2)-cycle after deleting an arbitrary non-boundary edge, and an induced t-cycle through an arbitrary boundary edge, is not a routine consequence of the territory definition. A complete proof of Observation 6.1 should be supplied, or it should be replaced by a proved lemma; as written, Theorem 4.5 is not established.
  2. [Section 6, Lemma 6.2] The displayed inequality in the proof of Lemma 6.2, dist_TK(x,y) ≤ t^{7t−1} < t^{5t−1}, is false: applying Theorem 3.3 with d = t−1 gives t^{4t−1}, not t^{7t−1}. With the corrected exponent the intended contradiction to dist_K(x,y) ≥ t^{5t−1} still works, so this is likely a typo, but the proof as printed is invalid and must be corrected and re-checked.
  3. [Section 5, claim (11) and Observations 5.1–5.2] Observations 5.1 and 5.2 are stated without proof but are used in the proof of claim (11) inside Theorem 4.4. In particular, the assertion that for a sector P of length at least three there is a path L′ of length t−3 in L_P containing e whose interior vertices have degree two in T_K needs more justification than the stated Observation 5.1 provides. Since claim (11) feeds directly into the counting argument proving C_{2t−2}-freeness, these observations should be proved explicitly or replaced by a more detailed derivation.
minor comments (4)
  1. [Throughout] The name ``Peterson graph'' should be ``Petersen graph''.
  2. [Abstract and Introduction] The proper name of the author of [5] is garbled as ``Dvoŕˇak'' in the abstract and introduction; it should be ``Dvořák''.
  3. [Figure 4 caption] The caption says ``the induced cycle B′ in T′'' when it likely means the new boundary cycle B in T; the caption should be clarified.
  4. [Abstract] The abstract states that the paper constructs H-induced-saturated graphs for every even cycle on at most 10 vertices; for C_10 this relies on a computer verification, which should be mentioned explicitly in the abstract or the wording softened.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the construction is explicit and the central claims are proved internally, with only an independent external girth-graph existence theorem as input.

full rationale

The paper's derivation of Theorem 1.6 is not circular. The construction of G_t starts from a 3-regular high-girth graph Γ supplied by Theorem 4.1 (Linial and Simkin); this is an external existence result whose assumptions do not include the target theorem, so it is independent support rather than a self-citation. The canonical territories are built by explicit recursive operations in Section 3, and Theorem 3.1 shows that every sufficiently large even perimeter occurs; the C_{2t-2}-freeness of canonical territories (Theorem 3.2) and the distance bound (Theorem 3.3) are proved by induction from the construction. No parameter is fitted to the conclusion, and no 'prediction' is a renamed output of a fit. The proof of Theorem 4.4 projects a hypothetical induced cycle onto Γ and derives a contradiction with the girth g = t^{5t}; that girth bound is stated independently of the present result. The proof of Theorem 4.5 uses Observation 6.1, which is asserted without proof, and Lemma 6.2 contains the internally inconsistent displayed bound t^{7t-1} < t^{5t-1}. These are correctness and verification concerns, not circularity: they do not make any claimed result equivalent, by definition or by fitted input, to its own assumptions. There are no self-citations by the authors, no imported uniqueness theorem, and no ansatz smuggled in via citation. Accordingly the circularity score is 0.

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

The construction is fully explicit given the external high-girth graph existence theorem. No numerical parameters are fitted to data; the proof introduces only graph-theoretic definitions such as territories, expansions, and canonical territories.

assumptions (2)
  • domain assumption There exists a 3-regular graph with a Hamiltonian cycle and girth at least t^{5t} for each t at least 5, as stated in Theorem 4.1 and attributed to Linial and Simkin.
    The construction of G_t starts from such a graph Gamma; all girth-based arguments in Lemmas 4.3, 6.2, and Theorem 4.4 depend on it.
  • standard math Standard facts about finite graphs, paths, cycles, induced subgraphs, and matchings are used without proof.
    This is ordinary background for a graph theory paper and is not specific to the central claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Halfway to induced saturation for even cycles." pith.science (2026). https://pith.science/paper/7VNMXLL4

@misc{pith2026250524100,
  author       = {Pith},
  title        = {Pith review of: Halfway to induced saturation for even cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7VNMXLL4}},
  note         = {Machine review of arXiv:2505.24100}
}
abstract

For graphs $G$ and $H$, we say that $G$ is $H$-free if no induced subgraph of $G$ is isomorphic to $H$, and that $G$ is $H$-induced-saturated if $G$ is $H$-free but removing or adding any edge in $G$ creates an induced copy of $H$. A full characterization of graphs $H$ for which $H$-induced-saturated graphs exist remains elusive. Even the case where $H$ is a path -- now settled by the collective results of Martin and Smith, Bonamy et al., and Dvo\'{r}\v{a}k -- was already quite challenging. What if $H$ is a cycle? The complete answer for odd cycles was given by Behren et al., leaving the case of even cycles (except for the $4$-cycle) wide open. Our main result is the first step toward closing this gap: We prove that for every even cycle $H$, there is a graph $G$ with at least one edge such that $G$ is $H$-free but removing any edge from $G$ creates an induced copy of $H$ (in fact, we construct $H$-induced-saturated graphs for every even cycle $H$ on at most 10 vertices).

Figures

Figures reproduced from arXiv: 2505.24100 by the authors.

Figure 1
Figure 1. The icosahedron (left), the Cartesian product of two 5-cycles (middle) and the dodecahedron (right). Theorem 1.1 (Martin and Smith [9]). There is no P4-induced-saturated graph. On the other hand, for various choices of H, the existence of H-induced-saturated graphs were proved in subsequent results by Behrens et al. [2] and by Axenovich and Csikós [1]. The current state of the art, however, is far from a characteriz… view at source ↗
Figure 2
Figure 2. A C10-induced-saturated graph. Naturally, cycles are the next graphs to be examined. For every integer t ≥ 3, we denote by Ct the t-vertex cycle, also called the t-cycle. Note that there is no C3-induced-saturated graph. Behrens et al. [2] gave a simple solution for all odd cycles on five or more vertices: Theorem 1.4 (Behrens, Erbes, Santana, Yager, and Yeager [2]). For every integer t ≥ 3, the line graph of the co… view at source ↗
Figure 3
Figure 3. A C10-free graph G in which removing each edge creates an induced C10 (left) and a drawing of G on the torus that constitutes a hexagonal tiling of the torus. This graph is not C10-induced-saturated. Let P be a path. We write P = p1- · · · -pk, for k ∈ N, to mean V (P) = {p1, . . . , pk} and E(P) = {pipi+1 : i ∈ Nk−1}. The vertices p1, pk are the ends of P, and V (P) \ {p1, pk} is the interior of P. The length of P … view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Top: A territory (T ′ , B′ ) of perimeter 10 with the graph T ′ on the left and the induced cycle B′ in T ′ highlighted on the right. Bottom: An expansion (T, B) of (T ′ , B′ ) (for t = 5) where k = 3 and I = {2, 3}, with the graph T on the left and the induced cycle B…
Figure 5
Figure 5. Figure 5: The territory (T3, B3) of perimeter t(t − 3)3 (for t = 5). (Tm−1, Bm−1) of perimeter t(t − 3)m−1 is defined. Then Bm−1 is a t(t − 3)m−1 -cycle; say Bm−1 = x1- · · · -xt(t−3)m−1 -x1. Now, let Tm be the graph constructed by first adding to Tm−1 the (t − 4)-subdivision Bm…
Figure 6
Figure 6. Figure 6: Construction of Gt : the three canonical territories (TK1 , K1),(TK2 , K2) and (TK3 , K3) for three cycles K1, K2, K3 ∈ K in Γ. Proof. Let x, y be the ends of L and let x ′ , y′ be the ends of L ′ . Without loss of generality, we may assume that K ∈ K1 and K′ ∈ K2. Let…
Figure 7
Figure 7. Figure 7: The possibilities for x, y, z and L as in Observation 5.2 where (T, B) is the canonical territory from [PITH_FULL_IMAGE:figures/full_fig_p013_7.png]

Discussion (0). Sign in 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

  1. Infinite induced-saturated graphs

    math.CO 2025-06 accept novelty 8.0 of 10

    For every finite graph H that is not a clique or independent set, a countable H-free graph exists such that any locally finite edit creates an induced copy of H.

Reference graph

Works this paper leans on

10 extracted references · 9 canonical work pages · cited by 1 Pith paper

  1. [1]

    Axenovich and M

    M. Axenovich and M. Csikós. Induced saturation of graphs.Discrete Math., 342(4):1195–1212, 2019

    work page 2019

  2. [2]

    Behrens, C

    S. Behrens, C. Erbes, M. Santana, D. Yager, and E. Yeager. Graphs with induced-saturation number zero. Electron. J. Combin., 23(1):Paper 1.54, 23, 2016

    2016

  3. [3]

    Bonamy, C

    M. Bonamy, C. Groenland, T. Johnston, N. Morrison, and A. Scott. Induced saturation forP5. https: //tomjohnston.co.uk/blog/2020-05-22-induced-saturation-for-paths.html

    work page 2020

  4. [4]

    E.-K. Cho, I. Choi, and B. Park. On induced saturation for paths.European J. Combin., 91:Paper No. 103204, 12, 2021

    work page 2021

  5. [5]

    Dvořák.Pn-induced-saturated graphs exist for alln ⩾ 6

    V. Dvořák.Pn-induced-saturated graphs exist for alln ⩾ 6. Electron. J. Combin., 27(4):Paper No. 4.43, 6, 2020

    work page 2020

  6. [6]

    F. Galvin. The list chromatic index of a bipartite multigraph.J. Combin. Theory Ser. B , 63(1):153–158, 1995

    work page 1995

  7. [7]

    Lazebnik and V

    F. Lazebnik and V. A. Ustimenko. Explicit construction of graphs with an arbitrary large girth and of large size. volume 60, pages 275–284. 1995. ARIDAM VI and VII (New Brunswick, NJ, 1991/1992)

    work page 1995

  8. [8]

    Linial and M

    N. Linial and M. Simkin. A randomized construction of high girth regular graphs.Random Structures & Algorithms, 58(2):345–369, 2021

    work page 2021

Show all 10 references
  1. [9]

    R. R. Martin and J. J. Smith. Induced saturation number.Discrete Math., 312(21):3096–3106, 2012

    2012

  2. [10]

    E. Räty. Induced saturation ofP6. Discrete Math., 343(1):111641, 3, 2020

    2020

Pith tools

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