R(4,6): bounds, history and how to improve them
The Ramsey number R(4,6) is known to lie between 36 and 40. Where the bounds come from, why the gap is hard to close, and what a new colouring or a new upper-bound computation would need to show.
Updated 2026-10-03 · CC BY 4.0
R(4,6) is the smallest n such that every red/blue colouring of the edges of the complete graph K_n contains a red K_4 or a blue K_6. In graph language: R(4,6) − 1 is the largest number of vertices of a graph with no clique of 4 vertices and no independent set of 6. It is one of the smallest open two-colour Ramsey numbers, and as of October 2026
36 ≤ R(4,6) ≤ 40.
Five possible values remain. This guide explains where each bound comes from and what it would take to move one.
History of the bounds
| Year | Bound | Who | How |
|---|---|---|---|
| 1997 | R(4,6) ≤ 41 | McKay and Radziszowski | subgraph counting identities and computer search |
| 2012 | R(4,6) ≥ 36 | Geoffrey Exoo | heuristic search found 37 colourings of K_35 |
| 2019–2024 | R(4,6) ≤ 40 | Vigleik Angeltveit and Brendan McKay | large gluing and linear-programming computations |
The lower bound is from Exoo's paper On the Ramsey number R(4,6) (Electronic Journal of Combinatorics 19, 2012), which raised it from 35 to 36. One of the colourings has an automorphism group of order 4 with one fixed point — a hint that symmetric constructions are a natural place to look for more. Brendan McKay's Ramsey graph collection lists the known extremal graphs.
The upper bound of 40 is recorded in Radziszowski's survey Small Ramsey Numbers (revision 18, April 2026) as one of the new upper bounds from Angeltveit and McKay's computations. The same project brought R(5,5) down to 46.
Why the gap is hard to close
Lower bounds need a single good colouring of K_36: a graph on 36 vertices with no K_4 and no independent set of size 6. The search space is astronomically large (there are 2^630 colourings of K_36), and no search so far has found one. Extending one of the 37 known colourings by a vertex is the obvious first attempt, and a documented failure of that search is itself useful.
Upper bounds need to rule out every colouring of K_40, i.e. show that no (4,6)-graph on 39 vertices exists. The standard approach looks at one vertex: its neighbourhood must be a (3,6)-graph and its non-neighbourhood a (4,5)-graph. Since R(3,6) = 18 and R(4,5) = 25, the degrees are tightly constrained, and the computation tries to glue all possible neighbourhoods together and shows it is impossible. The number of (3,6)- and (4,5)-graphs to consider is huge, which is why each step down has taken years.
What would count as progress
Even short of determining R(4,6), several results are useful and checkable:
- A colouring of K_36 with no red K_4 and no blue K_6. This would be a new lower bound, R(4,6) ≥ 37, and is checked in seconds.
- A proof that R(4,6) ≤ 39, with code, intermediate data and certificates so that it can be re-run.
- Partial structure results for a hypothetical (4,6)-graph on 39 vertices — degree restrictions, impossible neighbourhood types — each reducing the final computation.
- Documented negative results: an exhaustive search showing that no one-vertex extension of the known K_35 colourings exists, or that no circulant (or other symmetric) colouring of K_36 works, with code and running times. These are not new bounds, but they save everybody else the search.
- Independent re-verification of the upper-bound computation.
How to submit a colouring
The R(4,6) problem page accepts lower-bound certificates directly. The format is a header with s: 4 and t: 6, followed by the n × n 0/1 adjacency matrix of the red graph (symmetric, zero diagonal), one row per line. The Ramsey checker searches for a red K_4 and a blue K_6; if it finds neither, the claim is verified automatically and the leaderboard updates. For n = 36 the check takes well under a second.
Upper-bound work is submitted as a claim with its code and data and is reviewed: a reviewer re-runs the computation and checks that the case analysis is complete.
Approaches people try
- Symmetric constructions: circulant colourings, Cayley graphs of small groups, colourings with a prescribed automorphism — they shrink the search space enormously.
- Local search and simulated annealing, starting from the known K_35 colourings or from random ones, minimising the number of red K_4's plus blue K_6's.
- SAT solvers with symmetry breaking, for both directions: finding a colouring or proving none exists in a restricted class.
- Machine-learning-guided search, in the spirit of recent work on constructions in combinatorics.
Related
- Small Ramsey numbers — table of known values and bounds
- The Ramsey number R(5,5): 43 ≤ R(5,5) ≤ 46.
- All Ramsey theory problems in the catalogue.