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

DOI10.1214/11-AAP793zbMATH Open1248.05187arXiv1102.4479OpenAlexW2009212249MaRDI QIDQ453237FDOQ453237

Authors: Nathanaël Berestycki, Richard Pymar 

Publication date: 19 September 2012

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

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.

Full work available at URL: https://arxiv.org/abs/1102.4479

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Random graph dynamics
• Title not available (Why is that?)
• A phase transition in the random transposition random walk
• Title not available (Why is that?)
• Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles
• Discontinuity of the percolation density in one dimensional \(1/| x- y| ^ 2\) percolation models
• Transforming cabbage into turnip
• Limiting behavior for the distance of a random walk
• On the spread-out limit for bond and continuum percolation
• Shuffling chromosomes
• Statistical mechanics of crabgrass
• Line-of-sight percolation

Cited In (2)

• Cutoff for a one-sided transposition shuffle
• A phase transition in the random transposition random walk

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)