info prev up next book cdrom email home

Monochromatic Forced Triangle

Given a Complete Graph $K_n$ which is two-colored, the number of forced monochromatic Triangles is at least

\begin{displaymath}
\cases{
{\textstyle{1\over 3}} u(u-1)(u-2) & for $n=2u$\cr
...
...1$\cr
{\textstyle{2\over 3}} u(u+1)(4u-1) & for $n=4u+3$.\cr}
\end{displaymath}

The first few numbers of monochromatic forced triangles are 0, 0, 0, 0, 0, 2, 4, 8, 12, 20, 28, 40, ... (Sloane's A014557).

See also Complete Graph, Extremal Graph


References

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

Sloane, N. J. A. Sequence A014557 in ``The On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.




© 1996-9 Eric W. Weisstein
1999-05-26