Ramsey Number

The Ramsey number , sometimes also denoted (e.g., Mattheus and Verstraete 2023), gives the solution to the party problem, which asks the minimum number of guests that must be invited so that at least will know each other or at least will not know each other. In the language of graph theory, the Ramsey number is the minimum number of vertices such that all undirected simple graphs of order contain a clique of order or an independent set of order (i.e., have clique number at least or independence number at least ). Ramsey's theorem states that such a number exists for all and .

An -Ramsey graph is a graph on vertices containing neither a clique of order nor an independent vertex set of order . It demonstrates that vertices do not suffice to guarantee either configuration.

By symmetry, it is true that

(1)

It also must be true that

(2)

A generalized Ramsey number is written

(3)

and is the smallest integer such that, no matter how each -element subset of an -element set is colored with colors, there exists an such that there is a subset of size , all of whose -element subsets are color . The usual Ramsey numbers are then equivalent to .

For a fixed 3-uniform hypergraph , let be the least such that every red-blue coloring of the triples of an -element set contains a red copy of or an -element set all of whose triples are blue. Gishboliner et al. (2026) proved that is bounded by a polynomial in iff embeds into some member of the following recursively defined family. Let consist of one vertex, with no hyperedges. Construct from three disjoint copies of by retaining all their hyperedges and adding every triple with one vertex in each copy. Such are called iteratively tripartite.

The multicolor triangle Ramsey number is denoted

(4)

For , 2, 3, ..., the sequence begins 3, 6, 17, ... (OEIS A003323). Tatarevic (2026) improved the four-color upper bound from 61 to . The proof combines incidence counting, small-neighborhood classifications, and exhaustive satisfiability problem computations. The mathematical reductions are formalized in Lean, while the final satisfiability exclusions are checked by two solvers rather than by that formalization. Tatarevic (2026) reports AI contributions to the mathematical reductions, computations, and formalization.

For six colors, Chen et al. (2026) obtained from their construction for the sixth Schur number.

An AI-generated proof given by OpenAI (2026c) established that there is an absolute constant such that

(5)

for every integer . Together with the classical factorial upper bound, this gives

			(6)
			(7)

Here the exponent uses big-Theta notation. This resolves whether multicolor triangle Ramsey numbers grow superexponentially. It also implies that Shannon capacity is unbounded among graphs having independence number 2.

Bounds are given by

(8)

and

(9)

(Chung and Grinstead 1983). Erdős proved that for diagonal Ramsey numbers ,

(10)

This result was subsequently improved by a factor of 2 by Spencer (1975). was known since 1980 to be bounded from above by , and Griggs (1983) showed that was an acceptable limit. J.-H. Kim (Cipra 1995) subsequently bounded by a similar expression from below, so

(11)

Burr (1983) gives Ramsey numbers for all 113 graphs with no more than 6 graph edges and no isolated points.

Mattheus and Verstraete (2023) proved that

(12)

as , where is big-omega notation. This determines up to a factor of order .

Refining this logarithmic gap, Lin and Zhang (2026) obtain as , using an external OpenAI theorem asserting for every fixed and sufficiently large .

Kandasamy et al. (2026) reported an explicit graph with no clique of order 5, more than vertices, and independence number less than for every prime power . This gives the constructive lower bound . Kandasamy et al. (2026) also gave a deterministic polynomial time construction establishing for every fixed . Here is big-omega notation; these improve constructive bounds, not the best unrestricted lower bounds.

Kandasamy et al. (2026) report that ChatGPT suggested an algorithm and assisted in developing parts of the proofs.

A summary of known results up to 1983 for is given in Chung and Grinstead (1983). Radziszowski (2021) maintains an up-to-date list of the best current bounds. The numbers whose exact values are known are summarized below.

			Reference
3	3	6	Greenwood and Gleason (1955)
3	4	9	Greenwood and Gleason (1955)
3	5	14	Greenwood and Gleason (1955)
3	6	18	Graver and Yackel (1968)
3	7	23	Kalbfleisch (1966)
3	8	28	McKay and Min (1992)
3	9	36	Grinstead and Roberts 1982
4	4	18	Greenwood and Gleason (1955)
4	5	25	McKay and Radziszowski (1995)

Exoo (1989) proved that and Angeltveit and McKay (2024) proved that , establishing

(13)

For graphs , let be the least such that every red-blue coloring of the edges of contains a red copy of or a blue copy of .

Cremer (2026) constructed explicit edge colorings giving the lower bounds and , improving the previous lower bounds of 134 and 343, respectively. A red-blue coloring of the complete graph contains neither a red clique of order 6 nor a blue clique of order 8. Two red-blue colorings of the complete graph contain neither a red clique of order 8 nor a blue clique of order 10. The colorings were checked with independent clique verification programs. Cremer (2026) reports using GPT-6.1 coding agents in the search, guided by the author.

The induced Ramsey number is the analogous quantity when the monochromatic copies must be induced subgraphs of the host graph. The host is no longer required to be a complete graph. The Kohayakawa-Prömel-Rödl conjecture, proved by Zhong et al. (2026), bounds this quantity polynomially in one graph order when the other graph is fixed.

For an integer , a loose triangle in an -uniform hypergraph consists of three hyperedges whose pairwise intersections are three distinct single vertices, with no vertex in all three. If denotes this loose triangle, Basu et al. (2026) proved for fixed . Equivalently, an -vertex loose-triangle-free -uniform hypergraph has a subset of its vertices containing no hyperedge, of size at least for sufficiently large , with depending only on . This concerns hypergraphs, not the ordinary triangle graph Ramsey problem.