Percolation, first-passage percolation and covering times for Richardson's model on the n-cube

DOI10.1214/AOAP/1177005440MaRDI QIDQ687712zbMATH OpenOpenAlexFDO

Authors James Allen Fill, Robin Pemantle

Publication date 28 October 1993

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

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

zbMATH Keywords

contact processedge-passage percolationfirst-passage percolation

Mathematics Subject Classification ID

Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: Percolation with edge-passage probability p and first-passage percolation are studied for the n-cube B_n ={0,1}^n with nearest neighbor edges. For oriented and unoriented percolation, p=e/n and p=1/n are the respective critical probabilities. For oriented first-passage percolation with i.i.d. edge-passage times having a density of 1 near the origin, the percolation time (time to reach the opposite corner of the cube) converges in probability to 1 as n->infty. This resolves a conjecture of David Aldous. When the edge-passage distribution is standard exponential, the (smaller) percolation time for unoriented edges is at least 0.88. These results are applied to Richardson's model on the (unoriented) n-cube. Richardson's model, otherwise known as the contact process with no recoveries, models the spread of infection as a Poisson process on each edge connecting an infected node to an uninfected one. It is shown that the time to cover the entire n-cube is bounded between 1.41 and 14.05 in probability as n->infty.

Review text

The authors study edge-passage percolation for the cube \(\{0,1\}^ n\) with nearest neighbour edges. They show that the critical probability is \(p=e/n\) in the oriented and \(p=1/n\) in the unoriented case. Furthermore it is shown for oriented first-passage percolation with i.i.d. passage times having a density being equal to 1 near the origin that the time to reach the opposite corner of the cube tends to 1 in probability as \(n\to\infty\). The authors also show how their results apply to the contact process with no recoveries (Richardson's model).

Recommendations

• scientific article; zbMATH DE number 1047716
• Supercritical behaviors in first-passage percolation
• Unoriented first-passage percolation on the n-cube
• Oriented first passage percolation in the mean field limit
• Percolation and first-passage percolation on oriented graphs

Cited in

(21)

• Diffusion limited aggregation on the Boolean lattice
• First-passage percolation on Cartesian power graphs
• The width of random subsets of Boolean lattices
• Oriented first passage percolation in the mean field limit. II: The extremal process
• Reliable broadcasting in hypercubes with random link and node failures
• Derrida's random energy models. From spin glasses to the extremes of correlated random fields
• Accessibility percolation with backsteps
• Unoriented first-passage percolation on the n-cube
• First passage percolation on locally treelike networks. I. Dense random graphs
• Interacting particle systems as stochastic social dynamics
• scientific article; zbMATH DE number 1047716 (Why is no real title available?)
• The length of random subsets of Boolean lattices
• Kardar-Parisi-Zhang universality in first-passage percolation: the role of geodesic degeneracy
• Speeding up non-Markovian first-passage percolation with a few extra edges
• Positive association of the oriented percolation cluster in randomly oriented graphs
• On the Push&Pull Protocol for Rumor Spreading
• Undirected polymers in random environment: path properties in the mean field limit
• Random walks and electrical resistances in products of graphs
• First passage percolation on Erdös-Rényi graphs with general weights
• Hamiltonicity of random subgraphs of the hypercube
• Oriented first passage percolation in the mean field limit

This page was built for publication: Percolation, first-passage percolation and covering times for Richardson's model on the \(n\)-cube

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