**
**

**Goldberg, Leslie Ann; Lapinskas, John; Lengler, Johannes; Meier, Florian; Panagiotou, Konstantinos and Pfister, Pascal (2019): Asymptotically optimal amplifiers for the Moran process. In: Theoretical Computer Science, Vol. 758: pp. 73-93**

**Full text not available from 'Open Access LMU'.**

## Abstract

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 Galanis et al. We show that this family is optimal, up to logarithmic factors, since every strongly-connected n-vertex digraph has extinction probability Omega(n(-1/2)). Next, 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. Finally, 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. (C) 2018 Elsevier B.V. All rights reserved.

Item Type: | Journal article |
---|---|

Faculties: | Mathematics, Computer Science and Statistics > Mathematics |

Subjects: | 500 Science > 510 Mathematics |

ISSN: | 0304-3975 |

Language: | English |

Item ID: | 82393 |

Date Deposited: | 15. Dec 2021, 15:01 |

Last Modified: | 15. Dec 2021, 15:01 |