Erdos's first-moment lower bound on the diagonal Ramsey number

Colouring \(K_n\) at random, the expected number of monochromatic \(K_k\) is \(\binom{n}{k} 2^{1 - \binom{k}{2}}\); below 1 it proves \(R(k,k) > n\).

Usage

morie_first_moment_ramsey(k)

Arguments

k

Clique size, at least 2.

Value

A list with bound, certifies, expected_at_bound, search_capped, warnings.

Details

A search that runs to its own ceiling has found the CEILING, not the bound, so search_capped is reported and warned about rather than letting the cap read as a result.

References

Erdos P (1947) Bull AMS 53:292-294.

Examples

morie_first_moment_ramsey(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
#> 
#> $search_capped
#> [1] FALSE
#> 
#> $search_cap
#> [1] 100000
#> 
#> $k
#> [1] 5
#> 
#> $n
#> [1] 11
#> 
#> $warnings
#> character(0)
#> 
#> $method
#> [1] "First moment method (Erdos 1947)"
#>