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–900 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 Results

In this note we investigate random non-uniform hypergraphs, i.e., random families of subsets of an n-element set, or, equivalently, a random subset of the Boolean lattice P(n) = 2^{[n]}, where, as usual, [n] = {1, …, n}. Such random hypergraphs were probably first investigated by Rényi [3] who, answering a question of Erdős, determined the minimum cardinality of a family of random subsets of [n] that guarantees, with high probability, two distinct sets A and B with A ⊂ B. A family containing no such pair of sets, i.e., inducing no relation in the Boolean lattice, is usually called a Sperner family. The size of the largest Sperner family in a set-system Q ⊂ P(n) is simply the width of Q when Q is viewed as a poset, and we shall denote it here by α(Q). For any given 0 < p = p(n) < 1, let the random set-system P(n, p) be defined by picking each element of P(n) independently at random with probability p.

∗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).

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 the sequel, 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).

In fact, it will follow from the proof of Theorem 1 that the following structural result holds.

Theorem 2 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.

An immediate corollary to the results above is that, for ε > 0 and p = n^{−ε\sqrt{n}}, we almost surely have

\frac{α(P(n, p))}{|P(n, p)|} ∼ ε (1 + O (ε^{2})) \sqrt{\frac{8}{π}} .

The proof of Theorem 1 is given in the next section. For results concerning the length of P(n, p), i.e., the cardinality of a longest chain, the reader is referred to [1]. The threshold function for small sublattices in P(n, p) are investigated in [2], which may be thought of as a modern sequel to Rényi’s pioneering work [3].

2 Proofs

2.1 Proof of Theorem 1

Before giving the proof of Theorem 1, 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−k−ℓ}}{\sqrt{n}} × \frac{n^{k+ℓ}}{(k + ℓ)!}
≍ \frac{2^{n}}{\sqrt{n(k + ℓ)}} (\frac{en}{2(k + ℓ)})^{k+ℓ} .  (1)

For later reference, notice that the multinomial coefficient on the left-hand side of (1) 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} .  (2)

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}.  (3)

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) .  (4)

This implies the following very rough bound on |P_{i}(n, p)|. (*) 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.

Let now 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}⌋,  (5)

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) is 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 Theorem 1.

Lemma 3 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 4 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 5 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.

Before proving Lemmas 3, 4, and 5 we deduce Theorem 1 from those lemmas.

Proof of Theorem 1. 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 3. 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 of P(n, p). By Lemma 3 and assertion (*) 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.

This establishes the lower bound in Theorem 1. To prove the upper bound, 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 4 and 5, 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 the theorem follows. □

2.2 Proofs of the lemmas

It now remains to prove Lemmas 3, 4, and 5.

Proof of Lemma 3. 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 (1), 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 4. Assertion (*) 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.

Thus, in the sequel, 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 (5) 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 (2), 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}.  (6)

By (4), 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 assertion (*), 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 (3), 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 assertion (*), 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 5 we need the following auxiliary result.

Lemma 6 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 (5). 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 of Lemma 6. 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 5. 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 6. 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 6, 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. □

3 Concluding remarks

It would be interesting to investigate α(P(n, p)) for the range of p in which α(P(n, p)) is comparable to

|P_{0}(n, p)| = |P(n, p) ∩ \binom{[n]}{⌊n/2⌋}| .

In particular, one may ask what the threshold functions for the following properties are:

(1) α(P(n, p)) = |P_{0}(n, p)|,

(2) α(P(n, p)) ∼ |P_{0}(n, p)|.

Many similar questions remain open.

References

[1] Y. Kohayakawa, B. Kreuter, and D. Osthus. The length of random subsets of Boolean lattices. In preparation, 1998.

[2] B. Kreuter. Small sublattices in random subsets of Boolean lattices. Submitted, 1997.

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