Unoriented first-passage percolation on the n-cube

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,\dots ,0)$ to $(1,1,\dots ,1)$ converges in probability to $\ln (1+\sqrt{2})\approx 0.881$. It has previously been shown by Fill and Pemantle (1993) that this so-called first-passage time asymptotically almost surely satisfies $\ln (1+\sqrt{2})-o(1)\le T_n\le 1+o(1)$, and has been conjectured to converge in probability by Bollob'as and Kohayakawa (1997). 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\ge \ln (1+\sqrt{2})-o(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.