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-09-28}
} Also: CITATION.cff · Atom feed of results
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
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 (4,6)-colourings of K_35 by simulated annealing and tabu search, proving R(4,6) ≥ 36; McKay's Ramsey graph collection lists 37 such graphs on 35 vertices. At that time the upper bound was 41; it has since been lowered to 40 (attributed to Angeltveit and McKay in the Radziszowski survey, as reflected in current tables), 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.
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