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 K6 on six points are colored using two colors, there will be a monochromatic triangle (a K3 subgraph of K6 with all three edges having the same color.) More generally, Ramsey's theorem claims the existence of the Ramsey numbers Rm.

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 Rm provide a sharp bound. (Rm is the smallest positive integer N such that, if a complete graph KN 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 Rm points, what remains can be colored with m colors without forming a monochromatic triangle.

Proof

Let's for convenience N = Rm. Then, by the definition of Rm, the edges of KN-1 can be colored with m colors without generating a monochromatic triangle. Consider any such coloring. Pick any of the N-1 nodes of KN-1 and denote it P. Add an Nth point P' that will serve as P's clone in the following sense: P' is to be connected to all the points Q of KN-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 KN 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'Q1Q2, triangle PQ1Q2 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 K5 coloring and its expansion to K6 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|

    Copyright © 1996-2018 Alexander Bogomolny

    72088959