Long Cycles in Induced-Ramsey Graph Constructions

Definitions and mathematical statement

The supplied record asks for a description of long cycles in Ramsey graphs subject to a restriction on short induced cycles. Its conventions and intended extremal quantity are not fully specified. The following gives a conditional formalization under the usual finite, simple, undirected graph and edge-colouring conventions; these conventions require confirmation.

For a graph $G$, let $V(G)$ and $E(G)$ denote its vertex and edge sets. A cycle of length $\ell\geq 3$ consists of distinct vertices $v_1,\ldots,v_\ell$ with edges $v_iv_{i+1}$ for $1\leq i<\ell$ and $v_\ell v_1$. It is induced if the subgraph on these vertices has exactly the cycle edges. For $r\geq 1$, put $[r]=\{1,\ldots,r\}$. Under the ordinary edge-Ramsey interpretation, \[ H\to(F)^r \quad\Longleftrightarrow\quad \forall c:E(H)\to[r]\;\exists F'\subseteq H\;\exists i\in[r]\quad \left(F'\cong F\ \text{and}\ \forall e\in E(F'),\ c(e)=i\right). \] Here $F'$ is a subgraph copy, which need not be induced. If induced Ramsey copies are intended, the requirement $F'\subseteq H$ must instead require $F'$ to be an induced subgraph. The supplied notation and title do not resolve this choice.

Interpreting a cycle being "inherited from a copy of $F$" as containment in a copy of $F$, the short-cycle condition is \[ \forall C\subseteq H,\qquad \left(C\text{ is an induced cycle in }H\ \text{and}\ |V(C)|\leq n\right) \ \Longrightarrow\ \exists F_C\subseteq H\quad \left(F_C\cong F\ \text{and}\ C\subseteq F_C\right). \] The copy $F_C$ may depend on $C$. Whether these copies must be induced, must belong to a designated family of copies, or must be the same kind of copies as those in the Ramsey condition is unspecified.

Problem as supplied, with unresolved target. Given a graph $F$ and integers $r,n$, describe how many cycles of length greater than $n$, and which kinds of such cycles, can occur in a graph $H$ satisfying $H\to(F)^r$ and the short induced-cycle inheritance condition above. The edge-colouring interpretation requires $r\geq1$; the source gives no explicit range for $n$. Under the displayed definition of a cycle, the short-cycle condition is vacuous when $n<3$. The source does not specify whether the long cycles must themselves be induced, how their number is counted, what constitutes a kind of cycle, or whether the requested result is a universal restriction, an extremal bound, or a construction with controlled long cycles. Thus these formulas describe conditional hypotheses, but the record does not determine a unique precise mathematical target.

Short English statement

For a given graph $F$ and parameters $r,n$, the question concerns cycles longer than $n$ in a graph $H$ that is Ramsey for $F$, while every short induced cycle lies inside a copy of $F$. The intended Ramsey convention, meaning of inheritance, and requested description of long cycles remain unresolved. The supplied partially solved label and dated literature assessment require independent review.

Sources

• Local UnsolvedMath registry, permanent ID $30004358$, source problem code catalogue entry, title: Long Cycles in Induced-Ramsey Graph Constructions. The record belongs to the Oberwolfach Reports Open Problems collection and records proposed year $2020$; no individual proposer is supplied.
• Supplied report citation: Combinatorics (2021), Oberwolfach Reports, DOI 10.4171/owr/2020/1, pp. 6--89. https://doi.org/10.4171/owr/2020/1. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The citation's year and the year appearing in the DOI are retained as supplied.
• Supplied literature source: Reiher--Rödl, Girth Ramsey theory. https://ems.press/content/serial-article-files/46836?nt=1.
• Literature assessment checked at 2026-08-22: the supplied curation labels the problem partially solved and states that the girth Ramsey theorem can force every induced cycle up to any prescribed length to lie inside a copy of the target graph, while leaving unrestricted longer-cycle structure unsettled. This is supplied dated curation derived from the OWR collection, not an independently verified literature assessment; its status and cited claims require independent verification.
• The registry labels the statement corrected_verified, explaining that mathematical content was preserved while notation, typography, omitted definitions, or duplicate clauses were repaired for self-contained publication. This is a supplied editorial qualification, not independent verification of the present formulation.