### Skapa referens, olika format (klipp och klistra)

**Harvard**

Martinsson, A. (2016) *Unoriented first-passage percolation on the n-cube*.

** BibTeX **

@article{

Martinsson2016,

author={Martinsson, Anders},

title={Unoriented first-passage percolation on the n-cube},

journal={Annals of Applied Probability},

issn={1050-5164},

volume={26},

issue={5},

pages={2597-2625},

abstract={The n-dimensional binary hypercube is the graph whose vertices are the binary n-tuples {0,1)(n) and where two vertices are connected by an edge if they differ at exactly one coordinate. We prove that if the edges are assigned independent mean 1 exponential costs, the minimum length T-n of a path from (0,0,..., 0) to (1,1,, 1) converges in probability to ln(1 + root 2) approximate to 0.881. It has previously been shown by Fill and Pemantle [Ann. Appl. Probab. 3 (1993) 593-629] that this so-called first-passage time asymptotically almost surely satisfies ln(1 + root 2) - 0(1) <= T-n <= 1+ 0(1), and has been conjectured to converge in probability by Bollobas and Kohayakawa [In Combinatorics, Geometry and Probability (Cambridge, 1993) (1997) 129-137 Cambridge]. A key idea of our proof is to consider a lower bound on Richardson's model, closely related to the branching process used in the article by Fill and Pemantle to obtain the bound T-n >= ln(1 + root 2) - 0(1). We derive an explicit lower bound on the probability that a vertex is infected at a given time. This result is formulated for a general graph and may be applicable in a more general setting.},

year={2016},

keywords={First-passage percolation, Richardson's model, hypercube, branching translation process, lower bound, Mathematics },

}

** RefWorks **

RT Journal Article

SR Electronic

ID 245989

A1 Martinsson, Anders

T1 Unoriented first-passage percolation on the n-cube

YR 2016

JF Annals of Applied Probability

SN 1050-5164

VO 26

IS 5

SP 2597

OP 2625

AB The n-dimensional binary hypercube is the graph whose vertices are the binary n-tuples {0,1)(n) and where two vertices are connected by an edge if they differ at exactly one coordinate. We prove that if the edges are assigned independent mean 1 exponential costs, the minimum length T-n of a path from (0,0,..., 0) to (1,1,, 1) converges in probability to ln(1 + root 2) approximate to 0.881. It has previously been shown by Fill and Pemantle [Ann. Appl. Probab. 3 (1993) 593-629] that this so-called first-passage time asymptotically almost surely satisfies ln(1 + root 2) - 0(1) <= T-n <= 1+ 0(1), and has been conjectured to converge in probability by Bollobas and Kohayakawa [In Combinatorics, Geometry and Probability (Cambridge, 1993) (1997) 129-137 Cambridge]. A key idea of our proof is to consider a lower bound on Richardson's model, closely related to the branching process used in the article by Fill and Pemantle to obtain the bound T-n >= ln(1 + root 2) - 0(1). We derive an explicit lower bound on the probability that a vertex is infected at a given time. This result is formulated for a general graph and may be applicable in a more general setting.

LA eng

DO 10.1214/15-aap1155

LK http://dx.doi.org/10.1214/15-aap1155

LK http://publications.lib.chalmers.se/records/fulltext/245989/local_245989.pdf

OL 30