Upper bounds on R(k, l) from the classical arguments

The recursion is \(R(k,l) \le R(k-1,l) + R(k,l-1)\), STRICT when both terms on the right are even. Unrolling it with \(R(2,l) = l\) gives the Erdos-Szekeres binomial bound \(\binom{k+l-2}{k-1}\), which is much weaker.

Usage

morie_ramsey_upper_bound(k, l, use_known = TRUE)

Arguments

k, l

Clique sizes.

use_known

Consult the table of known values during recursion.

Value

A list with binomial, recursive, best, parity_saving, used_known_values.

Details

use_known decides whether the recursion may short-circuit on the nine tabulated values. On, it gives the tightest answer but makes the result partly a lookup; off, it gives what the argument alone supports. The two differ: 25 against 31 for \(R(4,5)\). Any claim that the recursion reproduces a known value must use FALSE.

References

Greenwood RE, Gleason AM (1955) Canadian Journal of Mathematics 7:1-7. Erdos P, Szekeres G (1935) Compositio Mathematica 2:463-470.

Examples

morie_ramsey_upper_bound(k = 5L, l = 5L)
#> $binomial
#> [1] 70
#> 
#> $recursive
#> [1] 50
#> 
#> $best
#> [1] 50
#> 
#> $parity_saving
#> [1] 20
#> 
#> $used_known_values
#> [1] TRUE
#>