LINEAR EXTENSIONS OF A RANDOM PARTIAL ORDER

Annals of Applied Probability 4 (1994), 108–123

Noga Alon, Béla Bollobás, Graham Brightwell and Svante Janson

Tel Aviv University, Cambridge University, London School of Economics and Uppsala University

Abstract. We study asymptotics of the number of linear extensions of the random G_{n,p} partial order, where p is fixed and n → ∞. In particular, it is shown that the distribution is asymptotically log-normal.

1. Introduction and results

One of the standard models for a random partial order is the G_{n,p} order, defined as follows. Let < denote the natural order on the vertex set [n] = {1, …, n}. A graph G on [n] induces a partial order on that vertex set, viz. the transitive closure of the relation {i < j and there is an edge ij}. I.e., if each edge ij in G, with i < j, is directed from i to j, i ≺ j iff there exists a directed path from i to j in G. The random G_{n,p} order is obtained by applying this procedure to the random graph G_{n,p}. Here, as throughout, we let G_{n,p} denote a random graph in G(n, p), i.e., a graph on [n] such that each possible edge appears with probability p, independently of all other edges. We assume throughout that 0 < p < 1 and set q = 1 − p.

This G_{n,p} order has previously been studied by Barak and Erdős [3], who investigated the width of the partial order, and by Albert and Frieze [1], who studied its height and set-up number. Our purpose in this paper is to investigate another fundamental parameter of partial orders, namely the number of linear extensions. Recall that a linear extension of a partial order (X, <) is a total order ≺ on the same set X such that x ≺ y whenever x < y.

We define a linear extension of a graph G on [n] to be a linear extension of the corresponding partial order. We denote by N(G) the number of linear extensions of G. The purpose of the present paper is to study the number N(G_{n,p}) of linear orders that extend the G_{n,p} partial order; we also use N_{n,p} for this random variable. Obviously, 1 ≤ N_{n,p} ≤ n! .

There is a simple formula for the expectation of N_{n,p}. We define

κ(p) = ∏_{k=1}^{∞}(1 − q^{k}).  (1.1)

Typeset by AMS-TEX

Theorem 1. With notation as above,

E N_{n,p} = ∏_{k=1}^{n} \frac{1 − q^{k}}{1 − q}  (1.2)

Hence, if p is fixed, 0 < p < 1,

E N_{n,p} ∼ κ(p)(\frac{1}{p})^{n}, as n → ∞.  (1.3)

The asymptotic distribution of N_{n,p} for fixed p turns out to be log-normal.

Theorem 2. Let p be fixed and n → ∞. For some μ = μ(p) > 0 and σ^{2} = σ^{2}(p) > 0,

\frac{log(N_{n,p}) − μn}{\sqrt{n}} ⟶^{d} N(0, σ^{2}),  (1.4)

with convergence of all moments. In particular

\frac{log(N_{n,p}) − E log(N_{n,p})}{(Var log(N_{n,p}))^{1/2}} ⟶^{d} N(0, 1).  (1.5)

We do not have an explicit expression for μ(p) and σ^{2}(p), but we can give simple bounds for μ(p).

Theorem 3. Let Y have the shifted geometric distribution P (Y = k) = pq^{k−1}, k ≥ 1. Then

E log(Y) = ∑_{1}^{∞} log(k)pq^{k−1} ≤ μ(p) ≤ (1 − κ(p)) log \frac{1/p − κ(p)}{1 − κ(p)} < log \frac{1}{p} = log(E Y). (1.6)

For p = 1/2 we obtain from (1.6) that 0.507 < μ < 0.625 and 1.66 < e^{μ} < 1.87.

It may seem surprising that μ < log \frac{1}{p}, since Theorem 2 says that N_{n,p} is concentrated about (e^{μ})^{n} (more precisely, N_{n,p} = exp(μn + O_{p}(\sqrt{n})), which thus is far less than the mean which is ≍ (\frac{1}{p})^{n}. Some thought, however, shows that Theorems 1 and 2 actually force e^{μ} < \frac{1}{p}, because (1.4) implies that if n is sufficiently large, P(N_{n,p} > exp(μn+σ\sqrt{n})) > 0.1, and thus (\frac{1}{p})^{n} ≥ E N_{n,p} > 0.1e^{σ\sqrt{n}}(e^{μ})^{n} > (e^{μ})^{n}.

The same phenomenon, that the variable is concentrated far below its mean, also occurs in the case of a product X_{n} = ∏_{1}^{n} Y_{k} of i.i.d. positive variables, where (assuming suitable moment conditions) log X_{n} is asymptotically normal and X_{n} is concentrated about (e^{E log Y_{1}})^{n}, which (by Jensen’s inequality) is less than E X_{n} = (E Y_{1})^{n}. The variable N_{n,p} is more complicated, but, as we will see in the proof, it has a somewhat similar structure.

We shall concentrate on the case where p is a constant, independent of n. In this case, we may assume that a random graph and the corresponding random partial order are defined as above on all of N, or Z, and define G_{n,p} as the restriction G_{N,p}|_{[n]}. Let N(i, j) be the number of linear extensions of the restriction of the random partial order to (i, j], so that N_{n,p} = N(0, n). Then {N(i, j)} is supermultiplicative,

N(i, k) ≥ N(i, j)N(j, k), i > j > k,  (1.7)

and Kingman’s subadditive ergodic theorem [10] applies to − log(N(i, k)). Thus we have that \frac{1}{n} log(N_{n,p}) converges a.s. to a random variable ξ a.s., which is easily shown to be constant; in fact, Theorem 2 implies ξ = μ a.s. This proves the following strong limit theorem.

Theorem 4. If p is fixed, N_{n,p}^{1/n} → e^{μ(p)} a.s. as n → ∞. □

We can sharpen Theorem 4 as follows.

Theorem 5. Let p be a constant with 0 < p < 1. For almost every G_{N,p}, there is an n_{0}(G, p) such that, for every n ≥ n_{0},

|N_{n,p}^{1/n} − e^{μ(p)}| ≤ \frac{15e^{μ}(log n)^{3/2}}{n^{1/2}p^{2}} .

Our final result shows that log N(G) is sharply concentrated around its mean.

Theorem 6. Suppose that 0 < λ ≤ n^{1/4} and that q ≥ 1/e. Then

P (| log N_{n,p} − nμ(p)| > \frac{λ\sqrt{n} log n}{p^{2}}) ≤ 3 exp (−\frac{λ^{2}}{6400}) .

The assumption that q ≥ 1/e here is purely for convenience: if the assumption is dropped, a similar result with different constants can be obtained. Results concerning deviations larger than those given by setting λ = n^{1/4} in Theorem 6 can also be obtained, but the lemmas in the proof below are a little simpler to state if this restriction is made. In Theorem 6, one should think of p as being constant, but no restriction is actually needed on how small p = p(n) can be. However, since log N_{n,p} < n log n for all G, the result is only meaningful if p has order larger than n^{−1/4}.

Acknowledgement. These results were obtained during the Durham symposium on probabilistic methods in combinatorics 1991, and were inspired by similar results by Graham Brightwell [6] for another model of random partial orders. We thank all the participants that entered into helpful discussions, in particular Tomasz Łuczak, who raised the problem, Joel Spencer and Herbert Wilf.

2. Proof of Theorem 1.

There is a 1−1 correspondence between linear orders ≺ on {1, …, n} and permutations π of {1, …, n} given by

i ≺ j ⟺ π(i) < π(j)  (2.1)

(where <, as above, denotes the natural order). It is easily seen that ≺ extends the G_{n,p} partial order if and only if π(i) < π(j) for all i, j, i < j, connected by an edge in G_{n,p}, or, equivalently,

there is no edge ij in G_{n,p} with i < j and π(i) > π(j).  (2.2)

Consequently,

E N_{n,p} = ∑_{π} P ((2.2) holds) = ∑_{π} q^{#{inversions in π}},  (2.3)

and (1.2) reduces to a well-known formula for the generating function of the number of inversions in permutations.

For later use, we also give a direct proof as follows.

We consider again the random partial order as defined on N, and let N_{n} = N(0, n), for simplicity omitting the subscript p. Let F_{n} be the σ -field generated by the edge indicators I(ij is an edge), 1 ≤ i < j ≤ n; thus N_{n} is F_{n}-measurable. Consider a particular linear order ≺ on [n − 1] = {1, …, n − 1} that extends the partial order there, and order [n − 1] according to this order as i_{1} ≻ i_{2} ≻ ⋯ ≻ i_{n−1}. This linear order has n extensions to [n], obtained by choosing k ∈ {1, …, n} and then inserting n between i_{k−1} and i_{k} (n ≻ i_{1} if k = 1, and i_{n−1} ≻ n if k = n). The linear order on [n] constructed in this way extends the partial order on [n] if and only if there are no edges i_{j}n with j < k. Consequently, the number of extensions of ≺ to [n] that are extensions of the partial order on [n] equals n ∧ min{j : i_{j}n is an edge}. Given F_{n−1}, this is a random variable with the distribution of Y ∧ n, where Y is the geometric variable in Theorem 3. Hence, N_{n} can be written as a sum

N_{n} = ∑_{1}^{N_{n−1}} Y_{i}^{(n)},  (2.4)

where Y_{i}^{(n)}, given F_{n−1}, are (dependent) random variables with the same distribution as Y ∧ n. Consequently

E(N_{n} | F_{n−1}) = E(Y ∧ n)N_{n−1}

and

E N_{n} = E(Y ∧ n) E N_{n−1} = \frac{1 − q^{n}}{1 − q} E N_{n−1},

which gives (1.2) by induction.

3. Proof of Theorem 2.

Suppose that, for a given realization of the random graph G_{n,p}, (or G_{N,p}), there is a vertex i, 1 ≤ i ≤ n, such that every other vertex is connected to i by a directed path (directed either towards or from i). Then, in the G_{n,p} partial order, every other element is comparable with vertex i. Thus i is a fixed point of every permutation that corresponds to a linear extension of the G_{n,p} order, and the number N_{n,p} = N(0, n) of such orders factorizes as the product N(0, i)N(i, n), i.e., equality holds in (1.7) in this case.

We call such a vertex a post, and obtain, letting i_{1}, i_{2}, …, i_{m} be the successive posts in {1, …, n}, a decomposition of N_{n,p} as a product of N(i_{j}, i_{j+1}) (with i_{0} = 1 and i_{m+1} = n). The number of factors is random, and we shall show later that the different factors are independent. However, before we can make such a statement, it is necessary to show that, almost surely, there do exist posts in the G_{N,p} order, indeed infinitely many of them.

Lemma 3.1. For every 0 < p < 1 there is a constant C = C(p) > 1 such that, for every sufficiently large k, the probability that none of the k elements 2k, 4k, 6k, … 2k^{2} are posts in G_{Z,p} is at most C^{−k}.

Proof. Observe first that, for j ≥ 1,

P(j comparable with 0 | 1, …, j − 1 comparable with 0) = 1 − q^{j},

so the probability that 0 is comparable with all elements 1, 2, … is

∏_{j=1}^{∞}(1 − q^{j}) = κ(p).

The same argument holds independently for the negative elements, so the probability that 0 (or, by symmetry, any other element) is a post is κ(p)^{2}.

The event that none of the k elements 2k, 4k, 6k, … 2k^{2} are posts in G_{Z,p} is equivalent to the event that, for each of the elements 2jk (j = 1, …, k), there is an element n_{j} of Z incomparable with 2jk in the G_{Z,p} partial order. We consider two events whose union contains this event, and show that each of the two events has small probability.

(i) For each j, there is an element n_{j} in the interval [(2j − 1)k, (2j + 1)k] incomparable with 2jk in the partial order.

This event is the conjunction of k independent events, since the existence of a suitable element n_{j} depends only on those edges with both endpoints in the interval [(2j−1)k, (2j+ 1)k]. Each of these events has probability at most the probability that 2jk is not a post, which is 1 − κ(p)^{2}. Hence the probability of this case is at most (1 − κ(p)^{2})^{k}. (ii) For some j, every element in the interval [(2j − 1)k, (2j + 1)k] is comparable with 2jk in the partial order, but there is an element n_{j} outside this interval incomparable with 2jk.

The probability of this event is at most 2k times the probability that 0 is comparable with every element 1, 2, …, k, but is incomparable with some element beyond k. This probability is at most

∑_{j=k}^{∞} P(j + 1 incomparable with 0 | 1, …, j comparable with 0) = ∑_{j=k}^{∞} q^{j+1} = \frac{q^{k+1}}{p} .

Combining the probabilities of events (i) and (ii), we see that

P(none of 2k, 4k, … 2k^{2} is a post) ≤ (1 − κ(p)^{2})^{k} + 2kq^{k+1}/p.

Taking C(p) to be any constant such that C^{−1} > max{1 − κ(p)^{2}, q}, the result follows. □

Equipped with this lemma, we are now in a position to prove a fair amount about the sequence of posts and the structure of the random partial order.

Lemma 3.2. The posts form a.s. a two-way infinite sequence, and the indicator variables I(i is a post), −∞ < i < ∞, form a stationary sequence.

Proof. It is obvious that the sequence I(i is a post) is stationary. Consequently, the events {i is the first post} have the same probability; since these events are disjoint, the probability has to be 0. Hence the sequence of posts has a.s. no first element. Similarly, there is a.s. no last element, so the sequence of posts is either empty or two-way infinite.

But Lemma 3.1 tells us that the probability that there is no post is less than C^{−k} for every k, and hence is 0. Therefore the sequence of posts is a.s. two-way infinite. □

Let …, U_{−1}, U_{0}, U_{1}, … denote the random variables giving the positions of the infinite sequence of posts, with (to be definite) U_{0} being the first post at or to the right of 0. We call the posets induced on the intervals [U_{j}, U_{j+1}] the segments of the partial order. Note that segments overlap at the posts, but that each edge is in at most one segment.

Lemma 3.3. The various distances U_{j+1} − U_{j}, j ≥ 0, are mutually independent, identically distributed, random variables. In particular the events {m is a post} are recurrent.

Given the set of posts, the distribution of the edges is as follows: The set of edges inside each segment has a distribution depending only on the length of the segment (ignoring an obvious translation); the sets of edges inside different segments are independent; the edges that do not lie in a segment occur with probability p, independently of each other and of the edges inside segments.

Proof. We prove that the distances between successive posts are mutually independent. By translation invariance, it suffices to prove that, if E is any event depending only on the set of edges one of whose end-points is to the left of 0, then

P(m is the first post to the right of 0 | E and 0 is a post) = P(m is the first post to the right of 0 | 0 is a post), (3.1) since this implies that the distribution of U_{1} (= U_{1} −U_{0}) is independent of the distribution of the posts to the left of U_{0} = 0. But (3.1) holds, since an element m to the right of the post at 0 is itself a post iff there is a directed path from m to every non-negative element of Z (since other elements then have a directed path to m via 0), and this last event is independent of E.

The remaining assertions are immediate. □

Remark 3.1. Note that, as for all stationary recurrent sequences, the distribution of U_{0} − U_{−1}, the length of the segment containing 0 and −1, differs from the distribution of U_{1}−U_{0} (“the waiting time paradox”). See (3.3) for the precise relation.

Lemma 3.3 implies that, if (X, <) is a finite poset with a minimal and a maximal element, but no other elements comparable to every element of X, then the probability that the segment between U_{j} and U_{j+1} is isomorphic to (X, <) is independent of the nature of any other segment. Hence we can consider the random G_{n,p} partial order as built up by successively choosing segments, independently, from some fixed distribution, and amalgamating them at the successive posts. (This picture is in fact slightly distorted by edge effects at both ends.)

Before completing the proof of Theorem 2, we need a moment condition on the lengths of the segments.

Lemma 3.4. Let L be the random variable describing the length of the segments:

P(L = l) = P(U_{1} = l | U_{0} = 0), l ≥ 1.

Then E L^{r} < ∞ for every r < ∞.

Similarly, if L̃ = U_{0} − U_{−1} is the length of the segment containing 0 and −1, E L̃^{r} < ∞ for every r < ∞.

Proof. Lemma 3.1 gives us that, for some C = C(p) > 1 and sufficiently large k,

P(none of 2k, 4k, …, 2k^{2} is a post | 0 is a post)

≤ P(none of 2k, 4k, …, 2k^{2} is a post)/ P(0 is a post) ≤ C^{−k}/κ(p)^{2}.

Hence the probability that L is greater than 2k^{2} is at most C_{1}^{−k} for some C_{1}(p) > 1 and sufficiently large k, which yields, for some C_{2}(p) > 1,

P (L > l) ≤ C_{2}^{−\sqrt{l}},  (3.2)

and the claim follows.

For L̃ we observe that

P(L̃ = l) = ∑_{1}^{l} P(−j is a post and l − j is the next)

= l P(0 is a post and l is the next)

= lκ(p)^{2} P(L = l).  (3.3)

Hence also E L̃^{r} < ∞. □

Remark 3.2. Summing (3.3) over l, we obtain E L = κ(p)^{−2}.

Remark 3.3. Using a different argument, we can improve (3.2) to show that

P(L > l) ≤ c_{1}e^{−c_{2}l/ log l},

but we do not know whether this can be improved to an exponential bound.

We may now complete the proof of Theorem 2. Let V_{i} = log(N(0, U_{i})), i ≥ 0. Further, let W_{0} = U_{0}, Z_{0} = V_{0}, and, for i ≥ 1, W_{i} = U_{i} − U_{i−1}, Z_{i} = V_{i} − V_{i−1} = log(N(U_{i−1}, U_{i})), where the last equality follows because U_{i−1} is a post. It follows from Lemma 3.3 that the two-dimensional random variables (W_{i}, Z_{i}), i ≥ 0, are independent, and that they have the same distribution for i ≥ 1. By Lemma 3.4, for any r < ∞, EW_{i}^{r} = EL^{r} < ∞ for i ≥ 1, and EW_{0}^{r} ≤ EL̃^{r} < ∞. Furthermore, 0 ≤ Z_{i} ≤ log(W_{i}!) ≤ W_{i} log(W_{i}), so EZ_{i}^{r} < ∞, r < ∞, i ≥ 0.

We also observe that the events {W_{i} = 3, Z_{i} = log 1} and {W_{i} = 3, Z_{i} = log 2} both have positive probability, so W_{i} and Z_{i} are not proportional and γ^{2} = Var(E(W_{1})Z_{1} − E(Z_{1})W_{1}) > 0.

Define τ(n) = min{i : U_{i} > n}, the index of the first post after n. We have placed ourselves in the setting of Gut [8, Section IV.2], except for the minor complication that here we have variables (W_{0}, Z_{0}) with a distribution different from (W_{i}, Z_{i}), i ≥ 1. Theorem IV.2.3 in [8] is easily generalized to this case by standard arguments which we omit; the theorem then yields

\frac{V_{τ(n)} − μn}{\sqrt{n}} ⟶^{d} N(0, σ^{2}), as n → ∞,  (3.4)

with convergence of all moments, where μ = E(Z_{1})/ E(W_{1}) and σ^{2} = γ^{2}(E W_{1})^{−3} > 0. Since V_{τ(n)−1} ≤ log(N_{n,p}) = log(N(0, n)) ≤ V_{τ(n)}, | log(N_{n,p}) − V_{τ(n)}| ≤ Z_{τ(n)} ≤

L̃_{n} log L̃_{n}, where L̃_{n} is the length of the segment containing n and n + 1. Since L̃_{n} =^{d} L̃ for all n, Lemma 3.4 and Cramér’s theorem implies that we can replace V_{τ(n)} by log(N_{n,p}) in (3.4), and the theorem follows. □

Remark 3.4. Say that a parameter f of partial orders is additive if whenever the partially ordered set P is the linear sum of P_{1} and P_{2}, i.e. P is obtained by putting all of P_{2} above P_{1}, then f(P) = f(P_{1})+f(P_{2}). Note that the logarithm of the number of linear extensions is an example of an additive parameter. Our proof of Theorem 2 shows also that other additive parameters of G_{n,p}, for example the height and the number of incomparable pairs, have asymptotic normal distributions, see [7, Theorem 8].

4. Proof of Theorem 3.

We continue the argument in Section 2, introducing Q_{n} = \frac{N_{n}}{N_{n−1}} , n ≥ 1, (with N_{0} = 1). If m is the last post before n, Q_{n} = N(0, n)/N(0, n − 1) depends only on the set of edges {ij : m ≤ i < j ≤ n}, and it follows easily that Q_{n} converges in distribution to some variable Q_{∞}. Using (2.4) and Jensen’s (or Cauchy’s) inequality, we obtain

Q_{n}^{2} ≤ \frac{1}{N_{n−1}} ∑_{1}^{N_{n−1}}(Y_{i}^{(n)})^{2},  (4.1)

and thus

E Q_{n}^{2} ≤ E(Y ∧ n)^{2} ≤ E Y^{2} < ∞,

which implies that {Q_{n}} and {log Q_{n}} are uniformly integrable and thus

E Q_{∞} = lim_{n→∞} E Q_{n} = lim_{n→∞} E(Y ∧ n) = E Y = \frac{1}{p},  (4.2)
E log(N_{n}) − E log(N_{n−1}) = E log(Q_{n}) → E log(Q_{∞}),  (4.3)

which yields

μ = lim_{n→∞} \frac{1}{n} E log(N_{n}) = E log(Q_{∞}).  (4.4)

By (2.4) and Jensen’s inequality again,

log(Q_{n}) ≥ \frac{1}{N_{n−1}} ∑_{1}^{N_{n−1}} log(Y_{i}^{(n)}),  (4.5)

and thus E log(Q_{n}|F_{n−1}) ≥ E log(Y ∧ n), which yields

μ = E log(Q_{∞}) ≥ E log(Y).  (4.6)

Finally we observe that Q_{n} = 1 if and only if every i with 1 ≤ i < n may be connected to n by a directed path (cf. the definition of posts in Section 3). Hence

P(Q_{∞} = 1) = lim_{n→∞} P(Q_{n} = 1) = lim_{n→∞} ∏_{1}^{n−1}(1 − q^{n−i}) = κ(p),  (4.7)

and, by Jensen’s inequality,

E log Q_{∞} = P(Q_{∞} ≠ 1) E(log Q_{∞} | Q_{∞} ≠ 1)
≤ P(Q_{∞} ≠ 1) log E(Q_{∞} | Q_{∞} ≠ 1)
= (1 − κ(p)) log \frac{E Q_{∞} − κ(p)}{1 − κ(p)}.  (4.8)

The theorem follows by (4.4), (4.6), (4.8), and the concavity of the logarithm.

5. Proof of Theorems 5 and 6.

Our proofs of these results are based on the following theorem, which in turn is based upon martingale inequalities due to Azuma [2] and Hoeffding [9]. For further details, the reader is referred to the articles by Bollobás [4], [5] or McDiarmid [11].

Theorem A. Suppose that H_{1} ∪ H_{2} ∪ ⋯ ∪ H_{m} is a partition of [n]^{(2)} into m parts. Let Z(G) be a random variable depending on the random graph G = G_{n,p} with vertex set [n], such that |Z(G) − Z(G′)| ≤ h whenever G and G′ differ only on one of the H_{i}. Then, for any real a, we have

P (|Z(G_{n,p}) − EZ(G_{n,p})| > a) ≤ 2 exp(−a^{2}/2mh^{2}).  □

Ideally, we would like to apply Theorem A to the random variable log N(G), with m = n and H_{j} being the set of pairs (i, j) with i < j. The condition |Z(G) − Z(G′)| ≤ h then amounts to saying that log N(G) does not change much when the edges “downward” from one vertex are changed. Unfortunately this is not quite true: in the worst case the addition of the single edge between the two middle vertices can change N(G) from \binom{n}{n/2} to 1. Our solution, as is often the case in applications of Theorem A, is to consider a slightly modified random variable in place of log N(G).

For G a graph with vertex set [n], and w a positive real number, let N^{∗}(G, w) be the number of linear extensions ≺ of G in which j ≺ k whenever j < k − 2w. In other words, N^{∗}(G, w) is the number of linear extensions of the the graph G^{∗} obtained from G by adding an edge between vertices j and k whenever j < k − 2w.

We now apply Theorem A to Z(G) = log N^{∗}(G, w).

Lemma 5.1. Let w and a be positive real numbers. Then

P (| log N^{∗}(G_{n,p}, w) − E log N^{∗}(G_{n,p}, w)| > a) ≤ 2 exp (−\frac{a^{2}}{16nw^{2}} ) .

Proof. As indicated, we apply Theorem A with m = n, Z(G) = log N^{∗}(G, w), and H_{j} = {(i, j) : i < j}, for j = 1, …, n.

We wish to bound |Z(G) − Z(G′)|, under the assumption that G and G′ differ only on the pairs in H_{j}. Clearly we may assume that G contains none of the edges from j to the vertices in {j − ⌊2w⌋, … j − 1}, whilst G′ contains all of them. Then, given a linear extension ≺ of G^{∗}, we can convert it to a linear extension ≺′ of (G′)^{∗} by putting all the vertices 1, …, j − 1 below all the vertices j, … n, with the ordering inside each of the two subsets {1, …, j − 1} and {j, …, n} the same in ≺′ as in ≺. Under this map, at most \binom{2⌊2w⌋}{⌊2w⌋} linear extensions ≺ of G^{∗} are mapped onto any linear extension ≺′ of (G′)^{∗}, since ≺ can be determined from ≺′ by specifying the relative positions of the vertices j − ⌊2w⌋, …, j + ⌊2w⌋ − 1. Hence N^{∗}(G, w) ≤ N^{∗}(G′, w)\binom{2⌊2w⌋}{⌊2w⌋}, and so

Z(G) − Z(G′) ≤ log \binom{2⌊2w⌋}{⌊2w⌋} ≤ 4w log 2 < 2\sqrt{2}w.

The result now follows from Theorem A. □

In order to make use of Lemma 5.1, we need to show that, for an appropriate choice of w = w(n, p), the random variable log N^{∗}(G, w) is not too different from log N(G). Let us first make the following easy observation.

Lemma 5.2. Let p be any constant. Then there is a constant C(p) such that, for all n,

P (N(G_{n,p}) ≠ N^{∗}(G_{n,p}, w)) ≤ n^{−2},

where w = ⌈C(p) + 3 log n/2p^{2}⌉.

Proof. If j and k are any vertices of G, the probability that j and k are not related in the induced partial order is at most (1 − p^{2})^{|j−k|−1}, since that is the probability that no vertex between j and k is adjacent to both. Hence the probability that some pair (j, k) with k − j > 2w is not related is at most

n ∑_{i=2w}^{∞}(1 − p^{2})^{i} = \frac{n}{p^{2}} (1 − p^{2})^{2w}

≤ \frac{n}{p^{2}} (1 − p^{2})^{2C(p)} [(1 − p^{2})^{1/p^{2}}]^{3 log n}

≤ \frac{n}{p^{2}} (1 − p^{2})^{2C(p)}n^{−3}.

For a suitable value of C(p), this is the required result. □

In order to prove Theorem 6, we shall need some results which are rather stronger than Lemma 5.2, to get the probability of failure down to the required level. However, Lemma 5.2 is already sufficient for us to prove Theorem 5.

Proof of Theorem 5. For p fixed, take w as in Lemma 5.2, and n large enough so that w ≤ 2 log n/p^{2}. Now set a = 12n^{1/2}(log n)^{3/2}p^{−2}. Lemma 5.1 tells us that

P (| log N^{∗}(G_{n,p}, w) − E log N^{∗}(G_{n,p}, w)| > a) ≤ 2n^{−9/4}

for every such n, and Lemma 5.2 gives

P (N(G_{n,p}) ≠ N^{∗}(G_{n,p}, w)) ≤ n^{−2}.

Since log N(G) ≤ n log n for every G, this implies that

E(log N(G_{n,p}) − log N^{∗}(G_{n,p}, w)) ≤ log n/n.

Combining these, we see that

P (| log N(G_{n,p}) − E log N(G_{n,p})| > 13n^{1/2}(log n)^{3/2}p^{−2}) ≤ 2n^{−2},

for n sufficiently large.

If we now consider the infinite random graph G_{N,p}, the Borel–Cantelli lemma implies that, almost surely, there is an n_{1} = n_{1}(G, p) such that

| log N(G_{n,p}) − E log N(G_{n,p})| ≤ 13n^{1/2}(log n)^{3/2}p^{−2}

for all n ≥ n_{1}.

To complete the proof, we require some bounds on the convergence of \frac{1}{n}E log N(G_{n,p}) to its limit μ(p). We obtain such bounds by relating N_{2n,p} to N_{n,p}.

For G a graph with vertex set [2n], let G_{1} be the graph G|_{[n]} and G_{2} be the graph G|_{{n+1,...,2n}}. Also let A(G) denote the average, over all linear extensions ≺_{1} and ≺_{2} of G_{1} and G_{2} respectively, of the number of linear extensions of G extending both ≺_{1} and ≺_{2}. Then we have

N(G) = ∑_{≺_{1}} ∑_{≺_{2}}(number of linear extensions of G extending both ≺_{1} and ≺_{2})
= N(G_{1})N(G_{2})A(G)

and

E log N_{2n,p} = 2E log N_{n,p} + E log A(G_{n,p})
≤ 2E log N_{n,p} + log(EA(G_{n,p})).

The expectation of A(G_{n,p}) is just the expected number of linear extensions of G extending any pair ≺_{1} and ≺_{2} of linear extensions of the two halves. It was observed in [6] that this expectation increases to ∏_{i=1}^{∞}(1 − q^{i})^{−1} = 1/κ(p), as n → ∞; moreover A(G) ≥ 1.

This means that μ_{n} = \frac{1}{n}E log N_{n,p} satisfies:

\begin{aligned}2nμ_{n} & ≤ 2nμ_{2n} ≤ 2nμ_{n} + log(1/κ(p)) \\ μ_{n} & ≤ μ_{2n} ≤ μ_{n} + \frac{log(1/κ(p))}{2n}. \end{aligned}

Hence, summing terms μ_{2^{k}n} − μ_{2^{k−1}n}, we have

μ(p) ≥ μ_{n} ≥ μ(p) − \frac{1}{n} log(1/κ(p)).  (5.1)

We now have that, for almost every G_{N,p}, there is an n_{2}(G, p) such that

| log N(G_{n,p}) − nμ(p)| ≤ 14n^{1/2}(log n)^{3/2}p^{−2}

for all n ≥ n_{2}. This implies the result. □

We now turn our attention to completing the proof of Theorem 6. Recall that we wish to relate N(G) to N^{∗}(G, w), for suitable w, and that we require our estimates to be correct with extremely high probability.

From now on, we set v = ⌈4 log n/ log(1/q)⌉ and w = 4v/p.

Let P and Q be the following properties of graphs with vertex set [n] (n ≥ 2). P: There is a set S of order at most n^{1/2}/ log n such that any two disjoint sets of vertices of size v, not intersecting S, have an edge between them. Q: There is a set T of order at most 2n^{1/2}/ log n such that (i) for every vertex j of G, not in T, with j ≤ n − w, there are at least 2v neighbours of j among the vertices j + 1, …, j + ⌈w⌉, and (ii) for every vertex j of G, not in T, with j > w, there are at least 2v neighbours of j among the vertices j − ⌈w⌉, …, j − 1.

Lemma 5.3. (i) The probability that G_{n,p} fails to have property P is at most exp(−n^{1/2}). (ii) The probability that G_{n,p} fails to have property Q is at most 2 exp(−n^{1/2}).

Proof. (i). We construct S by the following procedure. If the graph contains disjoint sets A_{1}, A_{2}, both of size v, without an edge between them, remove them from the graph, add the vertices in A_{1} ∪ A_{2} to S, and repeat. If the procedure halts after at most n^{1/2}/2v log n steps, then the original graph clearly has property P. If not, then the graph contains at least n^{1/2}/2v log n vertex disjoint pairs of sets of size v, with no edges between any of the pairs of sets. The probability of this is at most

\binom{n}{v}^{n^{1/2}/v log n} (q^{v^{2}})^{n^{1/2}/2v log n} ≤ exp [\frac{n^{1/2}}{2 log n} (2 log n − v log 1/q)]
≤ exp (−n^{1/2}) ,

as desired.

(ii). Let us take any vertex j ≤ n − w, and estimate the probability that it fails to have at least 2v neighbours in {j + 1, …, j + ⌈w⌉}. Applying the Chernoff bound P (Bi(N, p) ≤ Np(1 − ϵ)) ≤ exp(−ϵ^{2}pN/2), we see that this is at most e^{−pw/8}, since 2v ≤ p⌈w⌉/2. Since log(1/q) ≤ 1, we have w ≥ 16 log n/p, and so the probability that j is “bad” is at most n^{−2}. Hence the probability that more than n^{1/2}/ log n vertices fail to have 2v neighbours as required is at most

\binom{n}{⌈n^{1/2}/ log n⌉}(n^{−2})^{⌈n^{1/2}/ log n⌉} ≤ (n^{−1})^{n^{1/2}/ log n} = e^{−n^{1/2}}.

Similarly the probability that more than n^{1/2}/ log n vertices j ≥ w fail to have at least 2v neighbours in {j − ⌈w⌉, …, j − 1} is also at most e^{−n^{1/2}}, and the result follows. □

Lemma 5.4. Let G be a graph on [n] with properties P and Q. Then there is a set U of at most 11n^{1/2}/p log n vertices such that any two vertices j, k not in U with |j − k| > 2⌈w⌉ are comparable in the induced partial order.

Proof. Let S and T be sets as in the definitions of properties P and Q respectively. Set V = {j : there are more than v vertices of S in either the set {j + 1, …, j + ⌈w⌉} or the set {j − ⌈w⌉, …, j − 1}}, and set U = T ∪ V. Note that |V | ≤ 2⌈w⌉|S|/v ≤ 9|S|/p. So

|U| ≤ |T | + 9|S|/p ≤ \frac{n^{1/2}}{log n}(2 + 9/p) ≤ \frac{11n^{1/2}}{p log n} .

Suppose that neither j nor k is in U, and that k − j > 2⌈w⌉. Then j is adjacent to at least 2v vertices among {j + 1, …, j + ⌈w⌉}, and at most v of these vertices are in S. Let A be a set of v neighbours of j in {j + 1, …, j + ⌈w⌉} \ S. Similarly let B be a set of v neighbours of k in {k − ⌈w⌉, …, k − 1} \ S. Then there is an edge between some vertex x of A and some vertex y of B. Thus we have j < x < y < k in the partial order induced by G. □

Lemma 5.5. Suppose that G satisfies properties P and Q. Then N(G)/N^{∗}(G, w) ≤ exp(11n^{1/2}/p).

Proof. Let U be a set of vertices as given by Lemma 5.4. Note that G and G^{∗} induce the same partial order on \overline{U} = [n] \ U. Hence for any linear extension ≺ of G, there is a linear extension ≺^{∗} of G^{∗} extending ≺|\overline{U}. Any such map, taking ≺ to ≺^{∗}, is such that at most n^{|U|} linear extensions ≺ are mapped onto any one linear extension ≺^{∗}, since ≺ is determined by ≺^{∗} and the positions of the vertices in U. The result now follows. □

Proof of Theorem 6. First recall Lemma 5.1, which says that

P (| log N^{∗}(G_{n,p}, w) − E log N^{∗}(G_{n,p}, w)| > a) ≤ 2 exp(−\frac{a^{2}}{16nw^{2}} )  (5.2)

for every positive real a, w.

If G satisfies properties P and Q, then, by Lemma 5.5, we have 0 ≤ log N(G) − log N^{∗}(G, w) ≤ 11n^{1/2}/p. By Lemma 5.3, the probability that G_{n,p} fails to satisfy properties P and Q is at most 3 exp(−n^{1/2}); hence

P(log N(G_{n,p}) − log N^{∗}(G_{n,p}, w) > 11n^{1/2}/p) ≤ 3 exp(−n^{1/2}).  (5.3)

Since N(G) ≤ n! for every G, this also implies that

E(log N(G_{n,p}) − log N^{∗}(G_{n,p}, w)) ≤ 11n^{1/2}/p + 3 exp(−n^{1/2})n log n ≤ 12n^{1/2}/p. (5.4)

Recall that |E log N(G_{n,p}) − nμ(p)| ≤ log(1/κ(p)) by (5.1); moreover, rather crudely,

log(1/κ(p)) = ∑_{k=1}^{∞} − log(1 − q^{k}) ≤ ∑_{k=1}^{∞} \frac{q^{k}}{p} ≤ \frac{1}{p^{2}} .  (5.5)

Since the conclusion is trivially true for λ ≤ 80, we may assume 80 ≤ λ ≤ n^{1/4}. We set

a = \frac{λ\sqrt{n}w}{20} ;  (5.6)

recall that w = 4⌈4 log n/log(1/q)⌉/p ≤ 16 log n/p^{2} + 4/p. Now, if | log N^{∗}(G_{n,p}, w) − E log N^{∗}(G_{n,p}, w)| ≤ a and | log N(G_{n,p}) − log N^{∗}(G_{n,p}, w)| ≤ 11n^{1/2}/p, then by these estimates

| log N(G_{n,p}) − nμ(p)|

≤ | log N(G_{n,p}) − log N^{∗}(G_{n,p}, w)| + | log N^{∗}(G_{n,p}, w) − E log N^{∗}(G_{n,p}, w)|

+ | E(log N^{∗}(G_{n,p}, w) − log N(G_{n,p}))| + | E log N(G_{n,p}) − nμ(p)|

≤ 11n^{1/2}/p + a + 12n^{1/2}/p + log(1/κ(p)) ≤ a + 23n^{1/2}/p + 1/p^{2}

≤ \frac{λ\sqrt{n} log n}{p^{2}}(\frac{16}{20} + \frac{4p}{20 log n} + \frac{23p}{λ log n} + \frac{1}{λ\sqrt{n} log n}) ≤ \frac{λ\sqrt{n} log n}{p^{2}}.

Therefore, using (5.2), (5.6) and (5.3),

P(| log N(G_{n,p}) − nμ(p)| > \frac{λ\sqrt{n} log n}{p^{2}})

≤ P(| log N^{∗}(G_{n,p}, w) − E log N^{∗}(G_{n,p}, w)| > a)
+ P(log N(G_{n,p}) − log N^{∗}(G_{n,p}, w) > 11n^{1/2}/p)
≤ 2 exp(−λ^{2}/6400) + 3 exp(−n^{1/2}) ≤ 3 exp(−λ^{2}/6400),

as desired. □

References

1. M. Albert and A. Frieze, Random graph orders, Order 6 (1989), 19–30.

2. K. Azuma, Weighted sums of certain dependent random variables, Tôhoku Math. J. 19 (1967), 357– 367.

3. A. Barak and P. Erdős, On the maximal number of strongly independent vertices in a random acyclic directed graph, SIAM J. Algebraic and Disc. Meths. 5 (1984), 508–514.

4. B. Bollobás, Martingales, isoperimetric inequalities and random graphs, Combinatorics, A. Hajnal, L. Lovász and V.Sós Eds., Colloq. Math. Sci. Janos Bolyai 52, North Holland, 1988.

5. B. Bollobás, Sharp concentration of measure phenomena in the theory of random graphs, Random Graphs ’87, M.Karoński, J. Jaworski and A. Ruciński Eds., Wiley, Chichester, 1991, pp. 1–15.

6. G. Brightwell, Linear extensions of random orders, Discrete Math. (1991) (to appear).

7. G. Brightwell, Models of random partial orders, Surveys in Combinatorics 1993, Invited Papers at the 14th British Combinatorial Conference, K. Walker Ed., Cambridge University Press, 1993 (to appear).

8. A. Gut, Stopped random walks, Springer-Verlag, New York, 1988.

9. W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Stat. Assoc. 27 (1963), 13–30.

10. J.F.C. Kingman, The ergodic theory of subadditive stochastic processes, J. Roy. Statist. Soc. B 30 (1968), 499–510.

11. C.J.H. McDiarmid, On the method of bounded differences, Surveys in Combinatorics 1989, Invited Papers at the 12th British Combinatorial Conference, J. Siemons Ed., Cambridge University Press, 1989, pp. 148–188.

Noga Alon, Department of Mathematics, Tel Aviv University, Ramat Aviv, 69978 Tel Aviv, Israel

E-mail address: noga@math.tau.ac.il

Béla Bollobás, Department of Pure Mathematics and Mathematical Statistics, 16 Mill Lane, Cambridge CB2 1SB, England

E-mail address: B.Bollobas@pmms.cam.ac.uk

Graham Brightwell, Department of Statistical and Mathematical Sciences, London School of Economics, London WC2A 2AE, England

E-mail address: grb10@phx.cam.ac.uk

Svante Janson, Department of Mathematics, Uppsala University, P.O. Box 480, S–751 06 Uppsala, Sweden

E-mail address: svante.janson@math.uu.se