Verify a Ramsey lower-bound witness — morie_ramsey

A bound \(R(k,l) > n\) is proved by exhibiting a colouring of \(K_n\) with no red \(K_k\) and no blue \(K_l\). This checks one by exhaustive search over cliques, which is the only honest way to accept a witness.

Usage

morie_ramsey_witness(colouring, k, l)

Arguments

colouring: Symmetric 0/1 matrix.
k, l: Clique sizes to rule out.

Value

A list with valid, red_clique, blue_clique, certifies.

Examples

morie_ramsey_witness(colouring = 5L, k = 5L, l = 5L)
#> $valid
#> [1] TRUE
#> 
#> $red_clique
#> NULL
#> 
#> $blue_clique
#> NULL
#> 
#> $n
#> [1] 1
#> 
#> $certifies
#> [1] "R(5,5) > 1"
#>