Abstract

Let G be a graph (directed or undirected), and let v be some vertex of G. Two players play the following game. A token starts at v. The players take turns to move, and each move of the game consists of moving the token along an edge of the graph, to a vertex that has not yet been visited. A player who is unable to move loses the game. If the graph is finite, then one player or the other must have a winning strategy. In the case of an infinite graph, it may be that, with optimal play, the game continues for ever.

I’ll focus in particular on games played on the lattice Z^d, directed or undirected, with each vertex deleted independently with some probability p. In the directed case, the question of whether draws occur is closely related to ergodicity for certain probabilistic cellular automata, and to phase transitions for the hard-core model. In the undirected case, I’ll describe connections to bootstrap percolation and to maximum-cardinality matchings and independent sets.

This includes joint work with Alexander Holroyd, Irène Marcovici, Riddhipratim Basu, and Johan Wästlund.