Colour each edge of \(K_n\) independently at random. The expected
number of monochromatic \(K_k\) is
\(\binom{n}{k} 2^{1 - \binom{k}{2}}\); if that is below 1 then some
colouring has none, so \(R(k,k) > n\).
Usage
morie_ramsey_lower_bound_probabilistic(k)
Arguments
- k
Clique size, at least 2.
Value
A list with bound, certifies, expected_at_bound,
asymptotic_2_to_k_over_2.
Details
The argument proves an object exists without producing one, and
seventy-five years later no explicit construction comes close. The
union-bound calculation is also stronger than the clean
\(2^{k/2}\) form usually quoted from it.
References
Erdos P (1947) Bulletin of the AMS 53:292-294.
Examples
morie_ramsey_lower_bound_probabilistic(k = 5L)
#> $bound
#> [1] 11
#>
#> $certifies
#> [1] "R(5,5) > 11"
#>
#> $expected_at_bound
#> [1] 0.9023438
#>
#> $asymptotic_2_to_k_over_2
#> [1] 5.656854
#>
