Ramsey's Theorem

Ramsey's Theorem in its simplest form (that is known as the Friendship Theorem) asserts that if the C(6, 2) = 15 edges of the complete graph K₆ on six points are colored using two colors, there will be a monochromatic triangle (a K₃ subgraph of K₆ with all three edges having the same color.) More generally, Ramsey's theorem claims the existence of the Ramsey numbers R_m.

In a recent article, S. Golomb reports a result obtained by his student Herbert Taylor. As was observed by H. Taylor, the complete graphs on the number of points given by the Ramsey numbers R_m provide a sharp bound. (R_m is the smallest positive integer N such that, if a complete graph K_N on N points has all its C(N, 2) edges colored in m colors, there is at least one monochromatic triangle.)

Theorem

For every m ≥ 2, when a single edge is removed from the complete graph on R_m points, what remains can be colored with m colors without forming a monochromatic triangle.

Proof

Let's for convenience N = R_m. Then, by the definition of R_m, the edges of K_N-1 can be colored with m colors without generating a monochromatic triangle. Consider any such coloring. Pick any of the N-1 nodes of K_N-1 and denote it P. Add an N^th point P' that will serve as P's clone in the following sense: P' is to be connected to all the points Q of K_N-1, except P, and the new edges P'Q are to bear the color of PQ. Thus constructed graph has two properties:

1. This is practically K_N with only one edge (PP') missing.
2. It does not have a monochromatic triangle.

The first property is obvious. The second is almost so. If there is a monochromatic triangle P'Q₁Q₂, triangle PQ₁Q₂ is also monochromatic which is impossible due to our selection of the coloring.

Question: Missing (unproven and not mentioned by Golomb) is an assertion that any color selection for PP' leads to a monochromatic triangle. Something to think about.

As an example, there is a K₅ coloring and its expansion to K₆ less one edge that do not contain monochromatic triangles (node 6 clones node 1):

References

1. S. Golomb, Ramsey's Theorem is Sharp, Mathematics Magazine, v 79, n 4 (October, 2006), pp 304-306

Related material Read more...
	The Basic Rules of Counting
	Combinatorial Proofs
	Fibonacci Tilings
	The Inclusion-Exclusion Principle
	Inclusion-Exclusion Principle: an Example
	Coloring Points in the Plane
	Probabilities
	Example: A Poker Hand

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2012 Alexander Bogomolny