“Asymptotically Optimal Amplifiers for the Moran Process”, 2016-11-13 (; backlinks):
We study the Moran process as adapted by Lieberman, Hauert and Nowak. This is a model of an evolving population on a graph or digraph where certain individuals, called “mutants” have fitness r and other individuals, called non-mutants have fitness 1. We focus on the situation where the mutation is advantageous, in the sense that r > 1.
A family of digraphs is said to be strongly amplifying if the extinction probability tends to 0 when the Moran process is run on digraphs in this family. The most-amplifying known family of digraphs is the family of megastars of et al 2015. We show that this family is optimal, up to logarithmic factors, since every strongly-connected n-vertex digraph has extinction probability Ω(n−1⁄2).
Next, we show that there is an infinite family of undirected graphs, called dense incubators, whose extinction probability is 𝒪(n−1⁄3). We show that this is optimal, up to constant factors.
Finally, we introduce sparse incubators, for varying edge density, and show that the extinction probability of these graphs is 𝒪(n⁄m), where m is the number of edges. Again, we show that this is optimal, up to constant factors.