Small two-colour Ramsey numbers

The classical Ramsey number $R(k, l)$ is the size of a complete graph beyond which every red-blue edge colouring must contain a red $K_k$ or a blue $K_l$. Only nine nontrivial values are known exactly. This entry covers the table of small cases, where every improvement is either an explicit graph that can be checked in seconds or a large, repeatable computer proof.

Problem

$R(k, l)$ is the least $n$ such that every graph on $n$ vertices contains a clique of size $k$ or an independent set of size $l$. A graph on $n$ vertices with no $K_k$ and no independent set of size $l$ is a $(k, l)$-graph and shows $R(k, l) > n$.

Task: improve any entry of the table of bounds for $R(k, l)$ with $3 \le k \le 10$ and $k \le l \le 15$ other than $R(5,5)$, which has a project of its own (ramsey-number-r55), starting with the open cases $R(3, 10)$, $R(4, 6)$ and $R(3, 11)$.

Background

Ramsey numbers measure how much order is forced in large structures, and the exact small values have been pursued since the 1950s. Radziszowski's dynamic survey, revised regularly since 1994, records every known value and bound with its source. Lower bounds come from explicit graphs, often circulant graphs or graphs found by heuristic search; upper bounds come from counting arguments, linear programming and exhaustive computer enumeration, some now checked by SAT certificates or proof assistants.

What is known

From the survey's Table Ia (revision 18, April 2026):

• Exact values: $R(3,3) = 6$, $R(3,4) = 9$, $R(3,5) = 14$, $R(3,6) = 18$, $R(3,7) = 23$, $R(3,8) = 28$, $R(3,9) = 36$, $R(4,4) = 18$, $R(4,5) = 25$. The values $R(3,8)$ and $R(3,9)$ have been re-verified with checkable SAT proofs, and $R(4,5) = 25$ with the HOL4 proof assistant.
• Smallest open cases: $40 \le R(3,10) \le 41$ (Exoo, 1989; Angeltveit, 2025); $36 \le R(4,6) \le 41$ (Exoo, 2012; McKay and Radziszowski, 1997); $43 \le R(5,5) \le 46$ (Exoo, 1989; Angeltveit and McKay); $47 \le R(3,11) \le 50$ (Exoo, 2013; Goedgebeur and Radziszowski, 2013).
• Further out: for example $102 \le R(6,6) \le 165$ in Table Ia. The newest lower bounds are Exoo's for $R(5,6)$ (2023) and those of Nagda, Raghavan and Thakurta (2026 preprint) for $R(3,13)$, $R(3,18)$ and $R(4,k)$ with $k = 13, 14, 15$.
• Unpublished improvements: the survey's Table Ib lists better upper bounds from computations by Angeltveit and McKay (2019–2024), including $R(4,6) \le 40$ and $R(6,6) \le 160$.

What would count as progress

• A $(k, l)$-graph larger than the current lower bound allows, for example a 40-vertex triangle-free graph with no independent set of size 10, which would settle $R(3,10) = 41$. Checking one is fast: test for cliques and compute the independence number of a graph on a few dozen vertices, seconds.
• A lower upper bound, for example $R(3,10) \le 40$ (which would settle $R(3,10) = 40$) or $R(4,6) \le 39$, with code or a certificate (such as a DRAT proof) that others can rerun.
• Publication and independent verification of the Table Ib bounds.
• Lean statements for several Ramsey numbers are in formal-conjectures.

References

1. S. P. Radziszowski, "Small Ramsey numbers", Electronic Journal of Combinatorics, Dynamic Survey DS1, revision 18 (2026). doi:10.37236/21
2. G. Exoo, "On two classical Ramsey numbers of the form R(3,n)", SIAM Journal on Discrete Mathematics 2 (1989), 488–490. doi:10.1137/0402043
3. V. Angeltveit, "R(3,10) ≤ 41", Electronic Journal of Combinatorics 32(4) (2025), P4.30. doi:10.37236/12936
4. B. D. McKay and S. P. Radziszowski, "Subgraph counting identities and Ramsey numbers", Journal of Combinatorial Theory, Series B 69 (1997), 193–209. doi:10.1006/jctb.1996.1741
5. J. Goedgebeur and S. P. Radziszowski, "New computational upper bounds for Ramsey numbers R(3,k)", Electronic Journal of Combinatorics 20(1) (2013), P30. doi:10.37236/2824

Source

Imported from Small Ramsey Numbers (Radziszowski, dynamic survey DS1), Tables Ia and Ib, curated by Stanisław Radziszowski. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.