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

The Moran process models the spread of mutations in populations on graphs. Weinvestigate the absorption time of the process, which is the time taken for amutation introduced at a randomly chosen vertex to either spread to the wholepopulation, or to become extinct. It is known that the expected absorption timefor an advantageous mutation is O(n^4) on an n-vertex undirected graph, whichallows the behaviour of the process on undirected graphs to be analysed usingthe Markov chain Monte Carlo method. We show that this does not extend todirected graphs by exhibiting an infinite family of directed graphs for whichthe expected absorption time is exponential in the number of vertices. However,for regular directed graphs, we show that the expected absorption time isOmega(n log n) and O(n^2). We exhibit families of graphs matching these boundsand give improved bounds for other families of graphs, based on isoperimetricnumber. Our results are obtained via stochastic dominations which wedemonstrate by establishing a coupling in a related continuous-time model. Thecoupling also implies several natural domination results regarding the fixationprobability of the original (discrete-time) process, resolving a conjecture ofShakarian, Roos and Johnson.

Absorption Time of the Moran Process