×

zbMATH — the first resource for mathematics

Effect of scale on long-range random graphs and chromosomal inversions. (English) Zbl 1248.05187
Summary: 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.
MSC:
05C80 Random graphs (graph-theoretic aspects)
05C90 Applications of graph theory
60K35 Interacting random processes; statistical mechanics type models; percolation theory
92D15 Problems related to evolution
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Aizenman, M. and Newman, C. M. (1986). Discontinuity of the percolation density in one-dimensional \(1/|x-y|^{2}\) percolation models. Comm. Math. Phys. 107 611-647. · Zbl 0613.60097 · doi:10.1007/BF01205489
[2] Berestycki, N. (2011). Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles. Electron. J. Probab. 16 152-173. · Zbl 1228.60079 · doi:10.1214/EJP.v16-850 · emis:journals/EJP-ECP/_ejpecp/viewarticle3771.html
[3] Berestycki, N. and Durrett, R. (2006). A phase transition in the random transposition random walk. Probab. Theory Related Fields 136 203-233. · Zbl 1102.60005 · doi:10.1007/s00440-005-0479-7
[4] Berestycki, N. and Durrett, R. (2008). Limiting behavior for the distance of a random walk. Electron. J. Probab. 13 374-395. · Zbl 1187.60033 · doi:10.1214/EJP.v13-490 · emis:journals/EJP-ECP/_ejpecp/viewarticle82ea.html · eudml:231985
[5] Bollobás, B. (1985). Random Graphs . Academic Press, London. · Zbl 0567.05042
[6] Bollobás, B., Janson, S. and Riordan, O. (2009). Line-of-sight percolation. Combin. Probab. Comput. 18 83-106. · Zbl 1216.05140 · doi:10.1017/S0963548308009310
[7] Bramson, M., Durrett, R. and Swindle, G. (1989). Statistical mechanics of crabgrass. Ann. Probab. 17 444-481. · Zbl 0682.60090 · doi:10.1214/aop/1176991410
[8] Diaconis, P. and Graham, R. L. (1977). Spearman’s footrule as a measure of disarray. J. Roy. Statist. Soc. Ser. B 39 262-268. · Zbl 0375.62045
[9] Durrett, R. (2002). Probability Models for DNA Sequence Evolution . Springer, New York. · Zbl 0991.92021
[10] Durrett, R. (2003). Shuffling chromosomes. J. Theoret. Probab. 16 725-750. · Zbl 1047.92020 · doi:10.1023/A:1025676617383
[11] Durrett, R. (2010). Random Graph Dynamics . Cambridge Univ. Press, Cambridge. · Zbl 1223.05002
[12] Hannenhalli, S. and Pevzner, P. A. (1999). Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals. J. ACM 46 1-27. · Zbl 1064.92510 · doi:10.1145/300515.300516
[13] Kent, W. J., Baertsch, R., Hinrichs, A., Miller, W. and Haussler, D. (2003). Evolutions cauldron: Duplication, deletion, and rearrangement in the mouse and human genomes. Proc. Natl. Acad. Sci. USA 100 11484-11489.
[14] Liggett, T. M. (1985). Interacting Particle Systems. Grundlehren der Mathematischen Wissenschaften [ Fundamental Principles of Mathematical Sciences ] 276 . Springer, New York. · Zbl 0559.60078
[15] Penrose, M. D. (1993). On the spread-out limit for bond and continuum percolation. Ann. Appl. Probab. 3 253-276. · Zbl 0771.60097 · doi:10.1214/aoap/1177005518
[16] York, T. L., Durrett, R. and Nielsen, R. (2002). Bayesian estimation of inversions in the history of two chromosomes. J. Comput. Biol. 9 808-818.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.