Effect of scale on long-range random graphs and chromosomal inversions

Authors:
  • NBNathanaël Berestycki
    Nathanaël Berestycki
  • RPRichard Pymar
    Richard Pymar

Abstract
We consider bond percolation on $n$ vertices on a circle where edges are permitted between vertices whose spacing is at most some number $L=L(n)$. We show that the resulting random graph gets a giant component when $L\gg(\log n)^{2}$ (when the mean degree exceeds 1) but not when $L\ll\log n$. The proof uses comparisons to branching random walks. We also consider a related process of random transpositions of $n$ particles on a circle, where transpositions only occur again if the spacing is at most $L$. Then the process exhibits the mean-field behavior described by Berestycki and Durrett if and only if $L(n)$ tends to infinity, no matter how slowly. Thus there are regimes where the random graph has no giant component but the random walk nevertheless has a phase transition. We discuss possible relevance of these results for a dataset coming from D. repleta and D. melanogaster and for the typical length of chromosomal inversions.

This publication has 14 references indexed in Scilit: