Monochromatic triangles by Goodman's identity — morie_goodman

For any two-colouring of $K_n$, a triangle fails to be monochromatic exactly when two of its vertices see one edge of each colour. Summing over vertices counts each such triangle twice, so $$\#mono = \binom{n}{3} - \frac{1}{2}\sum_v r_v b_v,$$ with $r_v$, $b_v$ the red and blue degrees. This is an IDENTITY holding exactly for every colouring, not an approximation; brute_force = TRUE checks it against direct enumeration.

Usage

morie_goodman_triangles(colouring, brute_force = FALSE)

Arguments

colouring: Symmetric 0/1 matrix; 1 marks a red edge.
brute_force: Also enumerate all triangles and check.

Value

A list with monochromatic, bichromatic, total_triangles, goodman_minimum, identity_residual.

Details

The identity is what makes $R(3,3) \le 6$ provable by hand. Since $r_v + b_v = n-1$, the product is at most $\lfloor (n-1)^2/4 \rfloor$, so at $n = 6$ the count is at least $20 - 18 = 2$: every colouring of $K_6$ contains not one monochromatic triangle but two. At $n = 5$ the bound gives zero and the five-cycle attains it.

References

Goodman AW (1959) American Mathematical Monthly 66(9):778-783.

Examples

set.seed(6)
col <- matrix(rbinom(36, 1, 0.5), 6); col[lower.tri(col)] <- t(col)[lower.tri(col)]; diag(col) <- 0
morie_goodman_triangles(col, brute_force = TRUE)[c("monochromatic", "identity_residual")]
#> $monochromatic
#> [1] 3
#> 
#> $identity_residual
#> [1] 0
#>