The alteration method

Colour \(K_n\) at random, then DELETE one vertex from each monochromatic \(K_k\). What remains is clean, and its expected size is \(n - \binom{n}{k} 2^{1 - \binom{k}{2}}\).

Usage

morie_alteration_ramsey(k)

Arguments

k

Clique size, at least 2.

Value

A list with bound, first_moment_bound, improvement, best_bound, optimal_n, search_capped.

Details

Asymptotically this gains a factor of 2 in the exponent, but it is NOT uniformly better than the plain union bound: at the union bound's own \(n\) the expected count is below 1, so the surviving set exceeds \(n - 1\), which after the floor can be \(n - 1\). Measured, the union bound wins by one at \(k = 4\) and \(k = 5\) and ties at \(k = 6\). Both are valid, so best_bound reports the maximum and improvement is signed.

References

Alon N, Spencer JH (2016), Ch 3.

Examples

morie_alteration_ramsey(k = 5L)
#> $bound
#> [1] 10
#> 
#> $certifies
#> [1] "R(5,5) > 10"
#> 
#> $first_moment_bound
#> [1] 11
#> 
#> $improvement
#> [1] -1
#> 
#> $best_bound
#> [1] 11
#> 
#> $optimal_n
#> [1] 13
#> 
#> $expected_survivors
#> [1] 10.48633
#> 
#> $search_capped
#> [1] FALSE
#> 
#> $search_cap
#> [1] 200000
#> 
#> $k
#> [1] 5
#> 
#> $n
#> [1] 10
#> 
#> $method
#> [1] "Alteration method (Alon and Spencer, Ch 3)"
#>