Amplifiers for the Moran process
The graph Moran process, as studied by Lieberman, Hauert and Nowak, is a Markov chain modelling the spread of a single genetic mutation in a population. The structure of the population is represented by a graph in which each vertex contains one individual, either with or without the mutation. Initially, one uniformly random vertex is a mutant with some fitness r > 0 and the other vertices are non-mutants with fitness 1. At each time step a vertex is chosen to reproduce, with probability proportional to its fitness, and overwrites a random neighbour's state with its own. We are concerned with determining the probability that mutants take over the population (the "fixation probability") and, more fundamentally, determining the range of values this probability can take. In particular, we give the first rigorous proof that there exists a sequence of graphs G_1, G_2, ... with fixation probability 1 - o(1) as n tends to infinity (for any fixed r > 1), and show that the convergence is faster than all other proposed candidates.