The Length of Random Subsets of Boolean Lattices^{∗}

Y. Kohayakawa,^{†}

Instituto de Matemática e Estatística, Universidade de São Paulo Rua do Matão 1010, 05508–900 São Paulo, Brazil

                     E-mail address: yoshi@ime.usp.br

B. Kreuter, and D. Osthus^{‡}

Institut für Informatik, Humboldt-Universität zu Berlin Unter den Linden 6, 10099 Berlin, Germany

             E-mail address: kreuter@informatik.hu-berlin.de
                     osthus@informatik.hu-berlin.de

Abstract

We form the random poset P(n, p) by including each subset of [n] = {1, …, n} with probability p and ordering the subsets by inclusion. We investigate the length of the longest chain contained in P(n, p). For p ≥ e/n we obtain the limit distribution of this random variable. For smaller p we give thresholds for the existence of chains which imply that almost surely the length of P(n, p) is (1+o(1)) n(log n − log log 1/p)/ log 1/p.

1 Introduction and basic definitions

We investigate random subsets of the power set P(n) of [n] = {1, …, n}. Such a random subset, denoted P(n, p), is obtained by selecting each element of P(n) with probability p independently of all other elements. If we order the elements of P(n) by inclusion, we obtain a Boolean lattice. If we order the elements of P(n, p) by inclusion, we obtain a partially ordered set (or simply poset) which is a subposet of the above Boolean lattice.

We focus on the cardinality of the maximum chain contained in P(n, p). Here a chain is a subset of P(n) whose elements are pairwise comparable and the length of a chain is its cardinality minus one. The length of P(n, p), for which we write length P(n, p), is defined to be the length of the maximum chain contained in P(n, p). Rényi was the first to investigate the behaviour of this random variable: in [12] he determined the threshold for the existence of a chain of length one in P(n, p). Recently, Kreuter [10] obtained (amongst other results) thresholds for the appearance of chains of any fixed length. Thus in this paper we confine our attention to the evolution of the length of P(n, p) when we increase p beyond the ranges investigated in the above references. Another important parameter of P(n, p) is the cardinality of its maximum antichain, also called the width. This is studied in [9] and [11]. We remark that the results proven in [11] make use of the central lemma of this paper, Lemma 7. Indeed, the investigation of antichains in P(n, p) for certain values of p seems to depend essentially on this technical lemma on chains.

∗Research supported by PROBRAL project number 026/95, a CAPES–DAAD exchange programme.

†Partially supported by FAPESP (Proc. 96/04505–2), by CNPq (Proc. 300334/93–1), and by MCT/ FINEP (PRONEX project 107/97).

‡Graduate school “Algorithmische Diskrete Mathematik”, supported by Deutsche Forschungsgemeinschaft grant GRK/3-98

Brightwell [6] gives an overview of some other models of random posets. For example, several authors (see e.g. [3]) have studied the length of the random poset generated by picking n random points in the k-dimensional unit cube. However this model, although similar to ours, requires quite different proof techniques. Our methods are more related to those used in the past to investigate the diameter and other parameters of random subgraphs of the n-dimensional hypercube (see e.g. Bollobás, Kohayakawa and Łuczak [4, 5]). Also, in [7] Fill and Pemantle prove the analogue of Theorem 4 in the context of edge percolation on the hypercube.

Throughout, we refer to the subset P_{t}(n) ⊂ P(n) whose elements have cardinality t as the tth level of P(n). The levels of P(n, p) are defined in the same way. The (Hamming) distance d_{H}(x, y) of x, y ∈ P(n) is given by |(x\y)∪(y\x)|. We write a.s. to mean “with probability tending to one as n tends to infinity”.

This paper is organised as follows. In the next section, we state our main results, Theorems 1 and 4. Our main technical tool is given in Section 3, where we state and prove Lemma 7. Theorems 1 and 4 are proved in Sections 4 and 5.

2 Results

Kreuter [10] proved that the length of P(n, p) is constant when p decreases exponentially. The following theorem tells us about the length of P(n, p) when p is superexponential:

Theorem 1 Let k = k(n) ≤ n − 1 be an integer valued function tending to infinity. Then

lim_{n→∞} ℙ( length P(n, p)≥k−1 ) = \{ \begin{matrix}0 & if p (k+1)^{n/k} → 0 \\ 1 & if p (k+1)^{n/k}(k/n)^{2} → ∞. \end{matrix}  (1)

At the end of Section 3 we indicate how one may remove the factor (k/n)^{2} at the expense of more extensive calculations. An immediate corollary of the above theorem is that when p decreases polynomially in n, the degree of the polynomial turns out to be the average distance beween two elements of a typical maximum chain:

Corollary 2 Let r ≥ 1 be a fixed constant. Then

lim_{n→∞} ℙ ( length P(n, p)≥ \frac{n}{r} −2 ) = \{ \begin{matrix}0 & if pn^{r} → 0 \\ 1 & if pn^{r} → ∞. \end{matrix}  (2)

We remark that the above threshold could be sharpened slightly by the use of branching processes and indicate how this may be done at the end of the final section. Another immediate corollary of Theorem 1 is the following asymptotic formula for the length of P(n, p):

Corollary 3 If c^{n} = o(p) for any 0 < c < 1 and p = O(n^{−1}), then a.s.

length P(n, p) = (1 + o(1)) \frac{n}{log 1/p} (log n − log log 1/p) .  (3)

Our second theorem (which improves Corollary 2 for the special case when r = 1) gives a detailed picture of the final stage of the evolution of the length of P(n, p):

Theorem 4 Let c ≥ e be a given constant. Define p(n) = c/n. Let η = η(c) satisfy η = e^{c(η−1)} and 0 < η < 1. Then

lim_{n→∞}ℙ( length P(n, p)=n−2 ) = (1 − η)^{2},
lim_{n→∞}ℙ( length P(n, p)=n−3 ) = 2η(1 − η),
lim_{n→∞}ℙ( length P(n, p)=n−4 ) = η^{2}.

We remark that η is the extinction probability of a branching process whose family size has Poisson distribution with parameter c. Also note that since the top and bottom levels of P(n) contain only a single element, a.s. we have that length P(n, p) < n − 1 as long as p → 0. Finally, the following proposition shows that the previous theorem is essentially best possible in the sense that if c < e, then P(n, p) becomes significantly shorter. Indeed, if p = p(n) = c/n, Theorem 1 and Proposition 5 imply that, very crudely, we have

n − length P(n, p) \{ \begin{matrix}O(1) & if c ≥ e \\ → ∞ & if c < e \end{matrix}  (4)

almost surely. We believe that the fact that the techniques in this paper are enough to identify the sharp change of behaviour given in (4) is quite pleasant.

Proposition 5 Let c < e be a given constant. Define p(n) = c/n. Then a.s.

length P(n, p) ≤ (1 − \frac{log(e/c)}{3 log n}) n.

Proof. Let

a = ⌈\frac{log(e/c)}{3 log n}n⌉ .

For Q ⊂ P(n) denote by Y (Q) the number of (n − a)-element chains in Q. A chain on n − a elements corresponds to an ordered partition of [n] into n − a nonempty sets. To bound the number of those, first choose n − a elements, one for each partition class. There are (n)_{n−a} = n!/a! ways of doing this. Then order the remaining a elements and distribute them among the n − a classes, with (n − a)^{a} possibilities for this second step. Hence by Stirling’s formula,

Y (P(n)) ≤ n^{a}n! = O(n^{a+1/2}(n/e)^{n}).

Thus the expected value of Y = Y (P(n, p)) is

𝔼(Y) = O(n^{a+1/2}(n/e)^{n}p^{n−a}) = O(n^{2a+1/2}(c/e)^{n−a}) = o(1)

by the definition of a. □

3 Regular chains

The aim of this section is to prove Lemma 7 below. This lemma implies that the number of “regular” chains is not too far from its expected value provided that p is beyond some threshold. Once we have this result, Theorem 1 will follow immediately, while we still have to do some additional work for Theorem 4. These “regular” chains are defined as follows: suppose x, y ∈ P(n) are given with x ⊂ y. Given any r and k, we say (x_{1}, …, x_{k}) is an (x, y, r, k)-chain if x ⊂ x_{1} ⊂ ⋯ ⊂ x_{k} ⊂ y with the additional condition that |x_{i}| = |x|+⌈ir⌉ for all i. Since r and k are always related in what follows, (x, y, r, k)-chains are simply referred to as (x, y, r)-chain.

Throughout this section we assume that x ∈ P_{t}(n) and y ∈ P_{n−t}(n) for some fixed integer t. Also k, the number of elements in a chain, is a given integer function of n with k ≤ n − 2t − 1. As a measure of the average distance between two chain elements we define

r = \{ \begin{matrix}1 & if k = n − 2t − 1 \\ (n−2t−1)/(k+1) & if k < n − 2t − 1. \end{matrix}  (5)

The extra minus one in the fraction is a technical artifice to ensure that P_{|x_{i}|}(n, p) is large enough even when r is not an integer and i is close to k. We separate the two cases since we want to achieve the best possible result when r = 1. Now, for given m ∈ ℕ, let

h(m) = \{ \begin{matrix}m + 1 & if k = n − 2t − 1 \\ ⌊(m + 1)r⌋ + 1 & if k < n − 2t − 1. \end{matrix}  (6)

Writing x_{0} = x and x_{k+1} = y, the Hamming distance between chain elements x_{j} and x_{j′} with j′ > j is then at most h(j′ − j − 1). We shall often make use of the fact that h(j′) − h(j) ≤ (j′ − j)r + 1. Finally we assume that

p(n) = d h(0)! (\frac{e}{(n − 2t)(k + 1)^{1/k}} )^{r}  (7)

with d = d(n) ≥ 1. The following form of Stirling’s formula (valid for all n > 0) will suffice for our purposes:

\sqrt{n} (\frac{n}{e})^{n} < n! < 3\sqrt{n} (\frac{n}{e})^{n} .  (8)

Let S be a family of subsets of P(n). In what follows, S will usually consist of various chains in P(n). For α ∈ S let I_{α} be the indicator of α, i.e., for Q ⊆ P(n) we have I_{α}(Q) = 1 iff α ⊆ Q. Now define

X_{S} = ∑_{α∈S} I_{α}.  (9)

Proposition 6 Let t ∈ ℕ, x ∈ P_{t}(n) and y ∈ P_{n−t}(n) with x ⊂ y be given. Let S = S(x, y, r) be the set of all (x, y, r)-chains in P(n). Then

lim_{n→∞} 𝔼(X_{S}) = ∞.

Proof. Let R_{k} denote the number of (x, y, r)-chains in P(n). By definition of k and r we have

R_{k} = \binom{n − 2t}{⌈r⌉, ⌈2r⌉ − ⌈r⌉, …, n − 2t − ⌈kr⌉} ≥ \frac{(n − 2t)!}{h(0)!^{k+1}}.

But 𝔼(X_{S}) = R_{k} p^{k}. The result now follows by Stirling’s formula (checking the cases r = 1 and r > 1 separately). □

For α ≠ β ∈ S write α ∼ β if α ∩ β ≠ ∅. Then we define

Δ(S) = ∑_{α∼β} 𝔼(I_{α}I_{β}),  (10)

where the sum is over all ordered pairs α, β ∈ S with α ∼ β.

Lemma 7 Let t ∈ ℕ, x ∈ P_{t}(n) and y ∈ P_{n−t}(n) with x ⊂ y be given. Let S = S(x, y, r) be the set of all (x, y, r)-chains in P(n). Then

Δ(S) ≤ \frac{9}{d} 𝔼(X_{S})^{2},

provided n is large enough.

There are several results on random subgraphs of the hypercube which rely on a similar lemma, essentially giving bounds on the number of pairs of various kinds of paths in the hypercube. In fact, case (a) of the proof of Lemma 7 is similar to Lemma 2.2 proved by Fill and Pemantle in [7], but is sketched for completeness. However, in general their bounds do not apply to our model (even for the simplest case r = 1) owing to the differences in the geometry of the paths involved.

Proof of Lemma 7. Consider any ordered pair (α, β) of (x, y, r)-chains with α ∼ β. Let i = i(α, β) = |α ∩ β| be the number of common elements. Note that 0 < i < k.

A disjoint interval γ is a subset of α \ β with the property that, whenever we have w, w′ ∈ γ, v ∈ α, and w ⊂ v ⊂ w′, we must have v ∈ γ. We then let l be the maximum cardinality (or size) of a disjoint interval and let s be the number of disjoint intervals. Note that 0 < l ≤ k − i and 0 < s ≤ k − i.

Now write ∑_{i,l,s} for the sum over all ordered pairs of (x, y, r)-chains α and β with i(α, β) = i, l(α, β) = l, and s(α, β) = s. Let

Δ_{ils} = ∑_{i,l,s} 𝔼(I_{α}I_{β})

and define Δ_{i}, Δ_{il} and Δ_{is} similarly. We can then write Δ = Δ(S) as

Δ = ∑_{i=1}^{k−1} Δ_{i}, where Δ_{i} = ∑_{l=1}^{k−i} Δ_{il} = ∑_{s=1}^{k−i} Δ_{is} and Δ_{is} = ∑_{l=1}^{k−i} Δ_{ils}. (11)

Let now i, l and s > 0 with i + l ≤ k and i + s ≤ k be given. Then an admissible (i, l, s)-configuration is a set A ⊂ [k] with |A| = i such that the longest interval of consecutive elements in [k]\A contains exactly l elements and such that the number of intervals of consecutive elements is exactly s. The set of all admissible (i, l, s)-configurations, denoted A_{ils}, corresponds to the possible intersection patterns of two (x, y, r)-chains (indeed, the configurations give the positions in which two chains may intersect). Let C_{ils} = |A_{ils}|. Let C_{il} = ∑_{s} C_{ils}, C_{is} = ∑_{l} C_{ils}, and C_{i} = ∑_{l} C_{il}. Note the trivial bounds C_{ils} ≤ C_{il} ≤ C_{i} ≤ \binom{k}{i}.

Now we investigate the number of ways in which a given configuration can be extended. Let i, l and s be given and let α = (x_{1} ⊂ x_{2} ⊂ ⋯ ⊂ x_{k}) be a fixed (x, y, r)-chain and A ∈ A_{ils}. Let E(A) be the number of possible extensions corresponding to the intersection pattern given by A: i.e., E(A) is the number of β that are (x, y, r)-chains in P(n) with α ∩ β = {x_{i}: i ∈ A}. Let

E_{ils} = max_{A∈A_{ils}} E(A).

This time, define E_{il} = max_{s} E_{ils} and E_{is} = max_{l} E_{ils}. To estimate E_{ils}, note that each disjoint interval, between x_{j} and x_{j′} with j′ > j say, contributes a factor of

\binom{⌈j′r⌉ − ⌈jr⌉}{⌈(j + 1)r⌉ − ⌈jr⌉, …, ⌈j′r⌉ − ⌈(j′ − 1)r⌉}.

By the convexity of factorials, E(A) is then maximised if A has as few disjoint intervals as possible and if as many of these intervals as possible have maximum size. Instead of bounding E_{ils} directly, it turns out to be more convenient to consider E_{ils}/R_{k}, where R_{k} is defined to be the number of (x, y, r)-chains in P(n) as in the proof of Proposition 6. This has the advantage that some of the factorials involving ⌈r⌉ and ⌊r⌋ cancel straightaway. The same applies also to E_{il} and E_{is}: for instance, the above argument and the formula for R_{k} given in the proof of Proposition 6 imply that

\frac{E_{il}}{R_{k}} ≤ \frac{h(0)!^{i}}{(n − 2t)!}h(l)! h(k − i − l)!.  (12)

Indeed, note that we must have at least one disjoint interval of size l and that in the worst case, all the remaining disjoint vertices are contained in a single disjoint interval of size k − i − l. We remark that the above inequality also shows that one may interpret E_{il}/R_{k} as an upper bound on the fraction of all (x, y, 1)-chains whose intersection with a given (x, y, r)-chain is an admissible (i, l)-configuration.

For notational convenience let δ_{ils} = Δ_{ils}/𝔼(X_{S})^{2} and define the δ_{i} etc similarly. Noting that 𝔼(X_{S}) = R_{k} p^{k}, we have

δ_{ils} = \frac{Δ_{ils}}{𝔼(X_{S})^{2}} ≤ \frac{R_{k} p^{2k−i} C_{ils} E_{ils}}{𝔼(X_{S})^{2}} ≤ \frac{C_{ils} E_{ils}}{R_{k} p^{i}} .  (13)

We will bound the δ_{ils} by applying different estimates for different ranges of i, l and s. To fix these ranges we need to define the following constants:

λ = 1/40 and ρ = 1/40e.  (14)

Choose κ > 0 sufficiently small so that

(1 − λ)(1 + κ)^{2} < 1.  (15)

Choose σ > 0 sufficiently small so that

(e/σ)^{2σ}(1 − λ)^{ρ}(1 + κ)^{2} < 1.  (16)

Finally choose l_{0} ∈ ℕ large so that for any l ≥ l_{0},

2 (\frac{4e}{l})^{σ} < 1 and h(l)!^{1/(l−1)} ≤ (\frac{lr(1 + κ)}{e})^{r} .  (17)

We assume that n is large enough whenever needed. We shall also make use of the following inequality, which follows immediately from Stirling’s formula (8) and the definition of r and p in (5) and (7):

\frac{h(0)!^{i}}{p^{i} (n − 2t)!} ≤ \frac{(k + 1)^{ir/k}}{d\sqrt{kr}} (\frac{e}{(k + 1)r} )^{h(k−i)} .  (18)

(a) i < λk

It turns out that the only significant contribution of Δ_{ils} to Δ comes from the case when i is small and l = k − i (which implies that s = 1): in the case (a1), when l is small, we have only a trivial bound on the number of configurations but this is compensated by the fact that, in this case, the number of extensions is severely limited. In the case (a2), when l is large, the situation is reversed. Overall this allows us to show that δ_{i} is a constant multiple of the worst case contribution δ_{i,k−i}.

(a1) l ≤ k − 4i

We have ∑_{l=1}^{k−4i} C_{il} ≤ C_{i} ≤ \binom{k}{i} and by (12)

\frac{E_{il}}{R_{k}} ≤ \frac{h(0)!^{i}}{(n − 2t)!} h(k − 4i)! h(3i)!.

Thus, using h(0) ≥ 1 and λ = 1/40, we have

∑_{l≤k−4i} C_{il} \frac{E_{il}}{R_{k}} ≤ \frac{h(0)!^{i}}{(n − 2t)!} h(k − i)! \frac{h(k − 4i)!}{h(k − i)!} h(3i)! \binom{k}{i}

≤ \frac{h(0)!^{i}}{(n − 2t)!} h(k − i)! (\frac{(4ir)^{3}}{((k − 4i)r)^{3}} \frac{ek}{i} )^{⌊ir⌋}

≤ \frac{h(0)!^{i}}{(n − 2t)!} h(k − i)! (\frac{64eλ^{2}}{(1 − 4λ)^{3}} )^{⌊ir⌋}

≤ \frac{h(0)!^{i}}{(n − 2t)!} h(k − i)! \frac{1}{4}.

(a2) l > k − 4i As there are k−l+1 choices for picking the position of the lowest disjoint interval of length l and at most \binom{k−l−1}{i−1} choices for picking the remaining elements we have

C_{il} ≤ (k − l + 1)\binom{k − l − 1}{i − 1}.  (19)

Define M_{il} to be the product of the right-hand sides of inequalities (19) and (12). Thus C_{il} E_{il}/R_{k} ≤ M_{il}. Furthermore, since r ≥ 1,

\frac{M_{i,l+1}}{M_{i,l}} ≥ \frac{k − l}{k − l + 1} \frac{k − i − l}{k − l − 1} (\frac{(l + 1)r}{(k − i − l + 2)r} )^{r}

≥ \frac{k − i − l}{k − i − l + 2} \frac{k − 4i}{4i} ≥ \frac{1}{3} \frac{1 − 4λ}{4λ} = \frac{7}{3}.

Since ∑_{j=0}^{∞}(3/7)^{j} = 7/4, the total contribution of the M_{il} for l > k − 4i is at most 7/4 times that of the maximum term l = k − i.

Putting both (a1) and (a2) together gives

δ_{i} ≤ ∑_{l=1}^{k−i} δ_{il} ≤ 2 \frac{M_{i,k−i}}{p^{i}} ≤ 2 (i + 1) \frac{h(k − i)!}{(n − 2t)!} p^{−i}

≤ 2(i + 1) (\frac{1}{2d})^{i} ,  (20)

since r ≥ 1 and, very crudely, h(k − i) ≥ (1 − λ)(n − 2t) ≥ p^{−1/r}. Thus, using this time that d ≥ 1,

∑_{1≤i≤λk} δ_{i} ≤ 2 ((1 − \frac{1}{2d})^{−2} − 1) ≤ \frac{8}{d}.

(b) λk ≤ i < (1 − ρ)k

(b1) l < l_{0}

We have C_{il} ≤ \binom{k}{i} ≤ 2^{k}. To estimate E_{il}/R_{k}, note that chain elements in the intersection which lie at either end of a disjoint stretch have distance at most h(l). Thus for each disjoint interval (of size l̄ say) we have a contribution of a factor of h(l̄)! ≤ h(0)! (2h(l))^{l̄r}. Using the fact that there are k − i disjoint vertices and at most i + 1 disjoint intervals yields the following bound:

\frac{E_{il}}{R_{k}} ≤ \frac{h(0)!^{i}}{(n − 2t)!} (2h(l))^{(k−i+1)r}.

Hence, by inequality (18), and noting (crudely) that (k+1)^{ir/k} ≤ (k+1)^{r} < e^{ρkr}, we have

δ_{il} ≤ \frac{h(0)!^{i}}{p^{i}(n − 2t)!} (2h(l))^{(k−i+1)r} 2^{k}

≤ \frac{e^{ρkr}}{d} (\frac{e}{(k + 1)r} )^{(k−i+1)r} (2(l_{0}+1)r)^{(k−i+1)r} 2^{k}

≤ \frac{1}{d} (\frac{2^{1+1/ρ}(l_{0}+1)e^{2}}{k} )^{ρkr}

≤ \frac{1}{dk^{3}} .

In the last line we used the fact that k → ∞.

(b2) l > l_{0}

Fix a chain α and any configuration with parameters i, l, and s. Denote the size of the disjoint intervals by l_{j}, for 1 ≤ j ≤ s. Then there are at most h(0)^{i−(s−1)} ∏_{j=1}^{s} h(l_{j})! (x, y, 1)-chains which meet α exactly at the i chosen points. But this product is maximised if we have as many disjoint intervals of size l as possible, say q of them. The remaining disjoint vertices will be distributed among one interval of size l̄, with 1 ≤ l̄ < l, and s − q − 1 unit size intervals. Then noting that ql + l̄+ (s − q − 1) = k − i and s − q − 1 < s gives

\frac{E_{ils}}{R_{k}} ≤ \frac{h(0)!^{i−(s−1)}}{(n − 2t)!} h(l)!^{\frac{k−i−s−l̄}{l−1}} h(l̄)! h(1)!^{s} ≤ \frac{h(0)!^{i}}{(n − 2t)!} h(l)!^{\frac{k−i−s}{l−1}} (4r)^{sr}.

Now use l ≤ k − i < (1 − λ)k and the definition of l in (17) to obtain

\frac{E_{ils}}{R_{k}} ≤ h(0)!^{i} (\frac{e}{n − 2t})^{n−2t} (\frac{lr(1 + κ)}{e})^{(k−i)r} (\frac{4er}{(l + 1)r} )^{sr}

≤ h(0)!^{i} (\frac{e}{n − 2t})^{ir} ((1 − λ)(1 + κ))^{(k−i)r} (\frac{4e}{l})^{s} .

By the definition of p in (7), and again crudely estimating (k+1)^{ir/k} ≤ (k+1)^{r} ≤ (1 + κ)^{ρkr}, we have

δ_{il} ≤ \frac{1}{d} ∑_{s=1}^{k} C_{ils} ((1 − λ)(1 + κ)^{2})^{ρkr} (\frac{4e}{l})^{s} .

When bounding C_{ils} we distinguish two cases. First suppose that s ≤ σk. Note that any admissible configuration may be defined in the following way: we first fix the lowest point of each of the s disjoint intervals. \binom{k}{s} is a crude bound on the number of choices. This first step fixes the positions of at least s−1 common vertices, since unless a disjoint interval is right at the top, it must obviously be below a common vertex. We now fix a configuration uniquely by successively adding a further i − s common vertices on top of the existing common intervals. In other words, we are now drawing i−s+1 elements (with replacement) from a set of s distinct elements, giving us \binom{s+(i−s+1)−1}{i−s+1} = \binom{i}{s−1} choices on the second step. Thus

C_{ils} ≤ \binom{k}{s} \binom{i}{s − 1} ≤ (\frac{ek}{s} )^{s} (\frac{ei}{s − 1})^{s−1} ≤ (\frac{ek}{s} )^{2s} ≤ (\frac{e}{σ} )^{2σk} .

For s > σk we just use the trivial bound C_{ils} ≤ 2^{k}. Plugging in and using (16) and (17) this yields

δ_{il} ≤ \frac{1}{d} ( ∑_{1≤s≤σk} (\frac{e}{σ} )^{2σk} ((1 − λ)(1 + κ)^{2})^{ρkr} + ∑_{σk<s≤k} 2^{k} (\frac{4e}{l})^{s})

≤ \frac{1}{d} (k^{−4} + k2^{k} (\frac{4e}{l_{0}})^{σk})

≤ \frac{1}{dk^{3}} .  (21)

(c) i ≥ (1 − ρ)k

There are at most \binom{i+s}{s} ways of choosing the relative order of i common vertices and the s disjoint intervals. We now fix the size of the intervals, by distributing the k − i − s remaining “disjoint” vertices among the s disjoint intervals. We are choosing these elements (with replacement) from s “urns”, giving at most \binom{k−i−1}{k−i−s} possibilities for this step. Hence, by applying Stirling’s inequality and then that i + s ≤ k and m^{−m} ≤ 3(m + 1)^{−m} for all m ≥ 0,

C_{is} ≤ \binom{i + s}{s}\binom{k − i − 1}{k − i − s}

≤ (\frac{e(i + s)}{s})^{s} (\frac{k − i}{e})^{k−i} (\frac{k − i − s}{e})^{s−(k−i)} (\frac{e}{s − 1})^{(s−1)}

≤ 3^{16} (\frac{ek}{s^{2}} )^{s} (k − i)^{k−i+1} (k − i − s + 15)^{s−(k−i)}.  (22)

Similarly to case (b2), but without the constraint on the size of the longest disjoint interval, the extremal configuration for given s is now attained if we have s − 1 disoint intervals of unit size and one interval containing all the other disjoint vertices. Thus

\frac{E_{is}}{R_{k}} ≤ \frac{h(0)!^{i−(s−1)}}{(n − 2t)!} h(k − i − s + 1)! h(1)!^{s−1}

≤ \frac{3h(0)!^{i}}{(n − 2t)!} (\frac{(k−i −s+15)r}{e} )^{h(k−i−s+1)+1/2} (4r)^{(s−1)r}.

The second line follows by Stirling’s formula (8). By the definition of h, the fact that (k−i −s+15) ≤ 3^{3}(k − i), and inequality (18), we now have

\frac{E_{is}}{R_{k} p^{i}} ≤ \frac{3^{4}}{d} \frac{(k−i)^{3/2}}{\sqrt{k}} (k+1)^{r} ×  (23)

× (\frac{e}{(k+1)r})^{h(k−i)}(\frac{(k−i −s+15)r}{e})^{h(k−i)−(s−1)r}(5r)^{(s−1)r}

≤ \frac{3^{7}}{d} \frac{(k−i)^{3/2}}{\sqrt{k}} (\frac{k − i − s + 15}{(k + 1)^{1−1/(k−i+1)}} )^{h(k−i)} (\frac{5e}{k − i − s + 15})^{(s−1)r}

≤ \frac{3^{10}}{d\sqrt{k}} (k−i)^{5/2} (\frac{k − i − s + 15}{k})^{k−i} (\frac{5e}{k − i − s + 15})^{s−1} .  (24)

The last line follows since one may check that both of the bracketed terms in the second line are smaller than one. Combining inequalities (22) and (24), we have

δ_{is} ≤ \frac{3^{30}}{d\sqrt{k}} (k − i)^{4} (\frac{3e^{2}k}{s^{2}} )^{s} (\frac{k − i}{k})^{k−i} .

It is easily verified that for fixed k and i, the expression (3e^{2}k/s^{2})^{s} is maximised at s = \sqrt{3k} if i ≤ k − \sqrt{3k} and is maximised at s = k − i if i ≥ k − \sqrt{3k}. Thus if i ≤ k − \sqrt{3k}, we have

δ_{is} ≤ \frac{3^{30}}{d\sqrt{k}} (k − i)^{4}e^{2\sqrt{3k}}ρ^{k−i} ≤ \frac{3^{30}}{d\sqrt{k}} k^{4}(ρe)^{2\sqrt{3k}},

and if i ≥ k − \sqrt{2k}, we have

δ_{is} ≤ \frac{3^{30}1}{d\sqrt{k}} (k − i)^{4} (\frac{3e^{2}}{k − i})^{k−i} .

Putting both the above together, and noting that s ≤ k − i ≤ k,

∑_{(1−ρ)k≤i<k} δ_{i} ≤ \frac{3^{30}}{d\sqrt{k}} (  ∑_{(1−ρ)k≤i≤k−\sqrt{3k}} k^{5}(ρe)^{2\sqrt{3k}} + ∑_{k−\sqrt{3k}≤i<k} (k−i)^{5} (\frac{3e^{2}}{k−i})^{k−i})

≤ \frac{3^{30}}{d\sqrt{k}} (k^{6}(ρe^{2})^{\sqrt{3k}} + K)

≤ \frac{1}{dk^{1/4}} ,

where K is some fixed constant.

Summing up the bounds in (a), (b) and (c) gives the desired result:

\frac{Δ}{𝔼(X_{S})^{2}} ≤ \frac{8}{d} + k^{2} \frac{1}{dk^{3}} + \frac{1}{dk^{1/4}} ≤ \frac{9}{d}.

□

We remark that the above result is best possible up to a constant factor. This may be seen by noting that the contribution to Δ/𝔼(X_{S})^{2} of those pairs of chains which have only the bottom element in common is asymptotically equal to 1/ed.

In the previous section, we mentioned that the threshold in Theorem 1 could be tightened by a factor of (n/k)^{2}: this can be done by considering not just (x, y, r)-chains (where the level of the ith element x_{i} is fixed at |x_{i}| = |x| + ⌈ir⌉), but allowing the level of x_{i} to deviate from this by a factor of \sqrt{r}. The calculations are then more cumbersome, but the techniques of this section still apply.

Finally, we state a slight variant of the previous lemma, which will be needed in [11], the difference being that the regular chains under consideration are now “squeezed”: let k be given as before and let m = m(n) and m′ = m′(n) be given integer functions which are o(n). In the definitions of r, h, and p in (5), (6), and (7) respectively, replace the term 2t by m + m′. Then we say that (x_{1} ⊂ ⋯ ⊂ x_{k}) is an [m, m′, r]-chain if |x_{i}| = m + ⌈ir⌉ for all i.

Lemma 8 Let S be the set of all [m, m′, r]-chains in P(n). Then for large enough n, and p as in (7), we have

Δ(S) ≤ \frac{9}{d} 𝔼(X_{S})^{2}.

The proof of Lemma 7 goes through as before: we may first of all assume without loss of generality that m ≥ m′; it turns out that the only difference arises when bounding the number of extensions: in the extremal configuration the longest disjoint interval is now situated at the top, which contributes a factor of at most (h(l)+m)_{m} to the numerator of the E_{ils}/R_{k}. Similarly, the second largest interval contributes a factor of at most (h(l) + m′)_{m′}. This is compensated by the additional (n)_{m+m′} in the denominator. In fact the only reason for stating Lemma 8 separately was to avoid additional notation in the previous lemma and its proof.

We further remark that the above bound on Δ(S) is only required in [11]. For the purposes of this paper, it would have been slightly more convenient to bound 𝔼(X_{S}^{2}) directly instead of Δ(S).

4 Proof of Theorem 1

The technically difficult part in the proof of Theorem 1 has been dealt with in Lemma 7, and hence this theorem may now be proved easily.

Proof of Theorem 1. For the first part assume that p (k +1)^{n/k} → 0. Let Y_{k} then be the number of k-element chains in P(n, p). The number of k-element chains in P(n) is at most (k +1)^{n}. To see this, note that we may associate with each k-element chain α a (k+1)-colouring of {1, …, n} as follows: Suppose α = (x_{1} ⊂ x_{2} ⋯ ⊂ x_{k}). Assign colour 1 to all elements in x_{1}, colour j to all elements in x_{j} \ x_{j−1} for 1 < j ≤ k and colour k+1 to [n]\x_{k}. Hence

ℙ(Y_{k} > 0) ≤ 𝔼(Y_{k}) ≤ (k+1)^{n} p^{k} = o(1),

which implies the first statement.

To prove the second statement, suppose p (k+1)^{n/k}(k/n)^{2} → ∞. Let r be given by (5). It is easily checked that this implies that p satisfies (7) with d = d(n) → ∞. Now let S be the set of (∅, [n], r)-chains, so that X_{S} is the number of (∅, [n], r)-chains in P(n, p). Since Var(X_{S}) ≤ Δ(S) + 𝔼(X_{S}) (see e.g. [1]), the desired result follows immediately from Chebyshev’s inequality after applying Proposition 6 and Lemma 7 with t = 0. □

5 Proof of Theorem 4

We shall use some results on branching processes in the proof of Theorem 4 in order to “amplify” the results of the previous section. This is a natural approach also exploited in [7]. We first present a few basic concepts and some notation.

Let X be a nonnegative integer valued random variable. A Galton-Watson branching process with family size X is a discrete Markov chain (X_{t})_{t=0}^{∞} with the following properties: at time t = 0 we have one “ancestor”, so we set X_{0} = 1. For t ≥ 1 define X_{t} to be the sum of X_{t−1} independent random variables, each having the same distribution as X (see e.g. [8] for details). As we shall only be concerned with the case when X has Poisson distribution with parameter c, in what follows (X_{t})_{t=0}^{∞} will always refer to a branching process with this property. Let η be the extinction probability of this process:

η = η(c) = ℙ(X_{t} = 0 for some t).  (25)

A simple result in branching process theory says that if c > 1 then η is the (unique) root of s = 𝔼(s^{X}) = e^{c(s−1)} in 0 < s < 1. Another basic result (see [8] again) is that for any constant k > 0, we have

lim_{t→∞} ℙ(X_{t} = k) = 0.  (26)

We now define branching processes in P(n). Consider any x ∈ P(n) at level m, say. An upward x-process (Z_{t}^{n})_{t=0}^{n−m} = (Z_{t}^{n}(x))_{t=0}^{n−m} is defined by letting Z_{t}^{n} denote the number of z ∈ P_{m+t}(n, p) that are connected to x via an (x, z, 1)- chain in P(n, p). A downward y-process is defined similarly. For simplicity, we will henceforth call an (x, y, 1)-chain an xy-chain.

The following proposition will help us determine the number of descendants we need at each end in order to link the “top” and “bottom” of P(n, p):

Proposition 9 For any given c ≥ e define η = η(c) as in (25). Given 0 < ε < 1−η, there exists a = a(c, ε) ∈ ℕ with (43/44)^{a} ≤ ε satisfying the following: for a random variable Z ∼ Bin(⌈2a/(1 − η − ε)⌉ , 1 − η − ε), we have ℙ(Z < a) < ε.

Proof. Certainly ℙ(Z > a) ≤ ℙ(|Z − 𝔼(Z)| ≥ a). Thus the result follows from Chernoff’s bound. □

For positive integers m and n with n > 2m, denote by P_{m...n−m}(n, p) the family of all sets from P(n, p) of cardinality at least m and at most n − m. Let X ⊆ P_{m}(n) and Y ⊆ P_{n−m}(n) be given. We say that X and Y can be linked if there are x ∈ X and y ∈ Y such that there is an xy-chain contained in P_{m+1...n−m−1}(n, p).

Lemma 10 Let ε > 0, c ≥ e and m ∈ ℕ be given. Let p = c/n and define η = η(c) as in (25). Let a = a(c, ε) be as in Proposition 9. Let

b = ⌈2a/(1 − η − ε)⌉ .

Furthermore let X ⊆ P_{m}(n) with |X| = b and Y ⊆ P_{n−m}(n) with |Y | = b and x ⊂ y for any x ∈ X and y ∈ Y be given. Then for large enough n

ℙ(X and Y can be linked) ≥ 1 − ε.

Lemma 7 implies that a single pair x ⊂ y is linked with probability bounded away from zero. Hence in order to prove Lemma 10 we would like to consider several pairs at the same time to ensure that with arbitrarily high probability we can find at least one that is linked by a chain. The following lemma tells us that this is indeed possible, provided the elements at each level are far enough apart.

Given x, y ∈ P(n) with x ⊂ y, denote by P^{xy} the subset of P(n) consisting of all elements (including x and y) which are both subset of y and superset of x.

Lemma 11 Let t, h ∈ ℕ be given. Suppose that x_{1}, x_{2} ∈ P_{t}(n) and y_{1}, y_{2} ∈ P_{n−t}(n) are such that x_{1} ⊂ y_{1}, x_{2} ⊂ y_{2}, d_{H}(x_{1}, x_{2}) ≥ h and d_{H}(y_{1}, y_{2}) ≥ h. Then the proportion of all x_{1}y_{1}-chains that meet P^{x_{2}y_{2}} is at most 2e^{−h/2}, provided n is large enough.

Proof. Let x̄ = x_{1} ∪ x_{2} and ȳ = y_{1} ∩ y_{2}. Then one may easily verify that P^{x_{1}y_{1}} ∩ P^{x_{2}y_{2}} = P^{x̄ȳ}. Furthermore x̄ has cardinality at least t + h and ȳ has cardinality at most n − (t + h). The crucial observation now is that any x_{1}y_{1}- chain which meets P^{x_{2}y_{2}} must be contained in P^{x_{1}ȳ} ∪ P^{x̄y_{1}}. For suppose an x_{1}y_{1}-chain contains a z ∈ P^{x_{2}y_{2}}. Then all elements in that chain below z are contained in P^{x_{1}ȳ} and all elements above z are contained in P^{x̄y_{1}}. It follows that any x_{1}y_{1}-chain which meets P^{x_{2}y_{2}} intersects (P^{x_{1}ȳ}∪P^{x̄y_{1}})∩P_{⌊n/2⌋}(n). But the fraction of such chains among all x_{1}y_{1}-chains is at most

\frac{|(P^{x_{1}ȳ} ∪ P^{x̄y_{1}}) ∩ P_{⌊n/2⌋}(n)|}{|P^{x_{1}y_{1}} ∩ P_{n/2}(n)|} ≤ 2 \binom{n − 2t − h}{⌊(n − 2t)/2⌋}/ \binom{n − 2t}{⌊(n − 2t)/2⌋} ≤ 2e^{−h/2}

and the lemma follows. □

We are now ready to prove the Lemma 10. In the sequel, we will make use of the following form of the second moment inequality:

ℙ(X_{S} = 0) ≤ 1 − \frac{𝔼(X_{S})^{2}}{𝔼(X_{S}^{2})} .  (27)

A proof of this elementary inequality may be found in [2].

Proof of Lemma 10. Let a be as in Proposition 9 and set h = log 4a. For each x ∈ X consider the upward x-branching process. For each such process the probability of survival during the next h steps is at least 1 − η − ε. We may assume that n is large enough to ensure that the probability that these processes intersect is at most ε. Thus, by the definition of b in Lemma 10 and by Proposition 9, with probability at least 1−2ε there are a processes which survive until level m + h. Pick one descendant x_{i} ∈ P_{m+h}(n) of each, where 1 ≤ i ≤ a. Let X′ = {x_{1}, …, x_{a}}. Note that we may find X̄ ⊂ X, X̄ = {x̄_{1}, …, x̄_{a}}, so that there is an x̄_{i}x_{i}-chain in P(n, p) for all i. Analogously, with probability 1 − 2ε, we may find a set Y′ = {y_{1}, …, y_{a}} with Y′ ⊂ P_{n−m−h}(n) and which is linked to Y in a similar way. Now assume that n is large enough to ensure that with probability at least 1 − ε these branching processes have the following property: (x_{i}\x̄_{i}) ∩ (x_{j}\x̄_{j}) = ∅ for all pairs i ≠ j, and similarly for the y_{i}. The latter implies that d_{H}(x_{i}, x_{j}) ≥ 2h and d_{H}(y_{i}, y_{j}) ≥ 2h for i ≠ j.

Now let S_{i} be the set of x_{i}y_{i}-chains and let T_{i} ⊆ S_{i} be the set of x_{i}y_{i}-chains not meeting ⋃_{j≠i} P^{x_{j}y_{j}}. We let Y_{i} = X_{S_{i}} and Yi^{′} = X_{T_{i}}, where the notation is as in (9). We also let Δ_{i} = Δ(S_{i}) and Δi^{′} = Δ(T_{i}), using the notation of (10). Note that Proposition 6 certainly implies that 𝔼(Y_{i}) ≤ 𝔼(Y_{i})^{2}. Thus by the definition of Δ_{S_{i}} and Lemma 7 (with t = m + h and d = 1) we have

𝔼(Y_{i}^{2}) ≤ Δ_{i} + 𝔼(Y_{i}) + 𝔼(Y_{i})^{2} ≤ 11𝔼(Y_{i})^{2}.

Now Yi^{′} ≤ Y_{i} implies that 𝔼(Y_{i}^{′2}) ≤ 𝔼(Y_{i}^{2}). But since 2a exp(−h) ≤ 1/2, Lemma 11 shows that 𝔼(Yi^{′}) ≥ 𝔼(Y_{i})/2. Altogether this implies that

\frac{𝔼(Yi^{′})^{2}}{𝔼(Y_{i}^{′2})} ≥ \frac{𝔼(Y_{i}^{2})}{4𝔼(Y_{i}^{2})} ≥ \frac{1}{44}.

Thus applying in turn the independence of the Yi^{′}, the second moment inequality (27), and the definition of a in Proposition 9, we have (for n sufficiently large)

ℙ (⋂_{i=1}^{a} Yi^{′} = 0) = ∏_{i=1}^{a} ℙ (Yi^{′} = 0) ≤ (\frac{43}{44})^{a} ≤ ε

and the lemma follows. □

In the remainder of this section we shall define (X_{t}^{n})_{t=0}^{n} as the Markov chain of an upward ∅-process and (Y_{t}^{n})_{t=0}^{n} as that of a downward [n]-process. We need a final preparation for the proof of Theorem 4:

Proposition 12 For a given c ≥ e define η = η(c) as in (25) and let p = c/n. Let 0 < ε < 1 − η and b ∈ ℕ be given. Then there exist m_{0}, n_{0} ∈ ℕ so that for m ∈ {m_{0}, m_{0} + 1} and all n ≥ n_{0}, we have

ℙ(X_{m}^{n} = 0) ≥ η − ε,  (28)
ℙ(X_{m}^{n} ≥ b) ≥ 1 − η − ε.  (29)

Proof. Let (X_{m})_{m=0}^{∞} be a Poisson branching process with parameter c. Note that ℙ(X_{m} = 0) ↑ η. Thus by (26) there is an m_{0} such that for m ∈ {m_{0}, m_{0}+1} we have

ℙ(X_{m} = 0) ≥ η − ε/2,
ℙ(X_{m} ≤ b | X_{m} > 0) ≤ ε/2.

It is straightforward to show that for fixed m, the random variables X_{m}^{n} tend to X_{m} in distribution as n → ∞. This implies that (28) and (29) hold for sufficiently large n. □

Proof of Theorem 4. Let ε > 0 be given. We now fix an a = a(c, ε) satisfying the conditions in Proposition 9 and let b = ⌈2a/(1 − η − ε)⌉. Then we fix m_{0} = m_{0}(b, ε) as in Proposition 12 and let m = m_{0} +1. Consider the branching processes (X_{t}^{n})_{t=0}^{n}, (Y_{t}^{n})_{t=0}^{n} defined earlier. We will distinguish several cases according to their (non)-extinction during the first m generations. To do so we first define some events. For Q ⊆ P(n) and i = 0, 1 call x ∈ Q_{m} i-connected if there is a zx-chain in Q for some z ∈ P_{i}(n). Then we define

A = {Q ⊆ P(n): ∅, [n] ∉ Q};
B^{u} = {Q ⊆ P(n): Q_{m} contains b elements which are 0-connected};
C^{u} = {Q ⊆ P(n): Q_{m} contains b elements which are 1-connected}.

Here the superscript accounts for the fact that we consider the upward branching process. Observe that Q ∈ B^{u} iff X_{m}^{n}(Q) ≥ b. For later use we now give some related definitions. First we equip the elements from P_{m}(n) with a total ordering by letting x < y if min x\y < min y\x. Now define B_{m}(Q) to be the set of the first b elements in Q_{m} which are 0-connected. If there are less than b elements in Q_{m} which are 0 connected then let B_{m}(Q) consist of all of these. Analogously define C_{m}(Q) to be the set of the smallest elements in Q_{m} which are 1-connected (again at most b of them).

Now we define some events for the downward branching process. To make them fit with the upward branching process we slightly refine the above definitions. For i = 0, 1 call an element y ∈ Q_{n−m} strongly (n − i)-connected if for any x ∈ B_{m}(Q) ∪ C_{m}(Q), we have x ⊂ y, and furthermore there is a yz-chain in Q for some z ∈ Q_{n−i}. With this notion we define

B^{d} = {Q ⊆ P(n): Q_{n−m} contains b strongly n-connected elements};
C^{d} = {Q ⊆ P(n): Q_{n−m} contains b strongly (n − 1)-connected elements}.

Observe that all events defined above only depend on P_{0...m}(n, p)∪P_{n−m...n}(n, p). Also observe that

ℙ(length P(n, p) ≥ n − 1) ≤ 1 − ℙ(A) ≤ ε.  (30)

Now we estimate ℙ(length P(n, p) ≥ n − 2). Assume that B^{u} and B^{d} both hold. Then there exist X ⊆ P_{m}(n, p) and Y ⊆ P_{n−m}(n, p) with |X| = |Y | = b such that all elements from X are 0-connected in P(n, p) and all elements from Y are strongly n-connected in P(n, p). We may assume that X contains the b smallest 0-connected elements and thus x ⊂ y for any x ∈ X and y ∈ Y. If X and Y can be linked then length P(n, p) ≥ n − 2. Observe that the event that X and Y can be linked only depends on P_{m+1...n−m−1}(n, p). Hence if B^{u} and B^{d} hold then by applying Lemma 10 we have that

ℙ( length P(n, p) ≥ n − 2 | B^{u} ∩ B^{d}) ≥ 1 − ε.

By (29) from Proposition 12, we have

ℙ(B^{u}) ≥ 1 − η − ε.  (31)

As b and m are constant, the probability that a fixed y ∈ P_{n−m}(n) does not contain all elements from B_{m}(P(n, p)) ∪ C_{m}(P(n, p)) is O(1/n). Hence,

ℙ(B^{d}) ≥ 1 − η − 2ε  (32)

provided n is large enough. Thus,

ℙ(length P(n, p) ≥ n − 2) ≥ (1 − ε)(1 − η − ε)(1 − η − 2ε).  (33)

On the other hand, if length P(n, p) ≥ n − 2 and A does not hold, then certainly X_{m}^{n} > 0 and Y_{m}^{n} > 0. Thus, by (28) from Proposition 12,

ℙ(length P(n, p) ≥ n − 2) ≤ ℙ(X_{m}^{n} > 0 and Y_{m}^{n} > 0) + ℙ(A)
≤ (1 − η + ε)^{2} + ε.  (34)

Now we consider ℙ(length P(n, p) ≤ n − 4). We first estimate ℙ(C^{u}). Let k satisfy (η + ε)^{k} ≤ ε/2. Let x_{i} = {i} for i = 1, …, k. For each x_{i}, consider the upward x_{i}-branching process. Let D denote the event that the branching processes are disjoint up to level m, i.e., x′_{i} ≠ x′_{j} whenever i ≠ j, x_{i} ⊂ x′_{i}, x_{j} ⊂ x′_{j}, and x′_{i}, x′_{j} ∈ P_{1...m}(n, p). Then ℙ(D) ≥ 1 − ε/2. Observe that C^{u} holds if at least one of the branching processes has (at least) b descendants in the mth generation. Hence, by (29) from Proposition 12, we have ℙ(¬C^{u} | D) ≤ (η + ε)^{k} ≤ ε/2. Thus,

ℙ(C^{u}) ≥ 1 − ε.  (35)

As in the proof of (32), we have

ℙ(C^{d}) ≥ 1 − 2ε.  (36)

Moreover, if B^{u} and C^{d} both hold, then Lemma 10 implies that with probability at least 1 − ε we have length P(n, p) ≥ n − 3. The same is true if B^{d} and C^{u} both hold. Hence by (31), (32), using that B^{u} and B^{d} are independent, (35), and (36) imply

ℙ(length P(n, p) ≥ n − 3) ≥ (1 − ε)ℙ((B^{u} ∩ C^{d}) ∪ (B^{d} ∩ C^{u}))
≥ (1 − ε)ℙ(B^{u} ∪ B^{d}) − ℙ(¬(C^{u} ∩ C^{d}))
≥ (1 − ε)(1 − (η + ε)(η + 2ε)) − 3ε.

Thus

ℙ(length P(n, p) ≤ n − 4) ≤ 1 − (1 − ε)(1 − (η + ε)(η + 2ε)) + 3ε
≤ (η + 2ε)^{2} + 4ε.  (37)

On the other hand, if both branching processes do not survive (and ∅, [n] ∉ P(n, p)) then the length can be at most n−4. Thus by (28) from Proposition 12,

ℙ(length P(n, p) ≤ n − 4) ≥ ℙ(X_{m}^{n} = 0 and Y_{m}^{n} = 0) − ℙ(A)
≥ (η − ε)^{2} − ε.  (38)

Finally if both C^{u} and C^{d} hold then with probability at least 1 − ε we have length P(n, p) ≥ n − 4. Hence by (35) and (36)

ℙ(length P(n, p) ≤ n − 5) ≤ 4ε.  (39)

The theorem now follows from (30), (33), (34), (37), (38), and (39) by using the fact that ε is arbitrary. □

We remark that the methods of this section would also enable us to replace the condition pn^{r} → ∞ by pn^{r} ≥ C for some C depending only on the constant r in the statement of Corollary 2. However, the analysis is rather cumbersome if r is not an integer, so we have chosen to omit it.

References

[1] N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, 1992.

[2] B. Bollobás, Random graphs, Academic Press, London, 1985.

[3] B. Bollobás and G. Brightwell, Random high-dimensional orders, Adv. Appl. Prob. 27, 161–184 (1995).

[4] B. Bollobás, Y. Kohayakawa, and T. Łuczak, On the diameter and radius of random subgraphs of the cube, Random Struct. Alg., 5, 627–648 (1994).

[5] B. Bollobás, Y. Kohayakawa, and T. Łuczak, Connectivity properties of random subgraphs of the cube, Random Struct. Alg., 6, 221–230 (1995).

[6] G. Brightwell, Models of random partial orders, Surveys in Combinatorics 1993 (K. Walker, Ed.), pp. 53–83, Cambridge Univ. Press, Cambridge, UK.

[7] J.E. Fill and R. Pemantle, Percolation, first-passage percolation and covering times for Richardson’s model of the n-cube, Annals Appl. Probab. 3 (2), 593– 629 (1993).

[8] T.E. Harris, The Theory of Branching Processes, Springer Verlag, Berlin, 1963.

[9] Y. Kohayakawa and B. Kreuter, The width of random subsets of Boolean lattices, submitted, 1998.

[10] B. Kreuter, Small sublattices in random subsets of Boolean lattices, Random Struct. Alg., to appear.

[11] D. Osthus, Maximum antichains in random subsets of the Boolean lattice (in preparation).

[12] A. Rényi. On random subsets of a finite set, Mathematica (Cluj ), 3 (26), 355–362 (1961).