A horde of ravenous zombies descends on a sole survivor loose in a ravaged city, filled with deserted streets and no help in sight. The survivor happens to be a Mathematician, and so has no weapons to use other than his mind.  He has, therefore, no choice but to make a run for it.  Which way should he go to minimize the probability of being eaten? Does he have any chance of survival, or is this really the end?

These are the questions we posed in a recent paper A probabilistic version of the game of Zombies and Survivors on graphs. Our approach is the first to consider the problem as a kind of game played on networks. Before I explain further, I describe the game of Cops and Robbers, which is a well-studied vertex pursuit game on played on graphs that served as our inspiration.

In the game of Cops and Robbers, there are two players, the set of cops and the sole robber. The players take alternate turns moving from vertex-to-vertex in a graph, with the cops going first. The cops win if they capture a robber, which is equivalent to landing on the vertex the robber occupies; the robber wins if she can indefinitely evade capture. For example, on a cycle graph with four or more vertices, two cops are needed to capture the robber, and it is easy to see that one is not enough. We say in this case that the cop number of a cycle is two. In general, the cop number of a graph is the minimum number of cops needed to win on a graph G, and is written c(G). See my previous post for more on the game, or visit my website and view my publications on the topic.

In the game of Zombies and Survivor, the cops are now zombies, and the robber is now the survivor. The survivor plays as a robber does as we described above in Cops and Robbers. The zombies however, have very limited intelligence. They don’t really play with a strategy at all: being dead and hungry, they just move towards the survivor. If there are multiple ways to do this, they choose a random direction to move towards him. The zombies win if they eat the survivor (which still amounts to landing on his vertex). At the beginning, they appear at randomly chosen nodes, just like they appear from nowhere say on The Walking Dead. The zombie number measures how favorable it is for the zombies to have dinner. More precisely, we define the parameter z(G) to be the minimum number of zombies such that the probability that they eventually get to eat the survivor is strictly greater than 1/2.

The zombie number is a weird graph parameter, and we don’t seem to have a good handle on how to compute it even for fairly elementary graphs. For example, on a classical grid graph (think of a chessboard), where the players move up, down, left, or right, the zombie number equals two just, as is the case for the cop number.  But if you consider a toroidal grid (think of Pong: a chessboard where you identify the top and bottom rows, and the left and right extreme columns … so no center and no boundaries), it is far less clear what the zombie number is. In fact, in the paper we can only prove a lower bound on the zombie number of toroidal grids. Lower bounds are usually much harder to prove in vertex pursuit games than upper bounds! More precisely, for the mathematical readers, in a toroidal grid with n^2 nodes, we can prove that the survivor has a winning strategy to evade n^(0.5) / w(n) log (n) zombies, where w(n) is any function of n tending to infinity. Even a sub-quadratic upper bound on the zombie number is not obvious!

Our paper studies the zombie number of some familiar graphs: cycles, hypercubes, incidence graphs of projective planes, and grids.  We define the cost of being undead of a graph G as that ratio of the z(G) and c(G). The cost of being undead can be very high: for example, consider a cycle with many leaves attached to one node. In this case, the cost of being undead is a constant times n, which is about as bad as can be. This means such a graph is a good place to be if you are a survivor.

Our random version of the game was inspired by a deterministic version first considered by a colleague Margaret-Ellen Messinger. In their version of the game, the zombies get to choose their starting places and choose their shortest paths to the robber. So the zombies in this game are smarter than ours.  Margaret-Ellen first told me about the zombie game at the SIAM Discrete Mathematics Conference in Minneapolis… a city better known for Mary Tyler Moore rather than zombies!

Anthony Bonato