The Ramsey number R(4,6)
Narrow the gap 36 ≤ R(4,6) ≤ 40. A 2-colouring of K_36 with no red K_4 and no blue K_6 would raise the lower bound; lowering the upper bound needs reproducible exhaustive computation.
Cite
@misc{cairn-ramsey-r46,
title = {The Ramsey number R(4,6)},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/ramsey-r46}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/ramsey-r46)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Beat the record — a computer checks it
Very hard Beats the record: A red/blue colouring of the edges of K₃₆ with no red K₄ and no blue K₆ (would show R(4,6) ≥ 37).
The lower bound 36 dates from 2012; circulant and Cayley colourings are the usual search space.
- Get a search program — your chatbot writes it from the prompt below
- Run it on your computer — it checks its own result and writes a file
- Upload the file — a computer checks it, usually within an hour; no reviewers
It happens: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), verified by a computer.
Other chatbot? · File format: Header `s: <red clique size>`, `t: <blue clique size>`, then the n×n 0/1 adjacency matrix of the red graph, one row per line.
Or give your chatbot a small task on this problem instead
ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
R(4,6) is the least n such that every red/blue colouring of the edges of K_n contains a red K_4 or a blue K_6. Equivalently, it is one more than the largest order of a graph with no K_4 and no independent set of size 6.
Known status. Exoo (2012) found 37 (4,6)-colourings of K_35 with a heuristic search, raising the lower bound from 35 to R(4,6) ≥ 36; McKay's Ramsey graph collection lists them. At that time the upper bound was 41 (McKay–Radziszowski); it has since been lowered to 40 by computations of Angeltveit and McKay (Radziszowski's survey, revision 18, 2026), so 36 ≤ R(4,6) ≤ 40.
What counts as progress
- Lower bound: a (4,6)-graph on 36 or more vertices. Level A: the ramsey checker verifies it.
- Upper bound: R(4,6) ≤ 39 via reproducible gluing/linear-programming/SAT computations, with code, intermediate data and certificates; partial results (e.g. degree constraints for a hypothetical (4,6,39)-graph) are welcome.
- Documented negative results: extension searches from the known K_35 colourings that fail (e.g. "no one-vertex extension of any of the 37 known graphs"), with code and hardware/runtime.
How it is checked. Lower-bound certificate: header s: 4, t: 6, then the n×n 0/1 adjacency matrix of the red graph (symmetric, zero diagonal), one row per line; the checker searches for a red K_4 and a blue K_6. Upper-bound work is reviewed for completeness of the case analysis and re-run by reviewers.
History of the bounds
| Year | Result | By |
|---|---|---|
| 1997 | R(4,6) ≤ 41 | McKay & Radziszowski |
| 2012 | R(4,6) ≥ 36 | Exoo |
| 2024 | R(4,6) ≤ 40 | Angeltveit & McKay |
Score: number of vertices n of a 2-colouring of K_n with no red K_4 and no blue K_6 (lower-bound certificate) (maximize)· checker ramsey