Chapter 20 Ramsey Colouring Games
Project by: Barun Gambhir and Siyu Long.
\(\textbf{Summary}\text{:}\) The project focuses on exploring the applications of Ramsey's theory in game design and recreational mathematics. By leveraging fundamental concepts from Ramsey's theory, the goal is to create an engaging and intellectually stimulating game. The game is designed to embody key Ramsey-theoretic properties, providing players with an interactive platform to experience the beauty of Combinatorial mathematics firsthand.
To play the game go to 1–player vs AI game link and 2-player game.
\(\textbf{Description of the project}\text{:}\) Our project mainly consists of two parts: (1) a writing part and (2) a coding part, and responsively our presentation is also going to be a combination of two parts. For the writing part, an expository text on the topic of Ramsey?s theory is presented. For the coding part, We initially developed a 2–player game during the first month which we improvised and created an even more advanced 1–player game in which a player plays against the computer (or AI). It has the following features:
- Single–Player Mode: In this mode, the player competes against the computer AI to form a monochromatic complete subgraph before the opponent.
Graph Visualization: The game provides an interactive graph visualization where players can click on edges to colour them.
- Smart AI: The computer AI in single-player mode makes intelligent moves to form complete subgraphs strategically.
Dynamic UI: The user interface dynamically updates to display the game status, current player's turn, and game messages.
Responsive Design: The game is designed to be responsive and works well on different screen sizes and devices.
Instructions: The game provides clear instructions on how to play and win.
\(\textbf{Code}\text{:}\) Throughout this project, we managed to develop two games, both 1–player and 2–player. However, much of the focus was made on the 1-player game against the AI since we invested much more time creating the algorithm for AI to play against (and even try to beat) human players.
The 2–player game, created initially is somewhat a prototype and a major chunk of the code for this game was reused in the 1-player game as well. Please check out the links for the game as well as the GitHub repository below:
To access the source code go to Code: 1–player vs AI game link and Code: 2–player game.
\(\textbf{A brief summary of surveying Ramsey colouring games}\text{:}\) In the project, we begin from generally surveying the Ramsey theory contents and have produced a brief summarizing article for the graph–theoretical Ramsey theory.
Ramsey theory is closely related to pigeonhole principle, an intuitive enumerating theorem that can lead to many non-intuitive facts in the world of Ramsey theory.
Theorem 20.0.1. Generalized Pigeonhole Principle.
If \(n\) and \(k\) are positive integers and \(n \lt k\text{,}\) \(S\) is a set of n elements and \(S_1, S_2, \ldots ,S_k\) are \(k\) subsets whose disjoint union is \(S\text{,}\) then there must be one subset whose cardinality is larger than \(\frac{n}{k}\text{,}\) and one subset whose cardinality is at most\(\frac{n}{k}\text{.}\)
Example 20.0.2.
If \(S\) is a set of \(10\) elements, any sets \(S_1, S_2, S_3\) whose disjoint union is \(S\) satisfy that (1) there is one set of \(S_1, S_2, S_3\) whose cardinality is larger than \(\frac{10}{3}\) i.e. an integer larger than 3, and (2) there is one set of \(S_1, S_2, S_3\) whose cardinality is less than \(\frac{10}{3}\) i.e. an integer that is at most 3.
This theorem has many analogues that we can think of, one of them being pigeons and holes when the totality of elements of \(S\) represents the totality of pigeons and \(S_1, S_2, \ldots, S_k\) represents the holes, and we can apply pigeonhole principle to predict that whatever way the pigeons settle in the holes, there is a hole that contains pigeons “many enough” to be more than \(\frac{n}{k}\) and a hole that contains pigeons “few enough” to be fewer than\(\frac{n}{k}\text{.}\)
Furthermore, we generally name the relation between some pigeons and the holes they are going to dwell as colouring.
To put it more blatantly, the pigeonhole principle describes that for any colouring of a finite set, no matter how we try to evenly colourize the set to avoid many monochromatic objects, we end up creating a monochromatic set that is “large enough” and another “small enough”. Thus when we are intrigued by the sizes of the monochromatic sets in a colouring, rather than how the objects are contained in the monochromatic sets, we may apply the pigeonhole principle to recognize necessary patterns of graph theoretical Ramsey theory, and our further investigation of Ramsey theory colouring games.