2017/03/28 by Paweł Prałat, Pralat, Pawel
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1703.09616
openalex publication_date 2017/03/28 · openalex created_date 2017/04/07 · openalex updated_date 2026/07/28
In Zombies and Survivors, a set of zombies attempts to eat a lone survivor loose on a given graph. The zombies randomly choose their initial location, and during the course of the game, move directly toward the survivor. At each round, they move to the neighbouring vertex that minimizes the distance to the survivor; if there is more than one such vertex, then they choose one uniformly at random. The survivor attempts to escape from the zombies by moving to a neighbouring vertex or staying on his current vertex. The zombies win if eventually one of them eats the survivor by landing on their vertex; otherwise, the survivor wins. The zombie number of a graph is the minimum number of zombies needed to play such that the probability that they win is at least 1/2. This variant of the game was recently investigated for several graph families, such as cycles, hypercubes, incidence graphs of projective planes, and grids Pn \square Pn. However, unfortunately, still very little is known for toroidal grids Cn \square Cn: the zombie number of Cn \square Cn is at least √ n/(ωlog n), where ω= ω(n) is any function going to infinity as n → ∞, and no upper bound is known except a trivial bound of O(n2 log n). In this note, we provide an approach that gives an embarrassing bound of O(n2) but it is possible that (with more careful, deterministic, argument) it might actually give a bound of O(n3/2). On the other hand, by analyzing a specific strategy for the survivor, it seems that one could slightly improve the lower bound to √ n/ω. In any case, we are far away from understanding this intriguing question. Your help is needed!