The other day I was sitting in The Coop in Cambridge, reading a book on combinatorial games, and so naturally I started wondering about games played in groups, or on their Cayley graphs at least. After a short T ride home, I discussed the idea with my roommate and I settled on the following game:

Let $G$ be a group with a specified presentation $\langle a_1, \dots, a_m \mid R \rangle$ and let $\Gamma$ be the corresponding Cayley graph. Fix some $k : \mathbb{N}, k \geq 1$. Then the game $E_{\Gamma, k}$ is played as follows:

There are two players, which for vividness I’ll call Rocket and Gravity. The players start on some vertex $v_0$ corresponding to the identity $e$ in $G$. The two players alternate turns, starting with Gravity. On its first move, Gravity moves to any vertex $v_1$ adjacent to $v_0$. Since we are in a Cayley graph, this amounts to choosing a generator.

Now suppose it is the $(i + 1)^{\text{th}}$ turn. If it is Gravity’s turn, then as before, they select an adjacent vertex $v_{i + 2}$, but now we must have $v_{i + 1} \neq v_i$. In other words, the players may not backtrack. In yet other words, the word in $G$ corresponding to the path the players are building must be freely reduced. If it is Rocket’s turn, they are allowed to choose $v_{i + 2}$ to be any vertex within $k$ edges of $v_{i + 1}$, again subject to the restriction that they may not move from $v_{i + 1}$ to $v_i$.

For each $i$, let $w_i$ be the word labelling a shortest path from $v_0$ to $v_i$. Then Gravity wins if $$ \limsup_{i \to \infty} |w_i| = \infty $$ and Rocket wins otherwise. I.e., if $$ \limsup_{i \to \infty} |w_i| < \infty $$ So, Gravity is trying to pull our hero away to infinity, while Rocket must struggle nobly till the end of time to stay within some bounded neighborhood of the origin.

The question then is, for a given $\Gamma$, what is the least $k$ such that Rocket has a winning strategy for the game $E_{\Gamma, k}$. Since $\Gamma$ is the Cayley graph of a finitely presented group, we have a weak upper bound (assuming every generator appears in some relator). Namely $\max_{r \in R} |r| - 1$, where $R$ again is our collection of relators. If Rocket has this many moves, then their winning strategy is simply to complete some relator containing the generator just chosen by Gravity.

It seems clear that in some cases this must be a lower bound as well. For example, consider the genus 2 surface group $\langle a, b, c, d \mid [a, b][c, d]\rangle$, shown above. If Rocket is given only 6 moves per turn, it seems clear that Gravity can succeed in pushing us out to boundary.

In fact this is the case, and we can say something more general: Take any group $G = \langle a_1, \dots, a_m | R \rangle$ with corresponding Cayley graph $\Gamma$, and let’s assume that $R$ is symmetrized (closed under inverses and cyclic permutations) for convenience. If $G$ is $C'(1/6)$ and for any $a_i$ there is an $a_j$ such that $a_i a_j$ does not appear as a subword of any relator in $R$, then Rocket requires at least $\max_{r \in R} |r| - 1$ moves per turn to have a winning strategy. Using the same proof, we can say something more general than this, but it is a bit complicated to state, so I won’t mention it for now.

So let’s prove this. We’ll give Rocket $\ell := \max_{r \in R} |r| - 2$ moves per turn, and construct a winning strategy for Gravity.

To prove this we’ll use, as with all facts about small cancellation groups, Greendlinger’s lemma.

The logic proof is to exhibit a strategy for Gravity such that

1. If it’s Gravity’s turn and a geodesic segment corresponding to the current position is $w$, then Gravity can choose a generator $a$ such that $wa$ is still geodesic. In other words, Gravity can increase the distance from the origin by 1 on each turn.

2. If it’s Rocket’s turn and a geodesic segment corresponding position is $w$, then for any $s$ of length at most $\ell$ (not backtracking on $w$) the length of the shortest word equal to $w\ell$ (which I’ll denote $|w\ell|$ is at least $|w|$. That is, Rocket can never decrease the distance to the origin.

It then follows that the $w_i$ are getting monotonically longer, so the strategy succeeds.

I’ll follow up this post eventually with proofs and pictures.