English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the classic Moran process modeling the spread of geneticmutations, as extended to structured populations by Lieberman et al.\ (Nature,2005). In this process, individuals are the vertices of a connected graph $G$.Initially, there is a single mutant vertex, chosen uniformly at random. In eachstep, a random vertex is selected for reproduction with a probabilityproportional to its fitness: mutants have fitness $r>1$, while non-mutants havefitness 1. The vertex chosen to reproduce places a copy of itself to auniformly random neighbor in $G$, replacing the individual that was there. Theprocess ends when the mutation either reaches fixation (i.e., all vertices aremutants), or gets extinct. The principal quantity of interest is theprobability with which each of the two outcomes occurs.  A problem that has received significant attention recently concerns theexistence of families of graphs, called strong amplifiers of selection, forwhich the fixation probability tends to 1 as the order $n$ of the graphincreases, and the existence of strong suppressors of selection, for which thisprobability tends to 0. For the case of directed graphs, it is known that bothstrong amplifiers and suppressors exist. For the case of undirected graphs,however, the problem has remained open, and the general belief has been thatneither strong amplifiers nor suppressors exist. In this paper we disprove thisbelief, by providing the first examples of such graphs. The strong amplifier wepresent has fixation probability $1-\tilde O(n^{-1/3})$, and the strongsuppressor has fixation probability $\tilde O(n^{-1/4})$. Both graphconstructions are surprisingly simple. We also prove a general upper bound of$1-\tilde \Omega(n^{-1/3})$ on the fixation probability of any undirectedgraph. Hence, our strong amplifier is existentially optimal.

Amplifiers and Suppressors of Selection for the Moran Process on Undirected Graphs