Ramsey's Theorem in its simplest form (that is known as the Friendship Theorem) asserts that if the
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
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.
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
- This is practically KN with only one edge (PP') missing.
- 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):
Copyright © 1996-2018 Alexander Bogomolny