Effect of scale on long-range random graphs and chromosomal inversions
Authors:
- Nathanaël BerestyckiNBNathanaël Berestycki
- Richard PymarRPRichard Pymar
Open Access
- 1 August 2012
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 22 (4) , 1328-1361
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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Line-of-Sight PercolationCombinatorics, Probability and Computing, 2009
- A phase transition in the random transposition random walkProbability Theory and Related Fields, 2005
- Evolution's cauldron: Duplication, deletion, and rearrangement in the mouse and human genomesProceedings of the National Academy of Sciences, 2003
- Shuffling ChromosomesJournal of Theoretical Probability, 2003
- Bayesian Estimation of the Number of Inversions in the History of Two ChromosomesJournal of Computational Biology, 2002
- Probability Models for DNA Sequence Evolution2002
- Transforming cabbage into turnipJournal of the ACM, 1999
- Discontinuity of the percolation density in one dimensional 1/|x?y|2 percolation modelsCommunications in Mathematical Physics, 1986
- Interacting Particle Systems1985
- Spearman's Footrule as a Measure of DisarrayJournal of the Royal Statistical Society Series B: Statistical Methodology, 1977