The Width 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–090 São Paulo, Brazil

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

B. Kreuter

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

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

Abstract Suppose we toss an independent coin with probability of success p for each subset of [n] = {1, …, n}, and form the random hypergraph P(n, p) by taking as hyperedges the subsets with successful coin tosses. We investigate the cardinality of the largest Sperner family contained in P(n, p). We obtain a sharp result for the range of p = p(n) in which this Sperner family has cardinality comparable to the cardinality of P(n, p).

1 Introduction

As is well known, a basic result in extremal set theory is a theorem of Sperner, which determines the width, that is, the maximum cardinality of an antichain, in the poset P(n) = 2^{[n]}. The investigation of extensions of this 74-year-old result has given rise to a surprisingly rich theory; the reader unfamiliar with the more recent developments in this area is encouraged to consult the monograph of Engel [8]. In this note, we are interested in the width of a poset naturally derived from P(n) = 2^{[n]}.

Let 0 ≤ p ≤ 1 be given, and consider the random subposet P(n, p) ⊂ P(n), whose elements are randomly chosen from P(n), independently, with probability p each, and the order relation is the naturally induced order. Our main aim here is to investigate the width of the random poset P(n, p).

For a good introduction to the theory of random posets, including results on the width, we recommend a survey of Brightwell [7]. It should be observed that, somewhat surprisingly, however, the model of random posets that we are concerned with here has not been studied to any great extent. Indeed, we shall settle here a rather basic problem about the width of P(n, p). We shall observe that the width of P(n, p), measured against the cardinality of P(n, p), varies from 1 to 0 as p grows (this is an easy observation), and we shall identify in our main theorem the parameterization of p that makes it transparent how this decay takes place (see Theorem 1 below). Let us mention that our technique also gives structural information about the largest antichains in P(n, p).

∗Research supported by PROBRAL (proj. 026/95 and 089/99), a CAPES–DAAD exchange programme.

†Partially supported by MCT/CNPq through ProNEx Programme (Proc. CNPq 664107/1997–4), by CNPq (Proc. 300334/93–1, 910064/99–7, and 468516/2000–0), and by FAPESP (Proc. 96/04505–2).

It may be of some interest to state a version of our results in terms of counting, and in the language of hypergraphs. Let H_{n,m} = {H_{1}, …, H_{m}} be a collection of m subsets of [n]. Denote by α(H_{n,m}) the size of the largest Sperner family contained in H_{n,m}. That is, α(H_{n,m}) is the largest cardinality of a subcollection of H_{n,m} of mutually incomparable elements. Define b = b(n) so that

m = m(n) = n^{−b\sqrt{n}} 2^{n}.  (1)

Theorem 1 below implies that a typical H_{n,m} (that is, almost all of them) are such that

\frac{1}{m}α(H_{n,m}) → 1 if b = b(n) → ∞ as n → ∞  (2)

and

\frac{1}{m}α(H_{n,m}) → 0 if b = b(n) → 0 as n → ∞.  (3)

Moreover, if b(n) → b_{0} as n → ∞, where 0 < b_{0} < ∞ is some constant, then the ratio α(H_{n,m})/m converges to a constant c(b_{0}) > 0, which we explicitly identify.

The random poset P(n, p) was probably first investigated by Rényi [15] who, answering a question of Erdős, determined the minimal asymptotic value of p = p(n) above for which the probability that P(n, p) should itself be an antichain tends to 0. The study of P(n, p) remained dormant for many years, but, recently, motivated by the explosive growth of the research in the theory of random graphs, Kreuter [12] investigated for P(n, p) analogues of some classical problems in random graphs. In modern language, Rényi established the threshold function for the emergence of the Boolean lattice L = P(1) in P(n, p). Kreuter extended this result by determining the emergence threshold function for a large class of lattices L. The interested reader is referred to [12], which may be thought of as a modern sequel to Rényi’s pioneering work [15]. For the background from the theory of random graphs, see Bollobás [2] and Janson, Łuczak, and Ruciński [10].

Another parameter that is of interest in the study of a poset is its height or length, i.e., the cardinality of a longest chain. For results concerning the length of P(n, p), the reader is referred to Kohayakawa, Kreuter, and Osthus [11]. We mention that Bollobás and Brightwell [4, 5] have investigated the height of random d-dimensional partial orders and, more generally, of random partial orders defined in terms of ‘box spaces’ (certain partially ordered probability spaces). The study of the height of random 2-dimensional partial orders goes back to Ulam [16] (see [5, 7] for further references). The flavour of the arguments in [11] are, however, closer to the ones in Fill and Pemantle [9] and Bollobás, Kohayakawa and Łuczak [6].

Further results

Soon after the results in this note were obtained, Osthus [14] discovered a powerful method of proof inspired in Lubell’s beautiful proof [13] of Sperner’s theorem. Indeed, making use of a technical lemma [11, Lemma 7], Osthus showed that Lubell’s method can be essentially carried over to P(n, p), for a wide range of p = p(n). Write p = p(n) = (r/n)^{r}. Osthus [14] determined α(P(n, p)) up to a multiplicative factor of 1+o(1) if r → ∞ as n → ∞. Moreover, he proved that, with probability tending to 1 as n → ∞, we have

α(P(n, p)) = (1 + o(1))p\binom{n}{⌊n/2⌋}

when p = ωn^{−1} log n, where ω = ω(n) is any function with ω → ∞ as n → ∞. (It is an open problem whether the log n factor is required.)

The results in this note cover a narrower range of p = p(n), namely, r above has to be of order \sqrt{n}; note that, however, this is an interesting period of the evolution of P(n, p), as show (1), (2), and (3). Our proof follows the ‘chain decomposition method’, based on matchings, and is self-contained. For a discussion on these classical proofs of Sperner’s theorem, see, e.g., [1] and [3].

2 Statements of the main results

Denote by Φ the distribution function of the normal distribution, i.e.,

Φ(b) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{b} exp(−x^{2}/2) dx.

For two functions f(n) and g(n), write f ∼ g if lim_{n→∞} f(n)/g(n) = 1 and f ≍ g if

0 < lim inf_{n→∞} f(n)/g(n) ≤ lim sup_{n→∞} f(n)/g(n) < ∞.

Our main result in this note may be formulated as follows. In what follows, we use the term almost surely to mean ‘with probability tending to 1 as n → ∞’.

Theorem 1 Let b > 0 be a constant and p = n^{−b\sqrt{n}}. Then we almost surely have

\frac{α(P(n, p))}{|P(n, p)|} ∼ Φ(2b) − Φ(−2b).

Using standard estimates, we may deduce the following numerical result from Theorem 1.

Corollary 2 There is an absolute constant ε_{0} > 0 for which the following assertion holds. For any fixed 0 < ε < ε_{0}, we have that

lim_{n→∞} P (|\frac{α(P(n, p))}{|P(n, p)|} − ε\sqrt{\frac{8}{π}} | ≤ 3ε^{2}) = 1.

We shall in fact prove the the following structural result.

Theorem 3 Almost surely, one may obtain a Sperner family of cardinality ∼ α(P(n, p)) from P(n, p) by taking all members of P(n, p) whose cardinalities are in the interval {⌊n/2− b\sqrt{n}⌋, …, ⌊n/2+b\sqrt{n}⌋\}, and then removing from this family the elements that are contained in some other element of the family.

The proofs of Theorems 1 and 3, which are quite simple and are self-contained, are given in Section 3.2. Since we would like to reach these proofs as soon as possible, our results are presented in a somewhat indirect order. We introduce the main concepts that we shall need and state the three technical lemmas that are required in the proofs of Theorems 1 and 3 in Section 3.2, and immediately give the half-page proof of Theorems 1 and 3. The remainder of this note is devoted to the proofs of the three technical lemmas.

Our logarithms are natural logarithms.

3 Proofs

3.1 Preliminaries

In this section, we state some asymptotics involving binomial coefficients. To simplify the notation, we shall often omit the ⌊ ⌋ and ⌈ ⌉ signs whenever they are not crucial. Moreover, we may and shall assume whenever needed that n is larger than any fixed absolute constant.

Let k, ℓ be integers with |k|, |ℓ| = O(\sqrt{n}) and k + ℓ > 0. Then,

\binom{n}{\frac{n}{2} − k, \frac{n}{2} − ℓ, k + ℓ} = \binom{n − k − ℓ}{\frac{n}{2} − k}\binom{n}{k + ℓ} ≍ \frac{2^{n}}{\sqrt{n(k + ℓ)}} (\frac{en}{2(k + ℓ)})^{k+ℓ} .  (4)

For later reference, notice that the multinomial coefficient on the left-hand side of (4) counts the number of pairs (A, B) with A ⊂ B ⊂ [n], |A| = n/2 − k, and |B| = |A| + k + ℓ.

For integers k and m with k = O(\sqrt{m}) and large enough m, the following rough bound holds:

\binom{m}{k} ≥ \frac{1}{m} (\frac{em}{k})^{k} .  (5)

Let an integer i with |i| ≤ (log n)\sqrt{n} and a real number b with 0 < b = O(1) be given. Then, for large n, we have

\binom{n}{⌊n/2⌋ + i}/ \binom{n}{⌊n/2⌋ + i + ⌊b\sqrt{n}⌋} ≤ (1 + \frac{2|i| + b\sqrt{n}}{n/2 − |i| − b\sqrt{n} + 1})^{b\sqrt{n}}
≤ exp (\frac{5 log n}{\sqrt{n}}b\sqrt{n}) = n^{5b}.  (6)

For a set-system Q ⊆ P(n) and an integer i with |i| ≤ n/2, denote by Q_{i} the (⌊n/2⌋−i)- th layer of Q, i.e.,

Q_{i} = {x: x ∈ Q and |x| = ⌊n/2⌋ − i}.

For a set of integers S ⊆ {−⌈n/2⌉, …, ⌈n/2⌉}, let Q_{S} = ⋃_{i∈S} Q_{i}. The set Q_{S} will sometimes be viewed as a graph, where {x, y} is an edge in Q_{S} if and only if x ⊂ y or y ⊂ x. Instead of P(n, p)_{S} we write P_{S}(n, p), and instead of Q_{{i,j}} we simply write Q_{i,j}.

Suppose 0 < p < 1 and 0 < ε < 1 are given, and let X be binomially distributed with parameters p and N. Then, the standard Chernoff bound for large deviations states that

P [|X − Np| ≥ εNp] ≤ 2 exp (−\frac{1}{3}ε^{2}Np)  (7)

(see, e.g., [10, Corollary 2.3]). Routine calculations using the Chernoff bound give the following simple estimate on |P_{i}(n, p)|.

Fact 4 Suppose p ≥ (2/3)^{n}. Then, with probability at least 1 − exp {−(5/4)^{n}}, for every integer i with |i| ≤ (log n)\sqrt{n}, we have

|P_{i}(n, p)| = (1 + O (\frac{1}{n})) \binom{n}{⌊n/2⌋ − i}p.

3.2 Main lemmas and the proofs of Theorems 1 and 3

We shall now introduce some key concepts and three lemmas that will allow us to prove Theorems 1 and 3. Since the lemmas are somewhat technical, their proofs are postponed to the Section 3.3.

Let a positive integer n, reals 0 < ε(n) < 1, 0 < p(n) < 1, and c = c(n) > 0 be given. Let j be an integer with c\sqrt{n} ≤ |j| ≤ (log n)\sqrt{n}. Define i = i(j) by putting

i = j − sgn(j)⌊2c\sqrt{n}⌋,  (8)

where sgn(j) denotes the sign of j. Note that, then, we have |j −i| = ⌊2c\sqrt{n}⌋ and, moreover, |i| ≤ |j|. In what follows, we shall often be interested in the bipartite graph Q_{i,j} with i and j as above. We now introduce some important definitions for what follows.

We shall say that Q ⊆ P(n) is (c, ε, p, j)-uniform if properties (a) and (b) below are fulfilled.

(a) The number of vertices of Q_{i,j} that have degree larger than

(1 + ε)\binom{n/2 + |j|}{⌊2c\sqrt{n}⌋}p

is at most 2 exp(−ε^{−1})|Q_{j}|.

(b) The number of vertices in Q_{j} that have Q_{i,j}-degree smaller than

(1 − ε)\binom{n/2 + |j|}{⌊2c\sqrt{n}⌋}p

is at most exp(−ε^{−1})|Q_{j}|.

The set-system Q ⊆ P(n) will be called (c, ε, p)-uniform if the following properties are fulfilled:

(i) For all integers j with |j| ≤ (log n)\sqrt{n}, we have

|Q_{j}| = (1 + Θ(1/n))\binom{n}{⌊n/2⌋ − j}p.

(ii) Let S = \{−n/2, …, −(log n)\sqrt{n}\} ∪ \{(log n)\sqrt{n}, …, n/2\}. Then |Q_{S}| ≤ 2^{n}p/n. (iii) For all integers j with c\sqrt{n} ≤ |j| ≤ (log n)\sqrt{n}, the set-system Q is (c, ε, p, j)-uniform.

Now we state three lemmas that together imply Theorems 1 and 3.

Lemma 5 Let c = c(n) > 0 with c = O(1) be given. Let p = n^{−c\sqrt{n}}(4c/e)^{2c\sqrt{n}} and put S = \{−c\sqrt{n}, …, c\sqrt{n}\}. Then, almost surely, the number of edges in P_{S}(n, p) is at most 2^{n}p/\sqrt{n}.

Lemma 6 For c = c(n) > 0 with c = O(1), define ε = 2^{−c\sqrt{n}/2}, and p = n^{−c\sqrt{n}}(9c/e)^{2c\sqrt{n}}. Then, almost surely, the random set-system P(n, p) is (c, ε, p)-uniform.

Lemma 7 Let c = c(n) > 0 with c = O(1) be given. Define p = n^{−c\sqrt{n}}(9c/e)^{2c\sqrt{n}} and let 0 < ε ≤ 1/n be given. Assume that Q is (c, ε, p)-uniform. Then the width of Q is at most

( ∑_{|j|<c\sqrt{n}} \binom{n}{⌊n/2⌋ − j} + O (\frac{2^{n}}{n} )) p.

We now deduce Theorems 1 and 3 from Lemmas 5, 6, and 7.

Proof of Theorems 1 and 3. Let b > 0 be given. Define c = c(n) by

p = n^{−b\sqrt{n}} = n^{−c\sqrt{n}} (\frac{4c}{e})^{2c\sqrt{n}} .

Then c = b + o(1). Let S be as in Lemma 5. Then removing from P_{S}(n, p) all elements that are contained in some other element of P_{S}(n, p) yields a Sperner subfamily S of P(n, p). By Fact 4 and Lemma 5 this subfamily is almost surely of cardinality at least

(1 + O (\frac{1}{n})) ∑_{|i|≤c\sqrt{n}} \binom{n}{⌊n/2⌋ − i}p − \frac{2^{n}}{\sqrt{n}}p ∼ (Φ(2c) − Φ(−2c))2^{n}p
∼ (Φ(2b) − Φ(−2b))2^{n}p.  (9)

This establishes the lower bound in Theorem 1. We now observe the following: if we now prove that (9) is also an asymptotic an upper bound for the width of P(n, p), then the family S proves Theorem 3, as S is as described in the statement of that theorem. Let us therefore prove that (9) is indeed an upper bound for the width of P(n, p). We now define c = c(n) by

p = n^{−b\sqrt{n}} = n^{−c\sqrt{n}} (\frac{9c}{e})^{2c\sqrt{n}} .

Again, c = b + o(1). By Lemmas 6 and 7, the width of P(n, p) is almost surely at most

∼ (Φ(2c) − Φ(−2c) + O (\frac{1}{n})) 2^{n}p ∼ (Φ(2b) − Φ(−2b)) 2^{n}p,

and hence (9) is an upper bound for the width of P(n, p), as required. □

3.3 Proofs of the lemmas

It now remains to prove Lemmas 5, 6, and 7.

Proof of Lemma 5. Denote by ∑_{k,ℓ} the sum over all pairs of integers k, ℓ with |k|, |ℓ| ≤ c\sqrt{n} and k + ℓ > 0. For Q ⊆ P(n), denote by X_{S}(Q) the number of edges in Q_{S}. Then, by (4) and the comment immediately after that estimate regarding the multinomial coefficient on the left-hand side of (4), we have

E[X_{S}(P(n, p))] ≍ ∑_{k,ℓ} \frac{2^{n}}{\sqrt{n(k + ℓ)}} (\frac{en}{2(k + ℓ)})^{k+ℓ} p^{2}

= O (2^{n}n^{−3/4} (\frac{e}{4c}\sqrt{n})^{2c\sqrt{n}} p^{2}) = O (2^{n}n^{−3/4}p) .

By Markov’s inequality, almost surely we have X_{S} ≤ 2^{n}p/\sqrt{n}, as required. □

Proof of Lemma 6. Fact 4 immediately gives that condition (i) holds almost surely. One may also easily check that condition (ii) is almost surely satisfied. To prove that condition (iii) holds almost surely, it is enough to show that, for any j with c\sqrt{n} ≤ |j| ≤ (log n)\sqrt{n}, the set-system P(n, p) is (c, ε, p, j)-uniform with probability at least, say, 1 − 1/n.

In what follows, we fix j with c\sqrt{n} ≤ |j| ≤ (log n)\sqrt{n} and bound from above the probability that P(n, p) is not (c, ε, p, j)-uniform. By symmetry, we may assume that j > 0 and thus i = i(j) in (8) is i = j − ⌊2c\sqrt{n}⌋. In particular, a set in P_{j}(n) contains \binom{n/2+j}{⌊2c\sqrt{n}⌋} elements from P_{i}(n).

For each x ∈ P_{j}(n), let Y_{x} be the random variable whose value is the the number of neighbours of x in P_{i}(n, p) if x ∈ P_{j}(n, p), and 0 otherwise. For all x ∈ P_{j}(n), the random variable Y_{x} conditioned on x ∈ P_{j}(n, p) is binomially distributed with parameters p and N = \binom{n/2+j}{⌊2c\sqrt{n}⌋}. Furthermore, by (5), if n is large enough,

Np ≥ \frac{1}{n} (\frac{en}{4c\sqrt{n}})^{2c\sqrt{n}} n^{−c\sqrt{n}} (\frac{9c}{e})^{2c\sqrt{n}} ≥ 2^{2c\sqrt{n}} = ε^{−4}.  (10)

By (7), if X is binomially distributed with parameters p and N,

P [|X − Np| ≥ εNp] ≤ 2 exp (−\frac{1}{3}ε^{2}Np) ≤ 2 exp (−\frac{1}{3}ε^{−2}) .

Denote by Z the number of elements in P_{j}(n, p) with degree larger than (1+ε)Np or smaller than (1 − ε)Np. By linearity of expectation,

E[Z] = O (\binom{n}{⌊n/2⌋ − j}p · exp (−\frac{1}{3}ε^{−2})) .

By Markov’s inequality and Fact 4, the probability that Z > exp (−ε^{−1}) |P_{j}(n, p)| is, very crudely, at most 1/2n. We have thus dealt with condition (b) and one part of condition (a).

As to the remaining part of condition (a), we notice that the degree of a vertex from P_{i}(n, p) in P_{i,j}(n, p) is binomially distributed with parameters p and

\binom{n/2 − i}{⌊2c\sqrt{n}⌋} ≤ \binom{n/2 + |j|}{⌊2c\sqrt{n}⌋} = N,

where we made use of the fact that |i| ≤ |j| = j. Hence the expected number of elements in P_{i}(n, p) with degree larger than (1 + ε)Np is, by (6), at most

2 exp (−\frac{1}{3}ε^{−2}) \binom{n}{⌊n/2⌋ + i}p ≤ 2 exp (−\frac{1}{3}ε^{−2}) \binom{n}{⌊n/2⌋ + j}pn^{10c},

provided n is large enough. Again, by Markov’s inequality and Fact 4, with probability at most 1/2n, more than exp (−ε^{−1}) |P_{j}(n, p)| elements in P_{i}(n, p) have degree larger than (1+ ε)Np in P_{i,j}(n, p), and the lemma follows. □

In the proof of Lemma 7 we need the following auxiliary result.

Lemma 8 Let 0 < c(n) = O(1) be given. Define p = n^{−c\sqrt{n}}(9c/e)^{2c\sqrt{n}}. Let 0 < ε ≤ 1/n be given, and let Q be (c, ε, p, j)-uniform for some j with c\sqrt{n} ≤ |j| ≤ (log n)\sqrt{n}. Define i = i(j) as in (8). Then there is a matching in Q_{i,j} that covers all but at most 4ε|Q_{j}| elements from Q_{j}, as long as n is sufficiently large.

Proof. Remove all vertices of Q_{i,j} of degree larger than (1 + ε)\binom{n/2+|j|}{⌊2c\sqrt{n}⌋}p. Call the resulting set-system R_{i,j}. By (a), the number of edges of Q_{i,j} incident to the vertices that have been removed may be bounded from above, very crudely, by

2 exp(−ε^{−1})|Q_{j}|\binom{n}{⌊2c\sqrt{n}⌋} ≤ 2 exp(−ε^{−1})|Q_{j}|n^{2c\sqrt{n}} ≤ ε|Q_{j}|p,

provided n is large enough.

Using condition (b), we see that the number of edges e(R_{i,j}) in R_{i,j} is at least

(1 − exp(−ε^{−1})) (1 − ε)|Q_{j}|\binom{n/2 + |j|}{⌊2c\sqrt{n}⌋}p − ε|Q_{j}|p ≥ (1 − 2ε)|Q_{j}|\binom{n/2 + |j|}{⌊2c\sqrt{n}⌋}p.

Moreover, R_{i,j} has maximum degree at most Δ(R_{i,j}) ≤ (1 + ε)\binom{n/2+|j|}{⌊2c\sqrt{n}⌋}p. Since the edgeset of the bipartite graph R_{i,j} may be partitioned into Δ(R_{i,j}) matchings, the graph R_{i,j} contains a matching covering at least

\frac{e(R_{i,j})}{Δ(R_{i,j})} ≥ \frac{1 − 2ε}{1 + ε}|Q_{j}| ≥ (1 − 4ε)|Q_{j}|

elements from Q_{j}, provided n is large enough. □

Proof of Lemma 7. For each j with c\sqrt{n} ≤ |j| ≤ (log n)\sqrt{n}, fix a matching in Q_{i,j} that covers all but ≤ 4ε|Q_{j}| elements from Q_{j}, as given by Lemma 8. Let R be the spanning subgraph of Q having as edges the union of all these matchings. A component in the graph R corresponds to a chain in Q, when Q is considered as a poset. Hence the width of Q is at most the number of components of R.

The graph R is a disjoint union of paths. Therefore the number of components of R is just the number of vertices in R minus the number of edges in R. By properties (i), (ii), and Lemma 8, the number of components of R is, therefore, almost surely at most

∑_{|j|≥(log n)\sqrt{n}} |Q_{j}| + ∑_{c\sqrt{n}≤|j|<(log n)\sqrt{n}} 4ε|Q_{j}| + ∑_{|j|<c\sqrt{n}} |Q_{j}|

≤ (\frac{2^{n}}{n} + 4 (1 + O (\frac{1}{n})) ε2^{n} + (1 + O (\frac{1}{n})) ∑_{|j|<c\sqrt{n}} \binom{n}{⌊n/2⌋ − j}) p

and the lemma follows as ε ≤ 1/n. □

4 Acknowledgements

We are grateful to an anonymous referee for his or her comments. We are also grateful to Professor Bruce Rothschild for his generous handling of this note.

References

[1] Ian Anderson, Combinatorics of finite sets, The Clarendon Press Oxford University Press, New York, 1987.

[2] Béla Bollobás, Random graphs, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1985.

[3] , Combinatorics, Cambridge University Press, Cambridge, 1986, Set systems, hypergraphs, families of vectors and combinatorial probability.

[4] Béla Bollobás and Graham Brightwell, Box-spaces and random partial orders, Trans. Amer. Math. Soc. 324 (1991), no. 1, 59–72.

[5] , The height of a random partial order: concentration of measure, Ann. Appl. Probab. 2 (1992), no. 4, 1009–1018.

[6] Béla Bollobás, Yoshiharu Kohayakawa, and Tomasz Łuczak, On the diameter and radius of random subgraphs of the cube, Random Structures Algorithms 5 (1994), no. 5, 627–648.

[7] Graham Brightwell, Models of random partial orders, Surveys in combinatorics, 1993 (Keele), Cambridge Univ. Press, Cambridge, 1993, pp. 53–83.

[8] Konrad Engel, Sperner theory, Cambridge University Press, Cambridge, 1997.

[9] James Allen Fill and Robin Pemantle, Percolation, first-passage percolation and covering times for Richardson’s model on the n-cube, Ann. Appl. Probab. 3 (1993), no. 2, 593–629.

[10] Svante Janson, Tomasz Łuczak, and Andrzej Ruciński, Random graphs, Wiley-Interscience, New York, 2000.

[11] Y. Kohayakawa, B. Kreuter, and D. Osthus, The length of random subsets of Boolean lattices, Random Structures Algorithms 16 (2000), no. 2, 177–194.

[12] B. Kreuter, Small sublattices in random subsets of Boolean lattices, Random Structures Algorithms 13 (1998), no. 3-4, 383–407.

[13] D. Lubell, A short proof of Sperner’s lemma, J. Combinatorial Theory 1 (1966), 299.

[14] Deryk Osthus, Maximum antichains in random subsets of a finite set, J. Combin. Theory Ser. A 90 (2000), no. 2, 336–346.

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

[16] Stanislaw M. Ulam, Monte Carlo calculations in problems of mathematical physics, Modern mathematics for the engineer: Second series, McGraw-Hill, New York, 1961, pp. 261–281.