Goodman's Formula

A two-coloring of a Complete Graph $K_n$ of $n$ nodes which contains exactly the number of Monochromatic Forced Triangles and no more (i.e., a minimum of $R+B$ where $R$ and $B$ are the number of red and blue Triangles) is called an Extremal Graph. Goodman (1959) showed that for an extremal graph,

$$R+B = \left\{\begin{array}{ll} {\textstyle{1\over 3}} m(m-1)(m-2) & \mb... ...\ {\textstyle{2\over 3}} m(m+1)(4m-1) & \mbox{for $n=4m+3$.}\end{array}\right.$$

Schwenk (1972) rewrote the equation in the form

$$R+B={n\choose 3}-\left\lfloor{{\textstyle{1\over 2}}n\left\l... ...r{{\textstyle{1\over 4}}(n-1)^2}\right\rfloor }\right\rfloor ,$$

where ${n\choose k}$ is a Binomial Coefficient and $\left\lfloor{x}\right\rfloor$ is the Floor Function.

See also Blue-Empty Graph, Extremal Graph, Monochromatic Forced Triangle

References

Goodman, A. W. ``On Sets of Acquaintances and Strangers at Any Party.'' Amer. Math. Monthly 66, 778-783, 1959.

Schwenk, A. J. ``Acquaintance Party Problem.'' Amer. Math. Monthly 79, 1113-1117, 1972.