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

DOI10.1214/11-AAP793MaRDI QIDQ453237zbMATH OpenOpenAlexFDO

Authors Nathanaël Berestycki, Richard Pymar

Publication date 19 September 2012

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.4479, https://projecteuclid.org/euclid.aoap/1344614197

zbMATH Keywords

phase transitionrandom graphsbranching random walkbond percolationgiant componentgenome rearrangementcoagulation-fragmentationrandom transposition

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

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 $Lgg(logn{)}^2$ (when the mean degree exceeds 1) but not when $Llllogn$. 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.

Recommendations

• The evolution of the random reversal graph
• The diameter of a long-range percolation graph
• The phase transition in the configuration model
• Percolation on sparse random graphs with given degree sequence
• The Small Giant Component in Scale-Free Random Graphs

Cites work

• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• scientific article; zbMATH DE number 1761225 (Why is no real title available?)
• scientific article; zbMATH DE number 3892344 (Why is no real title available?)
• Discontinuity of the percolation density in one dimensional \(1/| x- y| ^ 2\) percolation models
• Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles
• Limiting behavior for the distance of a random walk
• Line-of-sight percolation
• On the spread-out limit for bond and continuum percolation
• Random graph dynamics
• Shuffling chromosomes
• Statistical mechanics of crabgrass
• Transforming cabbage into turnip

Cited in

(1)

• Cutoff for a one-sided transposition shuffle

This page was built for publication: Effect of scale on long-range random graphs and chromosomal inversions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q453237)