Ramsey number R(k, l), exactly or as an interval
Source:R/ramsey_theory_native.R
morie_ramsey_number.Rd\(R(k, l)\) is the least \(n\) such that every red-blue colouring of the edges of \(K_n\) contains a red \(K_k\) or a blue \(K_l\).
Value
A list with value (NULL when unknown), lower, upper,
exact, credit, erdos_szekeres_bound, warnings.
Details
Almost nothing is known. For \(k, l \ge 3\) exactly nine values have ever been determined and the list has not grown since 1995. \(R(5,5)\) is unknown, lying in [43, 46]. The difficulty is not that the problem is open-ended but that it is finite and enormous: settling \(R(5,5)\) by exhaustive search means examining the \(2^{903}\) colourings of \(K_{43}\).
A value is returned only when one is known, and an interval otherwise. Nothing is interpolated and no bound is ever returned as though it were a value.
The claim \(R(5,5) = 50\) circulates and is WRONG; DS1 records that it has been shown incorrect more than once and is still cited. Asking for it returns the interval and a warning.
References
Radziszowski SP, Small Ramsey Numbers, Electronic Journal of Combinatorics, Dynamic Survey DS1, revision 17 (2024), doi:10.37236/21 , Tables Ia and Ib.
Examples
morie_ramsey_number(k = 5L)
#> $k
#> [1] 5
#>
#> $l
#> [1] 5
#>
#> $value
#> NULL
#>
#> $lower
#> [1] 43
#>
#> $upper
#> [1] 46
#>
#> $exact
#> [1] FALSE
#>
#> $credit
#> [1] "DS1 Tables Ia and Ib (bounds only)"
#>
#> $erdos_szekeres_bound
#> [1] 70
#>
#> $warnings
#> [1] "R(5, 5) has never been determined. The interval is a pair of proofs, not an estimate, and the true value is not more likely to sit in the middle of it."
#> [2] "The frequently repeated claim that R(5,5) = 50 is incorrect. DS1 records that it has been shown wrong more than once and is still being cited. The published interval is [43, 46], with 43 conjectured."
#>
#> $method
#> [1] "Ramsey number lookup with certified bounds"
#>