Speaker
Description
In evolutionary graph theory, population of size $n$ is represented as a (connected) graph with $n$ vertices whose edges represent who can replace whom. Initially, all $n$ vertices have fitness 1 except for one vertex (mutant) that has fitness $r>1$. This initial mutant may have arised either spontaneously (aka uniform initialization), or during reproduction (aka temperature initialization). The population then evolves according to so-called Moran process until, eventually, all vertices become the same type — the single mutant either goes extinct or reaches fixation. Graphs that ensure fixation probability of 1 in the limit of infinite population size are called strong amplifiers. Previously, only a few examples of strong amplifiers were known for uniform initialization, and no strong amplifiers were known for temperature initialization. We show that self-loops and weighted edges are two key features for strong amplification. On one hand, we show that without either self-loops or weighted edges, strong amplification is (i) impossible under temperature initialization, and (ii) impossible for bounded-degree graphs under uniform initialization. On the other hand, we show that with both self-loops and weighted edges, strong amplification is ubiquitous: Almost any graph with self-loops can be assigned weights that make it a strong amplifier for both temperature and uniform initialization. This is a joint work with Andreas Pavlogiannis, Krishnendu Chatterjee, and Martin A. Nowak.
