Exact cycle–clique Ramsey numbers

Source and verification

This article explains family 189 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Exact cycle–clique Ramsey numbers

For graphs $H,J$, the Ramsey number $R(H,J)$ is the least $N$ such that every red-blue coloring of $K_N$ contains a red $H$ or a blue $J$. Copies are not required to be induced. The cycle $C_m$ has exactly $m$ vertices.

Manuscript claim

For all integers $m\ge n\ge 3$ except $(m,n)=(3,3)$,

$$\begin{array}{c}R(C_m,K_n)\\ =(m-1)(n-1)+1.\end{array}$$

The exceptional value is $R(C_3,K_3)=6$. (OpenAI, 2026)

The exact cycle length matters. Producing some long red cycle, or a cycle with at least $m$ vertices, is not enough. The assertion does not include the whole range $m<n$.

🏷️ The lower construction and the exception

Take $n-1$ disjoint blocks of $m-1$ vertices. Color all edges within blocks red and all edges between blocks blue. A red cycle lies inside one block, so cannot have length $m$. A blue clique uses at most one vertex per block, so cannot have size $n$.

This gives the lower bound $(m-1)(n-1)+1$. The upper-bound problem is to show that adding one vertex always forces one of the specified graphs.

For triangles in both colors, a red five-cycle on five vertices has a blue complement that is also a five-cycle, giving $R(3,3)>5$. In $K_6$, one vertex has three incident edges of one color. If any edge among those three neighbors has that color, it closes a monochromatic triangle; otherwise the three neighbors form a triangle of the other color. Thus $R(3,3)=6$.

🏷️ Independent-set expansion from minimality

Set $k=m-1$ and $a=n-1$. A counterexample to the upper bound gives a red graph with no cycle of length $k+1$ and independence number at most $a\le k$.

Holding $k$ fixed and minimizing the remaining parameter yields the expansion condition

$$|N[I]|\ge k|I|+1$$

for every nonempty independent set $I$, where $N[I]$ is its closed neighborhood. In particular, a singleton gives minimum degree at least $k$.

The source uses rooted distance layers and path rotations to force a clique of size at least $\max \{3,\lfloor k/2\rfloor \}$. A path rotation changes an endpoint while retaining the same vertex set, allowing neighborhood restrictions to be accumulated without losing the available path length.

This structural reduction is stronger than a generic minimum-degree argument. The forbidden exact length and independent-set expansion together constrain how paths can return to the clique.

🏷️ Maximizing a system of external paths

For $k\ge 5$, choose a maximum clique $Q$ of size $t$. Consider paths joining its vertices, with nonempty interiors outside $Q$, disjoint interiors, and endpoint pairs forming disjoint chains. The amount of the system is the total number of interior vertices.

Maximize the amount below $k+1-t$, then minimize the number of paths among maximizers. Certain replacements or additions would allow the system to close through the clique into a cycle of exactly $k+1$ vertices, so they are forbidden.

These forbidden improvements force suitable neighborhoods of path vertices to be disjoint and anticomplete, meaning no edges join different neighborhoods. Expansion then supplies independent vertices from each. A separate size lemma raises some available independent-set contributions from two to three.

For $t\ge 9$, a numerical classification of the resulting inequalities gives more than $k$ independent vertices, contradicting $a\le k$. The small cases $k=3,4$ are handled directly; the triangle case is separate.

🏷️ The finite remainder

If $3\le t\le 8$, the earlier clique-size lower bound forces $5\le k\le 17$. A pattern records the interior-vertex counts along each chain, up to reversal and permutation of components.

The manuscript reduces this remainder to 3,099 parameter-pattern instances across 42 admissible pairs $(k,t)$. Its inference rules include path replacement, exact-cycle closure, neighborhood growth, independent-set packing, and contradictions created by adding an edge or a path with one new interior vertex.

The computation enumerates these patterns, not all graphs or all edge colorings. This is a finite certificate only after the structural theorem shows that every possible counterexample gives one of the enumerated patterns and the inference rules are proved sound.

The source reports two exact implementations and deduction traces. Those programs and traces were not executed for this post. The review here covers the main statement, structural reduction, and described certificate boundary; the finite remainder remains attributed to the manuscript.

🏷️ Relation to asymptotic results

Earlier asymptotic results already cover all but finitely many pairs in the range $m\ge n$. That does not identify or settle the remaining pairs unless the relevant constants are known and the remainder is checked.

The present manuscript instead supplies an explicit structural reduction to the bounded $(k,t)$ range above, independent of an unspecified asymptotic constant. This distinction explains how a theorem with an exact formula for every parameter differs from an eventual asymptotic result.

🏷️ Key steps and proof outlines

Minimality produces expansion with the indispensable extra vertex

Fix $k=m-1$ and choose the smallest $a=n-1$ admitting a graph $G$ on $ka+1$ vertices with no $C_{k+1}$ and $\alpha (G)\le a$. For every $b<a$, any $C_{k+1}$-free graph with independence number at most $b$ has at most $kb$ vertices. The cases $b=0,1$ follow directly from emptiness and completeness; the remaining cases follow from minimality. (OpenAI, 2026)

If $I$ is independent of size $r$, then $G-N[I]$ has independence number at most $a-r$, because any independent set there can be adjoined to $I$. Hence

$$|G-N[I]|\le k(a-r),|N[I]|\ge ka+1-k(a-r)=kr+1.$$

This proves more than minimum degree. The extra one persists when an entire independent pair or triple is deleted, and later supplies strict neighborhood inequalities.

Close a path system at exactly the forbidden length

Let $Q$ be a maximum clique of size $t$ and put $h=k+1-t$. Replace selected clique edges forming a linear forest by paths whose nonempty interiors lie outside $Q$ and are pairwise disjoint. Call the total number of interior vertices $q$, and the number of incident clique vertices $v$.

Exact-length closure interval

A system with $h\le q\le k+1-v$ already gives a forbidden cycle. Choose $u=k+1-q-v$ unused clique vertices; the inequalities say $0\le u\le t-v$. Expand the chains, adjoin those $u$ vertices as singleton paths, and join their endpoints through clique edges. The resulting cycle has exactly $q+v+u=k+1$ vertices.

Now maximize the amount $L<h$, and among maximizers minimize the number $e$ of assigned paths. A replacement system with amount $A$, $e^{\prime }$ paths, and $v^{\prime }$ incident clique vertices is impossible whenever

$$L+1_{\{e^{\prime }\ge e\}}\le A\le k+1-v^{\prime }.$$

Above $h$ this is exact-cycle closure; below $h$ it contradicts the first optimization, or the second if the amount stays equal and the number of paths decreases. Keeping both optimization criteria makes this one inequality reusable throughout the proof.

Representatives preserve every old interior vertex during replacement

Orient each chain. A chain’s first clique vertex represents itself; any later target clique vertex is represented by the first interior vertex of its incoming path. There are exactly $t$ distinct representatives. An outside path between two representatives can be extended along their retained incoming segments to join the corresponding targets.

Delete their zero, one, or two incoming paths and insert this combined path. No old interior vertex is lost; if the new outside path has $d$ interior vertices, the amount increases from $L$ to $L+d$. The represented graph remains a linear forest because deleting the incoming edges separates the two targets before the new edge is inserted. In particular, a one-interior-vertex detour is impossible by optimality and exact-length closure.

Let $S$ be the clique and all assigned interiors, and let $B_j(x)$ be the vertices within distance $j$ in $G-S$ of the outside neighbors of a representative $x$. If two representatives have no outside path with one through $r+s+2$ interior vertices, their balls $B_r,B_s$ are disjoint and anticomplete: an intersection or joining edge would concatenate the two short paths into precisely such a forbidden path.

Turn separated neighborhoods into too many independent vertices

Minimum degree and the one-vertex exclusions give $|B_1(x)|\ge k-|S|+t\ge t$. For the second-ball conclusions, assume additionally that no outside path with one or two internal vertices joins $x$ to another representative. This ensures that every vertex of $B_1(x)$ misses the other representatives; the later contradiction argument excluding paths with at most six internal vertices supplies this hypothesis. The second ball cannot be a clique: equality in all degree bounds would make it a clique of size $t$ adjacent to $x$, contradicting maximality of $Q$. Thus every second ball contains an independent pair.

If a first ball contains an independent pair, the expansion inequality improves its second ball to size at least $k+t$. When $t<k$, this exceeds both $k$ and $2t$. The source’s size lemma then provides an independent triple. Its proof is concrete: a graph of independence number at most two and order greater than $2t$ cannot be disconnected or have a cutvertex under clique bound $t$; it is Hamiltonian, and successive one-vertex shortenings reach the forbidden length $k+1$.

For the shortening step, either a cycle has a distance-two chord, which bypasses one vertex, or absence of all such chords forces every cyclic distance-four chord: otherwise three vertices spaced by two would be independent. Those distance-four chords explicitly rearrange the cycle to omit one vertex.

If no outside path with at most six interior vertices joins representatives, all $t$ second balls are separated. Their independent pairs give $2t$ independent vertices; in the borderline cases $k=2t$ or $2t+1$, two independent triples raise this to $2t+2>k$. This drives the large-clique contradiction. The remaining small patterns still require the manuscript’s finite deductions; the structural and size arguments do not themselves execute that certificate. See the reduction, size, optimal-path-system, and growth sections.

See Also

• Off-diagonal clique Ramsey bounds determines logarithmic exponents, rather than an exact integer formula.
• Snaky certificates explains a finite recursive proof whose supplied checkers were executed during this series review.

🏷️ Manuscripts and verification scope

• Cycle–clique Ramsey numbers — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects the complete stated parameter range and the exceptional triangle–triangle value. The finite pattern computations were not executed in this review. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Cycle–clique Ramsey numbers.