Strong Bounds for Evolution in Undirected Graphs

This work studies the generalized Moran process, as introduced by Lieberman, Hauert, and Nowak [Nature, 433:312-316, 2005], where the individuals of a population reside on the vertices of an undirected connected graph. The initial population has a single mutant of a fitness value r (typically r> 1), residing at some vertex v of the graph, while every other vertex is initially occupied by an individual of fitness 1. At every step of this process, an individual (i.e. vertex) is randomly chosen for reproduction with probability proportional to its fitness, and then it places a copy of itself on a random neighbor, thus replacing the individual that was residing there. The main quantity of interest is the fixation probability, i.e. the probability that eventually the whole graph is occupied by descendants of the mutant. In this work we concentrate on the fixation probability when the mutant is initially on a specific vertex v, thus refining the older notion of Lieberman et al. which studied the fixation probability when the initial mutant is placed at a random vertex. We then aim at finding graphs that have many “strong starts ” (or many “weak starts”) for the mutant. Thus we introduce a parameterized notion of selective amplifiers (resp. selective suppressors) of evolution, i.e. graphs with at least some h(n) vertices (starting points of the mutant), which fixate the graph with large (resp. wit