The exact threshold for a red cycle or a blue clique

← All digests

Family 189 · Combinatorics
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Imagine coloring every connection between a group of people red or blue. How many people guarantee either a red cycle through exactly $m$ distinct people or a group of $n$ people whose mutual connections are all blue?

Ramsey theory studies such unavoidable patterns. Its answers are often difficult even when the patterns sound simple. This family concerns the cycle–clique Ramsey number, where one color must contain a cycle of a prescribed length and the other a complete graph.

There is a particularly natural way to avoid both outcomes. Make $n-1$ separate red groups, each containing $m-1$ vertices, and color every connection between groups blue. No red cycle can reach $m$ vertices, while a blue clique can take at most one vertex from each group.

This construction uses $(m-1)(n-1)$ vertices. The conjecture addressed by the manuscript says that, when $m\ge n\ge3$, just one additional vertex forces one of the desired patterns, with a single small exception. The claim is an exact threshold, not an asymptotic estimate.

2. Background and essential definitions

A simple graph consists of vertices and edges joining distinct pairs of vertices, without repeated edges. The complete graph $K_n$ has every possible edge on its $n$ vertices. A clique is a set of vertices whose pairs are all joined.

The cycle $C_m$ has $m$ distinct vertices arranged around a closed route, with consecutive vertices joined. Its order and length are both $m$. Finding $C_m$ means finding exactly that cycle length; a longer cycle alone does not satisfy the requirement.

For two graphs $H$ and $J$, the Ramsey number $R(H,J)$ is the smallest integer $N$ such that every red–blue coloring of the edges of $K_N$ contains a red copy of $H$ or a blue copy of $J$. Copies here need not be induced: extra edges between the chosen vertices are allowed.

There is an equivalent formulation using just one graph $G$. Declare its edges red and its missing edges blue. A blue clique becomes an independent set in $G$, meaning a set containing no edges. Thus the desired upper bound says that every graph on $(m-1)(n-1)+1$ vertices has a cycle of length $m$ or an independent set of size $n$.

Write $\alpha(G)$ for the largest size of an independent set and $\omega(G)$ for the largest size of a clique. These two quantities measure opposite kinds of organization inside the same graph.

For a vertex set $I$, its closed neighborhood $N[I]$ consists of $I$ itself and every vertex adjacent to at least one member of $I$. A lower bound on $|N[I]|$ expresses expansion: a small set must reach many vertices.

3. Development history and previous partial results

The cycle–clique problem developed through a long sequence of exact cases and general parameter ranges. The case of a blue triangle goes back to Chartrand and Schuster in 1971. Bondy and Erdős proved the formula in 1973 when the red cycle was sufficiently long, specifically for $m\ge n^2-2$. Erdős, Faudree, Rousseau, and Schelp’s 1978 paper is the conjectural reference used by M1.

A succession of papers resolved all conjectured cycle lengths for clique sizes $n=4,5,6,7$, together with several cases for $n=8$. Nikiforov obtained a much wider general range, $m\ge4n+2$ for $n\ge4$. These results progressively reduced the gap between a cycle much longer than the clique and the boundary case $m=n$.

A major later advance came from Keevash, Long, and Skokan. Their theorem establishes the formula whenever

$$m\ge C\frac{\log n}{\log\log n},$$

with an absolute constant $C$, using suitable logarithm conventions for small $n$. Their paper was published in 2021. In particular, its threshold is smaller than $n$ once $n$ is sufficiently large. It therefore already covers all sufficiently large pairs in the conjectured range $m\ge n$. Their article explains this near-logarithmic cycle-length regime.

For each of the finitely many remaining clique sizes, their theorem also covers all sufficiently large cycle lengths. Consequently, only finitely many pairs in the stated conjecture were left outside its reach.

M1 claims to complete that remaining range. Its structural argument produces an explicit finite calculation without requiring a numerical value for the constant in the Keevash–Long–Skokan theorem. The distinction is essential: the new claim completes an exact conjecture whose broad asymptotic range had already been settled.

4. What the new manuscripts claim

The family contains one manuscript, M1. It states that for all integers $m\ge n\ge3$, except $(m,n)=(3,3)$,

$$R(C_m,K_n)=(m-1)(n-1)+1.$$

The exceptional value is

$$R(C_3,K_3)=6.$$

Since $C_3$ is itself a triangle, this is the familiar two-color triangle Ramsey number. The general formula would give five for this pair, so recording the exception changes the answer.

For example, the claimed formula gives $R(C_8,K_6)=36$. The lower construction uses five disjoint red complete graphs of order seven, for a total of 35 vertices. M1’s theorem says that every coloring on 36 vertices contains a red eight-cycle or a blue six-clique. This illustrates the formula; the novelty of the family lies in completing the whole stated parameter range, not in every individual numerical instance.

The cycle length remains exact, the copies remain ordinary rather than induced, and the hypothesis $m\ge n$ is part of the theorem. The claim does not provide a formula for every pair of cycle and clique sizes outside that region.

5. Why the advance matters

Importance: 3/5. An exact resolution of a long-standing Ramsey conjecture is a substantial contribution. The rating also reflects the strong earlier theorem: the unsettled portion was finite, rather than a previously unknown asymptotic range.

Exact Ramsey values expose extremal structure particularly clearly. Here the simplest obstruction, a union of small complete graphs, is claimed to remain optimal throughout the conjectured range. Adding a single vertex then forces a cycle of precisely the requested length or a larger independent set.

The argument is also an example of combining structural graph theory with a finite symbolic calculation. The computation described by M1 handles constrained path patterns after the general theory has compressed the problem. It is not an enumeration of all edge colorings up to an enormous vertex bound.

The scope is narrower than a general solution of Ramsey numbers. It nevertheless gives a complete answer for a natural two-parameter family and clarifies why the obvious lower construction has the correct size.

6. The main idea

A minimal obstruction must expand

Set $k=m-1$ and $a=n-1$. A counterexample to the upper bound would be a graph with

$$|V(G)|=ka+1,\qquad \alpha(G)\le a,$$

and no cycle of length $k+1$. Here $V(G)$ is the vertex set. The argument holds $k$ fixed and chooses a counterexample with the smallest possible $a$.

That minimality makes independent sets expand. M1 obtains, for every nonempty independent set $I$,

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

The intuition is deletion. If $I$ and its neighbors occupied too few vertices, the remaining graph would be large enough to contradict minimality: an independent set there could be combined with $I$, because no edges connect the two sets.

In particular, a one-vertex set shows that every vertex has at least $k$ neighbors. The graph cannot avoid the desired patterns merely by being sparse or split into small isolated pieces.

Use a clique as a reservoir of closing edges

The next structural step finds a clique $Q$ of order $t$ with

$$\max\{3,\lfloor k/2\rfloor\}\le t\le k.$$

The floor symbol means rounding down to an integer. M1 obtains this through distance layers from a root vertex and controlled changes to paths, building on established cycle–clique ideas.

A clique is useful because its vertices can be joined in many orders. The argument considers paths whose endpoints lie in $Q$ and whose interior vertices lie outside it. Their interiors must be disjoint, and their endpoint connections form disjoint chains. Combining these excursions with edges inside the clique can create cycles of specified lengths.

Call the total number of outside interior vertices the system’s amount. The manuscript chooses a system with maximum amount below $k+1-t$, breaking ties by using fewer paths. This optimization puts it just below the point where suitable closing edges could produce the forbidden cycle.

Possible improvements now become restrictions. If a new path or edge would increase the amount appropriately, it would close a cycle of length $k+1$, so that possibility must be absent. The resulting separations between neighborhoods allow independent sets to be assembled. Expansion makes those sets too large for the assumed bound on $\alpha(G)$.

Reduce the final cases to finite patterns

The structural analysis treats cliques of order $t\ge9$. The remaining range satisfies

$$3\le t\le8,\qquad 5\le k\le17,$$

after the smaller cycle cases are handled separately.

A pattern records the numbers of interior vertices along the chains, identifying descriptions that differ only by reversing chains or reordering components. M1 reports 3,099 such parameter-pattern instances across 42 admissible pairs $(k,t)$.

Its finite argument applies rules for replacing paths, closing exact cycles, growing neighborhoods, and packing independent sets. The manuscript reports two exact implementations and accompanying deduction traces that exclude every remaining pattern. This describes the stated computational component of the argument; the mathematical object being processed is the compressed path system, not an arbitrary colored complete graph.

7. Scope, limitations, and open questions

The theorem claims full coverage of $m\ge n\ge3$, with the one explicit exception. It makes no claim that the same formula holds without the order condition on $m$ and $n$. Much of cycle–clique Ramsey theory outside that range remains a different question.

A cycle copy can have chords, because the theorem is not induced Ramsey theory. Likewise, a cycle on more than $m$ vertices is not a substitute for the specified $C_m$. Both distinctions are important when translating the result into ordinary graph language.

The manuscript’s finite computation is part of its reported argument. The existence of programs or traces is not itself a claim about an efficient general-purpose algorithm for finding the red cycle or blue clique in a large input coloring.

Natural further directions include sharper descriptions of colorings just below the threshold and stronger results when the cycle is shorter than the clique. Those questions ask for information beyond the exact numerical formula completed here.

8. Sources and further reading

• Keevash, Long, and Skokan, Cycle-complete Ramsey numbers, for the earlier near-logarithmic cycle-length threshold.
• Bondy and Erdős, Ramsey numbers for cycles in graphs, Journal of Combinatorial Theory, Series B 14 (1973), 46–54, for an early general range.
• Erdős, Faudree, Rousseau, and Schelp, On cycle–complete graph Ramsey numbers, Journal of Graph Theory 2 (1978), 53–64, for the conjecture and structural antecedents.

M1 lists the primary papers for the successive small clique sizes and describes its finite path-pattern calculation.

Source manuscripts

• M1. OpenAI, Cycle–clique Ramsey numbers (September 25, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.