## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, March 02, 2017, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Pascal Pfister

## Asymptotically Optimal Amplifiers for the Moran Process

We study the Moran process, a model of an evolving population with two kinds of individuals — “mutants” and “non-mutants”. The individuals reside at the vertices of a graph G – each vertex contains exactly one individual, and it is either a mutant or a non-mutant. In the initial state, one vertex (chosen uniformly at random) contains a mutant. All of the other vertices contain non-mutants. Additionally, mutants have fitness r > 1 whereas non-mutants have fitness 1. At each time step, a vertex v is selected at random, with probability proportional to its fitness. Next, a neighbour w of v is selected uniformly at random and the state of vertex v (mutant or non-mutant) is copied to vertex w. If G is finite and connected then with probability 1, the process will either reach the state where there are only mutants (known as fixation) or it will reach the state where there are only non-mutants (extinction).
A family of graphs is said to be strongly amplifying if the extinction probability (the probability that there are no mutants left at some point) tends to 0 when the Moran process is run on graphs in this family. We show that there is an infinite family of undirected graphs, called dense incubators, whose extinction probability is O(n−1/3). We show that this is optimal, up to constant factors. Moreover, we introduce sparse incubators, for varying edge density, and show that the extinction probability of these graphs is O(n/m), where m is the number of edges. Again, we show that this is optimal, up to constant factors.

Information for students and suggested topics for student talks