Ramsey(3,3) = 6

The game of Sim, invented by Gustavus Simmons, matches Red against Blue on a hexagonal field of six dots. The players take turns drawing a line of their respective color between pairs of unconnected dots, losing if they make a triangle of their own color first.
This Demonstration shows all the 32768 2-colorings of the hexagon. When a set of vertices makes a triangle, the vertices are circled. All of the colorings contain at least one triangle.
The Ramsey problem asks for the smallest so that the complete graph always contains a smaller monochromatic subgraph , no matter how is 2-colored. The graph that connects three points, , is a triangle. Since can be 2-colored with no triangles (red star, blue pentagon), and since always contains a triangle, the solution to the Ramsey problem is 6. The solution for is 18, with the 17-Paley graph and its inverse providing a 2-coloring for without . The solution for is currently unknown, and it is predicted that the solution to will never be known.

THINGS TO TRY

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.