Here is an interesting idea I had while at a summer school in Daejeon. This is possibly well-known, since a lot of people seem to be interested in Ramsey numbers.
1. The Ramsey game#
Let \( k \) and \( l \) be positive integers, and consider the following game.
\( \mathsf{RG}[n,r,s] \): There is given a graph with \( n \) vertices and no edges. Paul and Carole play a game with this graph. In each round, Paul first picks an independent set \( S \) with \( r \) vertices, and then Carole draws some segments between the vertices of \( S \). (Carole has to draw at least \( 1 \) edge, and obviously, at most \( r(r-1)/2 \) edges.) Paul wins if, at some point, Carole makes a perfect graph \( K _ s \). Carole wins, if she manages to avoid making a \( K _ s \) until Paul cannot pick an independent set with \( r \) vertices.
Who has a winning strategy? Of course, if \( n \ge R(r,s) \), then Paul wins. Here, \( R(r,s) \) denotes the Ramsey number.
Proposition 1. If \( n \ge R(r,s) \) then Paul wins \( \mathsf{RG}[n,r,s] \).
Proof. The strategy for Paul is, pick an arbitrary independent set \( S \) of size \( r \). Since \( n \ge R(r,s) \), either Paul can continue the game or Carole must have already made a \( K _ s \). ▨
The surprising part is that this the exact bound.
Theorem 2. If \( n < R(r,s) \) then Carole wins \( \mathsf{RG}[n,r,s] \).
In the next section I will sketch the proof. But try to prove this puzzle before you read it!
2. The mod \( 2 \) counting#
This game \( \mathsf{RG}[n,r,s] \) is a perfect information game. Thus it suffices to show that if there exists a winning strategy for Paul, then \( n \ge R(r,s) \). We will prove the following proposition.
Proposition 3. If there exists a winning strategy for Paul for \( \mathsf{RG}[n,r,s] \), then every graph on \( n \) vertices either has an independent set with \( r \) vertices or a \( K _ s \) as a subgraph.
In some sense, this is like giving an upper bound for the Ramsey number \( R(r,s) \).
Here is the basic idea. Label the vertices with the numbers from \( 1 \) to \( n \), and define the variables \[ \displaystyle e _ {ij} = \begin{cases} 0 & \displaystyle \text{if } i \text{ and } j \text{ are not connected by an edge}, \\ 1 & \displaystyle \text{if } i \text{ and } j \text{ are connected by an edge}. \end{cases} \] If there is no \( K _ s \) or an independent set of size \( r \), then we will have the identity \[ \displaystyle 0 = e _ {i _ 1 i _ 2} e _ {i _ 1 i _ 3} \cdots e _ {i _ {s-1} i _ s}, \quad 0 = (1 - e _ {j _ 1 j _ 2}) (1 - e _ {j _ 1 j _ 3}) \cdots (1 - e _ {j _ {r-1} j _ r}) \] for every \( 1 \le i _ 1, \ldots, i _ s, j _ 1, \ldots, j _ r \le n \). Thus, if we can find polynomials \( p _ {I}, q _ J \in \mathbb{F} _ 2[e _ {12}, \ldots, e _ {(n-1)n}] \) such that \[ \displaystyle 1 = \sum _ {I}^{} p _ I e _ {i _ 1 i _ 2} \cdots e _ {i _ {s-1} i _ s} + \sum _ {J}^{} q _ J (1 - e _ {j _ 1 j _ 2}) \cdots (1 - e _ {j _ {r-1} j _ r}) \] as polynomials (over \( \mathbb{F} _ 2 \)), then we can immediately conclude that every graph on \( n \) vertices either has a \( K _ s \) or an independent set of size \( r \).
How is this related to the game \( \mathsf{RG}[n,r,s] \)? A strategy of a perfect information game can be considered as a direct graph, each node corresponding to a state of the game. In this case, there is one root node corresponding to the empty graph on \( n \) vertices. Each node, which is a graph, either has a \( K _ s \) or has \( 2^{r(r-1)/2} - 1 \) children nodes. These children nodes will correspond to the states Carole can make when Paul chooses a certain independent set according to the strategy.
Now take this directed graph \( H \), which has graphs on \( \{1, \ldots, n\} \) as nodes. For each graph (or node) \( G \in V(H) \), consider the monomial \[ \displaystyle \prod _ {(i,j) \in E(G)}^{} e _ {ij}. \] Consider a node \( G \) which does not have a \( K _ s \) and has \( 2^{r(r-1)/2} - 1 \) children. Suppose Paul’s strategy is to pick the independence set \( S _ G = \{j _ 1, \ldots, j _ r\} \subseteq \{1, \ldots, n\} \). Then \[ \displaystyle (1 + e _ {j _ 1 j _ 2}) (1 + e _ {j _ 1 j _ 3}) \cdots (1 + e _ {j _ {r-1} j _ r}) \prod _ {(i,j) \in E(G)}^{} e _ {ij} \] is the sum of the monomials associated to \( G \) and its children. If we add this over all \( G \in V(H) \), all the nodes will be counted exactly twice except the root node and those with no child. Thus \[ \displaystyle \sum _ {G \in V(H)} \prod _ {(i,j) \in E(G)}^{} e _ {ij} \prod _ {i,j \in S _ G}^{} (1 + e _ {ij}) = 1 + (\text{generated by } e _ {i _ 1 i _ 2} e _ {i _ 1 i _ 3} \cdots e _ {i _ {s-1} i _ s}) \] over characteristic \( 2 \). It immediately follows from this identity that every graph on \( n \) vertices either has a \( K _ s \) or a size \( r \) independent set. This finishes the proof of Proposition 3.