On Richardson’s Model on the Hypercube

B. Bollobás^{1, 2}* and Y. Kohayakawa^{3}†

1Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, 16 Mill Lane, Cambridge CB2 1SB, England

2Department of Mathematics, Louisiana State University, Baton Rouge, LA 70803, USA

3Instituto de Matemática e Estatística, Universidade de São Paulo, Caixa Postal 20570, 01452–990 São Paulo, SP, Brazil

Abstract. The n-cube Q^{n} is the graph on the subsets of {1, …, n} where two such vertices are adjacent if and only if their symmetric difference is a singleton. Fill and Pemantle [5] started the study of several percolation processes on Q^{n} and obtained many asymptotic results for n → ∞. As an application of these results, they investigated the contact process with no recoveries in Q^{n}, also known as Richardson’s model for the spread of a disease. They obtained that, in this model, the cover time T_{n} of Q^{n} starting from a single infected vertex is bounded in probability: they proved that, with probability tending to 1 as n → ∞, one has (1/2) log(2 + √5) + log 2 + o(1) = 1.414 … + o(1) ≤ T_{n} ≤ 4 log(4 + 2√3) + 6 + o(1) = 14.040 …+o(1). In this note we substantially improve this upper bound by showing that one in fact has T_{n} ≤ 1 + log 2 + o(1) = 1.693 … + o(1) in probability.

* Part of this work was done while this author was visiting the University of São Paulo, supported by FAPESP under grant 92/3169–8.

† Research partially supported by FAPESP under grant 93/0603–1 and by CNPq under grant 300334/93–1.

§0. Introduction

The n-dimensional cube Q^{n} is the graph whose vertices are the subsets of [n] = {1, …, n} where two such vertices are adjacent if and only if their symmetric difference is a singleton. Here we are interested in a stochastic process on Q^{n}, known as Richardson’s model for the spread of a disease. In this model, one vertex of Q^{n} is at first infected and the disease evolves by transmission of the infection according to i.i.d. Poisson processes associated to the edges of Q^{n}. Every time our Poisson clock associated to an edge xy goes off, if one of x or y is infected at that time the other vertex becomes infected. The natural questions concerning this model regard the manner in which the disease spreads, and in particular the time it takes for all the vertices of Q^{n} to become infected. The latter question has been recently studied by Fill and Pemantle [5], who proved that this covering time is bounded in probability. Our aim in this note is to give an improved upper bound for this covering time.

One may study Richardson’s model on Q^{n} by studying first-passage percolation on this graph where the passage times on the edges are i.i.d. exponential random variables. In fact, we shall study Richardson’s model only looking at first-passage percolation. Let W = (W_{e})_{e∈E(Q^{n})} be a family of independent exponential random variables each with mean 1. If x and y are two vertices of Q^{n}, we write d(x, y) = d_{Q^{n}}(x, y) for the distance between x and y in Q^{n}, and we set

d_{W} (x, y) = min_{P}{ℓ(P, W): P an x—y path in Q^{n}},

where ℓ(P, W) = ∑_{e∈E(P)} W_{e} is the W -length of the path P. The result in [5] concerning Richardson’s model on Q^{n} is that, for a fixed x_{0} ∈ Q^{n}, with probability 1 − o(1) as n → ∞, we have (1/2) log(2 + √5) + log 2 + o(1) = 1.414 … + o(1) ≤ max_{y∈Q^{n}} d_{W} (x_{0}, y) ≤ 4 log(4 + 2√3) + 6 + o(1) = 14.040 … + o(1). A corollary of our main result, Theorem 5, is that this upper bound can be improved to 1 + log 2 + o(1) = 1.693 … + o(1).

Indeed, we shall show that with probability 1 − o(1) as n → ∞, (i) for all fixed x_{0} ∈ Q^{n} we have that max_{y∈Q^{n}} d_{W} (x_{0}, y) ≤ 1 + log 2 + o(1), and (ii) diam(Q^{n}, W) = max{d_{W} (x, y): x, y ∈ Q^{n}} ≤ 1 + 2 log 2 + o(1). The methods used in the proof Theorem 5 are reminiscent of certain techniques first used in [3, 4].

The organisation of this note is as follows. In §1 we present some definitions and preliminary results, and in §2 we prove the main technical lemma (Lemma 4) that is needed in the proof of Theorem 5. This theorem is proved in §3. We close this note with some remarks and further problems.

§1. Preliminaries Throughout this note, we let W = (W_{e})_{e∈E(Q^{n})} be a family of independent exponential random variables each of mean 1. For this section and the next, we assume that a constant 0 < ε < 1/6 has been fixed.

One extremely simple but important idea in our analysis of (Q^{n}, W) is that we may easily decompose W_{e} (e ∈ E(Q^{n})) into a collection of independent exponential random variables. This decomposition is then used to handle several events independently. Let X = (X_{e}), Y = (Y_{e}), and Z = (Z_{e}) be three families of independent exponential r.vs, where the X_{e} have mean (1 − 2ε)^{−1}, and the Y_{e} and Z_{e} have mean ε^{−1}. Writing a ∧ b for the minimum of a and b, if W′_{e} = X_{e}∧Y_{e}∧Z_{e} (e ∈ E(Q^{n})), clearly W′_{e} is an exponential r.v. with mean 1. Thus we may study (Q^{n}, W) by analysing (Q^{n}, X), (Q^{n}, Y), and (Q^{n}, Z).

All the asymptotics below refer to n → ∞. Moreover, we very often tacitly assume that n is large enough in the estimates that follow. As is usual in the theory os random graphs, we use the terms ‘almost surely’ and ‘almost every’ to mean ‘with probability tending to 1 as n → ∞’. For clarity, we shall denote ∅ ∈ Q^{n} by x_{0}. The neighbourhood of x ∈ Q^{n} is denoted by Γ(x) = Γ_{Q^{n}}(x). For graph-theoretical terminology not defined here, we refer the reader to [1].

Our first two lemmas concern (Q^{n}, X).

Lemma 1. For all x ∈ Q^{n}, let N_{x} = N_{x}(ε, X) ⊂ Γ_{Q^{n}}(x) be defined by N_{x} = {y ∈ Γ_{Q^{n}}(x): X_{xy} ≤ log 2 + 3ε} if x ≠ x_{0}, and N_{x_{0}} = {y ∈ Γ_{Q^{n}}(x_{0}): X_{x_{0}y} ≤ ε}. Then there is a constant c_{1} = c_{1}(ε) > 0 such that with probability 1−o(1) we have |N_{x}| ≥ c_{1}n for all x ∈ Q^{n}.

Proof. Fix an arbitrary vertex x ≠ x_{0} in Q^{n}. Then, for a fixed y ∈ Γ_{Q^{n}}(x),

(X_{xy} ≥ log 2 + 3ε) = exp{−(log 2 + 3ε)(1 − 2ε)} ≤ (1 − α)/2,

for some α = α(ε) > 0. From standard bounds for the tail of the binomial distribution, we see that for a suitable constant c′_{1} > 0 we almost surely have |N_{x}| ≥ c′_{1}n for all x ≠ x_{0}. Similarly, for a suitable constant c′′_{1} > 0, we have that |N_{x_{0}}| ≥ c′′_{1}n almost surely. Thus we may take c_{1} = c′_{1} ∧ c′′_{1}.

We now describe the results from [5] concerning first-passage percolation on Q^{n}. For all n ≥ 1, let x_{0} = x_{0}^{(n)} = ∅ ∈ Q^{n} and y_{0} = y_{0}^{(n)} = [n] ∈ Q^{n}.

Consider (Q^{n}, W), and let

T_{0} = inf{T ∈ : d_{W} (x_{0}, y_{0}) ≤ T with probability 1 − o(1)}.  (1)

Equivalently, T_{0} is the smallest T (0 ≤ T ≤ ∞) such that, for any given δ > 0, we have lim sup_{n} (d_{W} (x_{0}, y_{0}) ≥ T + δ) = 0 Thus T_{0} is the first-passage percolation time between two opposite vertices in Q^{n}. Fill and Pemantle [5] have shown that T_{0} ≤ 1, and an argument due to Durrett given in [5] gives that T_{0} ≥ log(1+√2) = .881 · · ·. Our next lemma brings in the parameter T_{0} into our problem. Before we can state this lemma we need some definitions. A subcube of Q^{n} is a subgraph induced in Q^{n} by a set of the form

Q_{S,A} = Q(S, A) = {x ∈ Q^{n}: x ∩ S = A},

where A ⊂ S ⊂ [n]. In the sequel we shall denote the subcube induced by Q_{S,A} by Q_{S,A} = Q(S, A) as well, since this will not cause any confusion. The dimension dim(Q_{S,A}) of Q_{S,A} is n − |S|. For an integer k ≥ 0 and a set X, we write X^{(k)} for the set of all k-element subsets of X.

Given x and y ∈ Q^{n} we define the subcube ⟨x, y⟩ spanned by x and y by

⟨x, y⟩ = Q((x △ y)^{c}, x \ (x △ y)) = Q((x △ y)^{c}, y \ (x △ y)),

where u^{c} = [n] \ u and as usual △ denotes symmetric difference. If x ⊂ y then ⟨x, y⟩ equals the ‘interval’ [x, y] in Q^{n} = P([n]) regarded as a partial order under inclusion, that is ⟨x, y⟩ = [x, y] = {z ∈ Q^{n}: x ⊂ z ⊂ y}. If v ∈ ⟨x, y⟩, let us call the pair (⟨x, y⟩; v) a rooted cube with root v. For the rest of this note, we let k_{0} = ⌈log n⌉, and set

T = {(x, y, z) ∈ Q^{n} × Q^{n} × Q^{n}: d(x, y) ≥ 2k_{0} + 1, d(x, z) = 2k_{0}, z ∈ ⟨x, y⟩}.

For a triple (x, y, z) ∈ T let F_{x,y,z} be the family

{(⟨v, w⟩; v): v ∈ ⟨x, z⟩ , d(x, v) = k_{0}, w = v △ y △ z}

of rooted subcubes of ⟨x, y⟩. In visualising F_{x,y,z}, it might be helpful to note that the map φ_{y,z}: u ↦ u △ (y △ z) gives a natural isomorphism between the subcubes ⟨x, z⟩ and ⟨φ_{y,z}(x), φ_{y,z}(z)⟩ = ⟨φ_{y,z}(x), y⟩. Moreover, note that the rooted subcubes (⟨v, w⟩; v) in F_{x,y,z} are translates of the rooted cube (⟨x, φ_{y,z}(x)⟩; x) = (⟨x, x △ y △ z⟩; x). In fact, we may clearly regard Q^{n} as ⟨x, z⟩×⟨x, φ_{y,z}(x)⟩. Let us say that (⟨v, w⟩; v) ∈ F_{x,y,z} is inexpensive if d_{X}(v, w) is at most (T_{0} + ε)/(1 − 2ε), and expensive otherwise. In the sequel we write m_{0} = \binom{2k_{0}}{k_{0}}. Rather crudely we have n^{1.38} ≤ m_{0} ≤ n^{1.39}.

Lemma 2. There is a constant c_{2} = c_{2}(ε) > 0 such that the following holds almost surely. For all (x, y, z) ∈ T the number of rooted subcubes in F_{x,y,z} that are inexpensive is at least c_{2}m_{0} = c_{2}\binom{2k_{0}}{k_{0}}.

Proof. Let (x, y, z) ∈ T be given. Fix v, w ∈ Q^{ℓ} (ℓ ≥ 1) with d(v, w) = ℓ, and let U = (U_{e})_{e∈E(Q^{ℓ})} be a family of independent exponential r.vs of mean 1. By the definition of T_{0}, we have that for any given fixed δ > 0 we have lim_{ℓ} (d_{U}(v, w) ≥ T_{0} + δ) = 0. It follows that there is an integer ℓ_{0} = ℓ_{0}(ε) such that (d_{U}(v, w) ≤ (T_{0} + ε)/(1 − 2ε)) ≥ 1/2 if ℓ ≥ ℓ_{0}. Moreover, there clearly exists a constant c′_{2} = c′_{2}(ε) > 0 such that the probability that a rooted cube (⟨v, w⟩; v) is inexpensive is at least c′_{2} if 1 ≤ dim ⟨v, w⟩ ≤ ℓ_{0}. Let us now set c_{2} = (1/2)(c′_{2} ∧ 1/2).

Let (⟨v_{i}, w_{i}⟩; v_{i}) (1 ≤ i ≤ m_{0}) be the m_{0} rooted cubes in F_{x,y,z}. Note that the ⟨v_{i}, w_{i}⟩ are pairwise vertex-disjoint and hence the events that (⟨v_{i}, w_{i}⟩; v_{i}) (1 ≤ i ≤ m_{0}) should be inexpensive are independent. Thus the number J of inexpensive rooted cubes in F_{x,y,z} has binomial distribution Bi(m_{0}, p) with parameters m_{0} = \binom{2k_{0}}{k_{0}} and p ≥ 2c_{2}. It now follows that (J < c_{2}m_{0}) ≤ exp{−pm_{0}/8} ≤ exp{−n^{1.3}} = o(|T |^{−1}), as required.

Our next result is a simple lemma concerning (Q^{n}, Y). Recall that k_{0} = ⌈log n⌉. If x, y ∈ Q^{n} are such that d(x, y) = 2ℓ, let L_{x,y} denote the middle layer {z ∈ ⟨x, y⟩: d(x, z) = d(z, y) = ℓ} of ⟨x, y⟩.

Lemma 3. Let V_{0} = V_{0}(Y) be the set of vertices z of Q^{n} that are incident to at least (ε^{2}/3)n edges e with Y_{e} ≤ ε. Then almost surely for all x, y ∈ Q^{n} with d(x, y) = 2k_{0} at most n vertices in the middle layer L_{x,y} of ⟨x, y⟩ fail to be in V_{0}.

Proof. Let x = x_{0} = ∅ and fix y ∈ [n]^{(2k_{0})}. For any edge e ∈ E(Q^{n}) we have (Y_{e} ≤ ε) = 1 − exp(−ε^{2}) ≥ ε^{2}/2, and hence for fixed z ∈ L_{x,y} the probability that z does not belong to V_{0} is at most p_{0} = exp{−ε^{2}n/36}. Thus the probability that we have |L_{x,y} \ V_{0}| ≥ n is at most

\binom{m}{n} exp\{−ε^{2}n^{2}/36\} ≤ \binom{n^{1.4}}{n} exp\{−ε^{2}n^{2}/36\} ≤ exp\{−Ω(n^{2})\}.

Thus the probability that there exist x, y ∈ Q^{n} with d(x, y) = 2k_{0} such that |L_{x,y} \ V_{0}| ≥ n is at most 4^{n} exp{−Ω(n^{2})} = o(1).

Let V_{0} = V_{0}(Y) be defined as in Lemma 3. For all z ∈ V_{0} we let N′_{z} = N′_{z}(ε, Y) = {z′ ∈ Γ_{Q^{n}}(z): Y_{zz′} ≤ ε}. Thus |N′_{z}| ≥ (ε^{2}/3)n for any z ∈ V_{0}.

§2. The main lemma

In this section we study (Q^{n}, Z), and prove a lemma (Lemma 4) that will be fundamental for the proof of our main result, Theorem 5. We stress that the argument in the proof below is quite crude, and that with a little more patience one may prove a stronger result. However, such a stregthening of this lemma would not, as far as we can see, improve Theorem 5. Before turning to our lemma, recall that 0 < ε < 1/6 has been fixed.

Lemma 4. Set K = ⌊(ε^{6}n/650)^{1/7}⌋, and let m^{2} = ωn^{11/7} ≤ n^{2}, where ω = ω(n) → ∞ as n → ∞. Let x = x_{0} = ∅ and fix y ⊂ [n] with 1 ≤ k = |y| ≤ K. Let S ⊂ Γ_{Q^{n}}(x) and T ⊂ Γ_{Q^{n}}(y) with |S|, |T | ≥ m be given. Then in (Q^{n}, Z) there is an S—T path P of Z-length ℓ(P, Z) = ∑_{e∈E(P)} Z_{e} at most ε with probability at least 1 − e^{−ωn/ log ω}.

Proof. For all e ∈ E(Q^{n}) and 2 ≤ j ≤ K + 1, let Z_{e}^{(j)} be an exponential r.v. with mean K/ε, and assume that all these variables are independent. Set Z^{(j)} = (Z_{e}^{(j)})_{e∈E(Q^{n})} for 2 ≤ j ≤ K + 1. Clearly Z_{e} and ⋀_{j} Z_{e}^{(j)} have the same distribution for all e ∈ E(Q^{n}). Let t_{0} = ε/(2K + k − 2). Then for all 2 ≤ j ≤ K + 1 we have

p = \{Z_{e}^{(j)} ≤ t_{0}\} = 1 − exp \{\frac{−ε^{2}}{K(2K + k − 2)}\} ≥ \frac{ε^{2}}{2K(2K + k − 2)} ≥ \frac{ε^{2}}{6K^{2}} .

For all 2 ≤ j ≤ K + 1, let H_{j} = H_{j}(Z^{(j)}) ⊂ Q^{n} be the spanning subgraph of Q^{n} whose edge-set is {e ∈ E(Q^{n}): Z_{e}^{(j)} ≤ t_{0}}. Note that the H_{j} (2 ≤ j ≤ K + 1) are K independent random elements of G(Q^{n}, p), the space of random spanning subgraphs of Q^{n} whose edges are independently present with probability p. Let us set G_{j} = H_{2} ∪ ⋯ ∪ H_{j} (2 ≤ j ≤ K + 1). We now claim the following.

Claim. In G_{K+1} there is an S—T path of length at most 2K + k − 2 with probability at least 1 − exp{−ωn/ log ω}.

Note that a path as in the claim above has Z-length at most t_{0}(2K +k− 2) = ε, and hence to prove our lemma it suffices to prove this claim. To verify this claim we start by setting S_{1} = {v ∈ S: v ⊄ y} and T_{1} = {v ∈ T: y ⊂ v}. Clearly |S_{1}|, |T_{1}| ≥ m − k ≥ m/2. We shall think of Q^{n} as Q^{n−k} × Q^{k} in the following way. For each v ⊂ y^{c} = [n] \ y, let

Q_{v} = ⟨v, v △ y⟩ = ⟨v, v ∪ y⟩ = {z ⊂ [n]: z ∩ y^{c} = v}.  (2)

Note that Q_{v} is a cube of dimension k = |y|, and that Q = ⟨x_{0}, y^{c}⟩ = {v ∈ Q^{n}: v ⊂ y^{c}} is a cube of dimension n − k. Also, we may naturally regard Q^{n} as ⟨x_{0}, y^{c}⟩ × ⟨x_{0}, y⟩.

Write n_{1} = |y^{c}| = n − k and note that clearly n_{1} = (1 + o(1))n. Let us set

S′_{2} = {z ∈ (y^{c})^{(2)}: z ∈ Γ_{Q^{n}}(S_{1}) and z ∪ y ∈ Γ_{Q^{n}}(T_{1})}.

A moment’s thought shows that |S′_{2}| ≥ \binom{m/2}{2}. Thus, setting

S_{2} = {z ∈ (y^{c})^{(2)}: z ∈ Γ_{H_{2}}(S_{1}) and z ∪ y ∈ Γ_{H_{2}}(T_{1})},

quite crudely we have (|S_{2}|) ≥ \binom{m/2}{2}p^{2} ≥ m^{2}p^{2}/9. Hence, with probability at least 1 − exp{−m^{2}p^{2}/1800} = 1 − exp{−Ω(ε^{4/7}ωn)}, we have |S_{2}| ≥ m^{2}p^{2}/10.

For the rest of the argument, we condition on |S_{2}| ≥ m^{2}p^{2}/10 ≥ (1/5)(mp/n)^{2}\binom{n_{1}}{2}. In the sequel, if U ⊂ ⟨x_{0}, y^{c}⟩, we write U ∨y for \{u∪y: u ∈ U}, namely the translate of U by the map u ↦ u ∪ y, which is contained in the cube ⟨y, [n]⟩. Let us now fix 3 ≤ j ≤ K and condition on the existence of S_{2} ⊂ (y^{c})^{(2)}, …, S_{j−1} ⊂ (y^{c})^{(j−1)} for which the following conditions hold for all 2 ≤ i < j.

(i) |S_{i}| ≥ (4/5)2^{−i} (mp^{i−1}/n)^{2} \binom{n_{1}}{i},

(ii) for all z ∈ S_{i} there is an S_{1}—z path of length i − 1 in G_{i} =

H_{2} ∪ ⋯ ∪ H_{i},

(iii) for all z ∈ S_{i} there is a T_{1}—(z ∪ y) path of length i − 1 in G_{i} =

H_{2} ∪ ⋯ ∪ H_{i}.

Now let S′_{j} = Γ_{Q^{n}}(S_{j−1}) ∩ (y^{c})^{(j)} = {z′ ∈ (y^{c})^{(j)}: z ⊂ z′ for some z ∈ S_{j−1}}. Then, by the local LYM inequality (see for instance [2], §3), we have that

|S′_{j}| ≥ |S_{j−1}|\binom{n_{1}}{j − 1}^{−1}\binom{n_{1}}{j} ≥ \frac{4}{5}2^{−j+1} (\frac{mp^{j−2}}{n} )^{2} \binom{n_{1}}{j}.

We now set S_{j} = {z ∈ S′_{j}: z ∈ Γ_{H_{j}}(S_{j−1}) and z ∪ y ∈ Γ_{H_{j}}(S_{j−1} ∨ y)}. Then very crudely we have that

(|S_{j}|) ≥ |S′_{j}|p^{2} ≥ \frac{4}{5}2^{−j+1} (\frac{mp^{j−1}}{n} )^{2} \binom{n_{1}}{j},

and so with probability at least

1 − exp \{−\frac{1}{5}2^{−j} (\frac{mp^{j−1}}{n} )^{2} \binom{n_{1}}{j}\} ,

condition (i) above holds for i = j, that is |S_{j}| ≥ (4/5)2^{−j} (mp^{j−1}/n)^{2} \binom{n_{1}}{j}. Note that by the definition of S_{j} conditions (ii) and (iii) above hold for i = j. Let

S′′_{K} = {z ∈ (y^{c})^{(K)}: d_{G_{K}} (S, z), d_{G_{K}} (T, z ∪ y) ≤ K − 1},

where d_{G_{K}} denotes the distance in the graph G_{K}. Then, using the argument above for 3 ≤ j ≤ K in turn, we see that with probability at least

P_{0} = 1 − ∑_{3≤j≤K} exp \{−\frac{1}{5}2^{−j} (\frac{mp^{j−1}}{n} )^{2} \binom{n_{1}}{j}\}

we have

|S′′_{K}| ≥ \frac{4}{5}2^{−K} (\frac{mp^{K−1}}{n} )^{2} \binom{n_{1}}{K}.  (3)

To estimate P_{0}, note that if 3 ≤ j ≤ K then

\begin{aligned}A = 2^{−j} (\frac{mp^{j−1}}{n} )^{2} & \binom{n_{1}}{j} ≥ \frac{m^{2}}{n^{2}p^{2}} (\frac{p^{2}n_{1}}{2j} )^{j} \\ & ≥ \frac{m^{2}}{n^{2}p^{2}} \{(\frac{p^{2}n_{1}}{6} )^{3} ∧ (\frac{p^{2}n_{1}}{2K} )^{K}\} , \end{aligned}

since the function f(x) = (B/x)^{x} (x > 0) is log-concave. However,

(\frac{p^{2}n_{1}}{2K} )^{K} ≥ (\frac{1}{73} \frac{ε^{4}n}{K^{5}})^{K} = (Ω(n^{2/7}))^{K} ≥ (\frac{p^{2}n_{1}}{6} )^{3} ,

and hence A ≥ (1/216 + o(1))m^{2}np^{4} = Ω(ωn^{10/7}). Thus, very crudely,

P_{0} ≥ 1 − K exp{−Ω(ωn^{10/7})} ≥ 1 − exp{−ωn}.  (4)

Let us now condition on (3). To finish the proof of our claim, we shall show that with very high probability there is an S′′_{K}—(S′′_{K} ∨ y) path of length k in H_{K+1}. We shall do this using an extremely crude argument. Consider the family F = {Q_{v}: v ∈ S′′_{K}} of k-cubes as defined in (2). Recall that Q_{v} is a translate of ⟨x_{0}, y⟩ by v, and note that in particular the Q_{v} (v ∈ S′′_{K}) are pairwise disjoint. Consider for each v ∈ S′′_{K} a fixed v—(v∪y) path P_{v} ⊂ Q_{v} of length k, and note that the probability P_{1} that there should not be an S′′_{K}— (S′′_{K} ∨ y) path of length k in H_{K+1} is at most (1 − p^{k})^{|S′′_{K}|} ≤ (1 − p^{K})^{|S′′_{K}|} ≤ exp{−p^{K}|S′′_{K}|}. However, as (3) holds,

\begin{aligned}p^{K}|S′′_{K}| & ≥ \frac{4}{5}2^{−K}p^{K} (\frac{mp^{K−1}}{n} )^{2} \binom{n_{1}}{K} \\ & ≥ \frac{4}{5} \frac{m^{2}}{p^{2}n^{2}} (\frac{p^{3}n}{3K})^{K} ≥ \frac{4}{5} (\frac{m}{pn})^{2} (\frac{650}{648})^{K} , \end{aligned}

which is much larger than ωn. Thus P_{1} ≤ e^{−ωn}. This bound and inequality (4) finish the proof of the claim, and hence Lemma 4 is proved.

§3. The main result Recall that W = (W_{e}) is a collection of independent exponential r.vs each with mean 1. Also, recall that T_{0} is the first-passage percolation time between two diametrically opposite vertices in Q^{n} when the passage times are given by W (cf. (1) in Section 2).

Theorem 5. The following hold with probability 1 − o(1) as n → ∞.

(i) Writing x_{0} = ∅ ∈ Q^{n}, we have max_{y∈Q^{n}} d_{W} (x_{0}, y) ≤ T_{0} + log 2 + o(1), (ii) diam(Q^{n}, W) ≤ T_{0} + 2 log 2 + o(1).

Proof. (i) Let 0 < ε < 1/6 be fixed. We regard W_{e} as X_{e} ∧ Y_{e} ∧ Z_{e} (e ∈ E(Q^{n})), where X_{e}, Y_{e}, and Z_{e} are as in Section 2, i.e. the X_{e} are exponential with mean (1 − 2ε)^{−1}, the Y_{e} and Z_{e} are exponential with mean ε^{−1}, and all these variables are independent. Let us now consider the following events. (We keep the notation introduced in Section 2.)

(a) For all x ∈ Q^{n} we have |N_{x}| = |N_{x}(ε, X)| ≥ c_{1}n,

(b) for all (x, y, z) ∈ T , the number of inexpensive rooted subcubes in F_{x,y,z} is not smaller than c_{2}m_{0} = c_{2}\binom{2k_{0}}{k_{0}},

(c) for all x, y ∈ Q^{n} with d(x, y) = 2k_{0}, we have |L_{x,y} \ V_{0}| = |L_{x,y} \

V_{0}(Y)| ≤ n. Note that by Lemmas 1, 2, and 3 conditions (a), (b), and (c) above hold almost surely. For the rest of the argument we condition on (Q^{n}, X) and (Q^{n}, Y) satisfying (a), (b), and (c).

Let S_{x_{0}} = N_{x_{0}} = N_{x_{0}}(ε, X) = {y ∈ Γ_{Q^{n}}(x_{0}): X_{x_{0}y} ≤ ε}. For every x ∈ Q^{n} − x_{0}, set S_{x} = N′_{x} = N′_{x}(ε, Y) if x ∈ V_{0} = V_{0}(Y), and S_{x} = N_{x} = N_{x}(ε, X) otherwise. For a fixed pair x, y ∈ Q^{n} with d(x, y) ≤ K = ⌊(ε^{6}n/650)^{1/7}⌋, if we let S = S_{x} and T = S_{y}, Lemma 4 tells us that d_{Z}(S, T) ≤ ε with probability at least 1 − exp{−n^{5/4}}. Thus (d) below holds with probability 1 − o(1).

(d) For all x, y ∈ Q^{n} with d(x, y) ≤ K we have

d_{W} (x, y) ≤ \{ \begin{matrix}3ε & if x, y ∈ V_{0} ∪ \{x_{0}\} \\ log 2 + 5ε & if x ∈ V_{0} ∪ \{x_{0}\} or y ∈ V_{0} ∪ \{x_{0}\} \\ 2 log 2 + 7ε & otherwise. \end{matrix}

We now condition on (Q^{n}, W) satisfying (d), and claim that consequently we have max{d_{W} (x_{0}, y): y ∈ Q^{n}} ≤ T_{0} + log 2 + 3εT_{0} + 12ε. First note that it follows from (d) that max{d_{W} (x_{0}, y): y ∈ Q^{n}, d(x_{0}, y) ≤ K} is as small as claimed, and hence let y ∈ Q^{n} be such that d(x_{0}, y) > K ≥ 2k_{0}. Pick z ∈ ⟨x_{0}, y⟩ with d(x_{0}, z) = 2k_{0}, and note that then (x_{0}, y, z) ∈ T . Since we are conditioning on (b) and (c) above, we may find v ∈ L_{x_{0},y} such that v ∈ V_{0}, w = v △ y △ z ∈ V_{0}, and (⟨v, w⟩; v) is an inexpensive rooted cube. But then

\begin{aligned}d_{W} (x_{0}, y) & ≤ d_{W} (x_{0}, v) + d_{W} (v, w) + d_{W} (w, y) \\ & ≤ 3ε + \frac{T_{0} + ε}{1 − 2ε} + log 2 + 5ε ≤ T_{0} + log 2 + 3εT_{0} + 12ε. \end{aligned}

Theorem 5(i) follows by letting ε → 0.

(ii) Minor modifications to the above argument gives a proof of Theorem 5(ii).

The result above, coupled with the upper bound T_{0} ≤ 1 for the firstpassage percolation time T_{0} established by Fill and Pemantle [5], gives the following corollary.

Corollary 6. The following hold with probability 1 − o(1) as n → ∞.

(i) Writing x_{0} = ∅ ∈ Q^{n}, we have max_{y∈Q^{n}} d_{W} (x_{0}, y) ≤ 1 + log 2 + o(1), (ii) diam(Q^{n}, W) ≤ 1 + 2 log 2 + o(1).

§4. Concluding remarks and open problems The best bounds so far for the first-passage percolation time T_{0} in Q^{n}, defined in §1, are the ones given in [5], namely .881 … = log(1 + √2) ≤ T_{0} ≤ 1. We believe that percolation happens at a sharply defined time.

Conjecture 7. For all δ > 0 we have lim_{n→∞} {d_{W} (x_{0}, y_{0}) ≤ T_{0} − δ} = 0.

We also believe that the analogous phenomenon happens in Richardson’s model. As a starting point, it would be interesting to settle the following problem.

Problem 8. Do the following two assertions hold with probability 1 − o(1) as n → ∞?

(i) Writing x_{0} = ∅ ∈ Q^{n}, one has max_{y∈Q^{n}} d_{W} (x_{0}, y) = T_{0} + log 2 + o(1). (ii) One has diam(Q^{n}, W) = T_{0} + 2 log 2 + o(1).

References

[1] Bollobás, B., Graph Theory—An Introductory Course, Springer–Verlag, New York 1979, viii + 180pp.

[2] Bollobás, B., Combinatorics, Cambridge University Press, Cambridge 1986, xii + 177pp.

[3] Bollobás, B., Kohayakawa, Y., Łuczak, T., On the diameter and radius of random subgraphs of the cube, Random Structures and Algorithms, to appear.

[4] Bollobás, B., Kohayakawa, Y., Łuczak, T., Connectivity properties of random subgraphs of the cube, Random Structures and Algorithms, to appear.

[5] Fill, J.A., Pemantle, R., Percolation, first-passage percolation, and covering times for Richardson’s model on the n-cube, The Annals of Applied Probability 3 (1993), 593–629.