Oriented first passage percolation in the mean field limit. (English) Zbl 1453.60159

Summary: The Poisson clumping heuristic has lead Aldous to conjecture the value of the oriented first passage percolation on the hypercube in the limit of large dimensions. Aldous’ conjecture has been rigorously confirmed by J. A. Fill and R. Pemantle [Ann. Appl. Probab. 3, No. 2, 593–629 (1993; Zbl 0783.60102)] by means of a variance reduction trick. We present here a streamlined and, we believe, more natural proof based on ideas emerged in the study of Derrida’s random energy models.


60K35 Interacting random processes; statistical mechanics type models; percolation theory
05C80 Random graphs (graph-theoretic aspects)
82B43 Percolation


Zbl 0783.60102
Full Text: DOI arXiv Euclid


[1] Aldous, D. (2013). Probability Approximations Via the Poisson Clumping Heuristic. Applied Mathematical Sciences 77. New York: Springer. · Zbl 0679.60013
[2] Arguin, L.-P. (2016). Extrema of log-correlated random variables: Principles and examples. In Advances in Disordered Systems, Random Processes and Some Applications (P. Contucci and C. Giardiná, eds.). Cambridge: Cambridge Univiersity Press.
[3] Bolthausen, E. and Kistler, N. (2006). On a nonhierarchical version of the generalized random energy model. The Annals of Applied Probability 16, 1-14. · Zbl 1100.60026
[4] Bovier, A. and Kurkova, I. (2009). A short course on mean field spin glasses. In Spin Glasses: Statics and Dynamics. Summer School Paris, 2007 (A. Boutet de Monvel and A. Bovier, eds.). Basel-Boston-Berlin: Birkhäuser. · Zbl 1209.82042
[5] Derrida, B. (1981). Random-energy model: An exactly solvable model of disordered systems. Physical Review B 24, 2613-2626. · Zbl 1323.60134
[6] Derrida, B. (1985). A generalization of the random energy model which includes correlations between energies. Journal de Physique Lettres 46, 401-407.
[7] Fill, J. A. and Pemantle, R. (1993). Percolation, first-passage percolation and covering times for Richardson’s model on the \(n\)-cube. The Annals of Applied Probability 3, 593-629. · Zbl 0783.60102
[8] Hegarty, P. and Martinsson, A. (2014). On the existence of accessible paths in various models of fitness landscapes. The Annals of Applied Probability 24, 1375-1395. · Zbl 1325.92065
[9] Kistler, N. (2015). Derrida’s random energy models. From spin glasses to the extremes of correlated radom fields. In Correlated Random Systems: Five Different Methods (V. Gayrard and N. Kistler, eds.), Lecture Notes in Mathematics 2143. Cham: Springer. · Zbl 1338.60231
[10] Martinsson, A. · Zbl 1353.60088
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.