Ramsey's Realm Games

If you'd like to read more about Ramsey Theory, the mathematics behind these games, then please check out my post https://drakeomath.wordpress.com/2022/08/15/ramseys-realm/.

Have fun!

Ramsey's Realm: two colors

Non-Example 1

Ramsey's Realm: three colors

Ramsey's Realm: four colors

Ramsey's Realm: two colors

Goal:

Color each edge red or blue in such a way that no three vertices have all the edges between them colored the same. That is, your coloring should not have a monochromatic triangle: a monochromatic triangle is a set of three vertices such that all the edges between them are colored the same.

With two colors, this means that there is no red triangle and no blue triangle in a correct solution.

Note: The vertices are the big circles. Crossings between lines are not considered vertices here.

Avoid! ---->

Non-Example 1

This configuration is not a solution because the three vertices 0,1, and 3 form a red triangle.

Non-Example 2

This is also not a solution. This time, there is a blue triangle formed by the vertices 0, 1, and 2.

Instructions:

Toggle the color of an edge from uncolored to red to blue by clicking on the edge. You can revert an edge back to uncolored by clicking on it when it is blue. You can use the "Reset All" button to uncolor all the edges at once.

Check:

When you think you have a solution, click the "Check" button.

Four Vertices

Five Vertices

The solution can be found here: Ramsey's Realm Game 1: Solution and Analysis

Six Vertices

Warning: There are no solutions! Can you discover and explain why?

I encourage you to think about why there are no solutions here.

Hints:

In the two previous games on K4 and K5, can you find a solution where a vertex is incident with at least three edges of the same color?
Can you find any red-blue coloring of K6 that does not have a vertex with at least three incident edges of the same color?

Read my complete explanation - along with some helpful figures - here: Ramsey's Realm Game 2: Solution and Analysis.

Ramsey's Realm: three colors

Goal:

Color each edge red, blue, or green in such a way that no three vertices have all the edges between them colored the same. That is, your coloring should not have a monochromatic triangle: a monochromatic triangle is a set of three vertices such that all the edges between them are colored the same.

With two colors, this means that there is no red triangle, no blue triangle, and no green triangle in a correct solution.

Note: The vertices are the big circles. Crossings between lines are not considered vertices here.

Instructions:

Toggle the color of an edge from uncolored to red to blue to green by clicking on the edge. You can revert an edge back to uncolored by clicking on it when it is green. You can use the "Reset All" button to uncolor all the edges at once.

Start with five vertices, find a solution, and then increase the level (# of vertices). See how far you can go!

Check:

When you think you have a solution, click the "Check" button.

Warning: The maximum number of vertices for which there exists a solution is 16 = R(3,3,3)-1. This result is due to Greenwood and Gleason.

Spoiler Alert: Click the doi below to access the article and uncover their solution for 16 vertices.

[Greenwood, R. E.; Gleason, A. M. (1955), "Combinatorial relations and chromatic graphs", Canadian Journal of Mathematics, 7: 1–7, doi:10.4153/CJM-1955-001-4, MR 0067467.]

Ramsey's Realm: four colors

Goal:

Color each edge red, blue, green, or orange in such a way that no three vertices have all the edges between them colored the same. That is, your coloring should not have a monochromatic triangle: a monochromatic triangle is a set of three vertices such that all the edges between them are colored the same.

With two colors, this means that there is no red triangle, no blue triangle, no green triangle, and no orange triangle in a correct solution.

Note: The vertices are the big circles. Crossings between lines are not considered vertices here.

Instructions:

Toggle the color of an edge from uncolored to red to blue to green to orange by clicking on the edge. You can revert an edge back to uncolored by clicking on it when it is orange. You can use the "Reset All" button to uncolor all the edges at once.

Start with five vertices, find a solution, and then increase the level (# of vertices). See how far you can go!

Check:

When you think you have a solution, click the "Check" button.

High Score: The highest number of vertices for which a solution has been found is 50. This result was discovered by Fan Chung. [F.R.K. Chung, On the Ramsey Numbers N (3, 3, ..., 3 ; 2), Discrete Mathematics, 5 (1973) 317-321.]

Warning: It is currently known that there are no solutions on 61 vertices, but it is not known if there are solutions on 51 through 60 vertices. [S. Fettes, R.L. Kramer and S.P. Radziszowski, An Upper Bound of 62 on the Classical Ramsey Number R(3, 3, 3, 3),Ars Combinatoria,72(2004) 41-63.]

If you happen to find a coloring that works on 51 or more vertices (and the applet actually runs), then take a picture and send me an email (if you'd like to collaborate on a paper) or publish a paper yourself.