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.
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
. The solution for
is currently unknown, and it is predicted that the solution to
will never be known.