Polynomial size even-cycle induced saturation

Question 1.8 · arXiv:2505.24100

arXiv Question high confidence— first stated 2025-06-02

Authors: Xinyue Fan, Sahab Hajebi, Sepehr Hajebi, Sophie Spirkl

Status open high confidence

Question 1.8 from arXiv:2505.24100 asks whether a polynomial $f$ suffices to bound the size of an induced-saturated graph for $C_{2t-2}$, replacing the doubly-exponential construction of Theorem 1.6. The authors themselves state they have no rationale for expecting the vertex count to exceed linear in $t$, but no polynomial construction or impossibility result has been found in the literature as of May 2026.

Reviewer notes. No follow-up paper resolving or making partial progress on Question 1.8 was found in five web calls. The paper is approximately 11 months old. The conjecture is open: the only known construction (Theorem 1.6 of the source paper) is doubly exponential in t, while the question asks whether polynomial size in t is achievable.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Question. Does there exist a polynomial $f$ such that for every $t\geq 3$, there is a graph $G$ on at most $f(t)$ vertices with $E(G)\neq\varnothing$, such that $G$ is $H$-free but $G-e$ has an induced subgraph isomorphic to $C_{2t-2}$ for every $e\in E(G)$?

Context

The construction of $G_t$ in Theorem 1.6 has doubly exponential size in $t$. The authors remark they do not even have a rationale for expecting the number of vertices to be more than linear in $t$, making this a natural question about the efficiency of the construction.

Source paper

Halfway to induced saturation for even cycles
Xinyue Fan, Sahab Hajebi, Sepehr Hajebi, Sophie Spirkl · 2025-06-02
https://arxiv.org/abs/2505.24100