Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

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

**Duration**: 30 minutes

**Location**: CAB G51

**Speaker**: Pascal Pfister

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.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login