intellecton/papers/project_paper_1_relativity/references/Kleitman1975.txt

TRANSACTIONS OF THE
AMERICAN MATHEMATICAL SOCIETY
Volume 205, 1975

ASYMPTOTIC ENUMERATION OF PARTIAL ORDERS
ON A FINITE SET

BY

D. J. KLEITMANi1) AND B. L. ROTHSCHILD(2)

ABSTRACT.   By considering special cases, the number Pn of partially

ordered sets on a set of n elements is shown to be (1 + 0(\¡n))Qn, 
where

Qn is the number of partially ordered sets in one of the special classes.   The

number Qn can be estimated, 
and we ultimately 
obtain
'»-('+0©)C5lC)(7)<''-^-^)-

1. Introduction. It is known [7] that the logarithm (base 2, as all logarithms
in this paper will be) of the number Pn of partial orders (or equivalently of T0
topologies) on a set of tj elements is T22/4 + o(tj2). In this paper we show that
Pn is asymptotically equal to Qn, the number of partial orders in a certain special
class which is characterized in a simple way. It will follow that log Pn = «2/4 +
3n/2 + 0(log tj). An explicit asymptotic formula for Pn will be given, but it is a
bit messy.
In [5] the number Gn of "graded" partially ordered sets is enumerated.
Since the partial orders counted by Qn turn out to be graded, the number arrived
at in [5] is also asymptotically equal to Pn. The computation of Gn   [5], then,
is asymptotically applicable to Pn.
The methods used here are similar to those used in [7] for obtaining the
asymptotic estimate for log Pn, but here they are somewhat more delicate and
more complicated. We use induction to show that Pn < Qn(l + 0(1/«)), while
Qn < Pn by definition. The proof is accomplished by obtaining all partial orders
on tj + 1 elements from those on tj or fewer elements in certain specified ways.
In each of these ways, except those corresponding to Qn + x, we obtain only an
asymptotically negligible number of partial orders.
The partial orders corresponding to Qn can be described as follows. They
consist of three sets Lx, L2, L3 with \LX\, \L3\ = tj/4 + o(n), \L2\ = ti/2 + o(tj).
Each element in L¡ "covers" only elements in L¡_x (see below for definitions).
And finally, each element behaves in the "average" way.  That is, each element in

Received by the editors November 2, 1973 and, in revised form, January 21, 1974.
AMS (MOS) subject classifications (1970). Primary 05A15.
(x)  Work supported in part by ONR Grant 0014-67-A-0204-0063.
(2)  Work supported in part by NSF Grant GP-33580X.
Copyright © 1975, American Mathematical Society
205


206
D. J. KLEITMAN AND B. L. ROTHSCHILD

L¡ is covered by (asymptotically) half of those in Li+l and covers half of those
inL¡_x.

2. Terminology. We represent a partial order P on a set of tj elements by
its unique Hasse diagram, also denoted by P.   This is a directed graph with the
elements of P as vertices and a single directed edge from a to ft if and only if a
covers b in P (a covers ft if a > ft and a > c>b 
implies c = ft).  Distinct partial
orders have distinct diagrams.  Thus we let Pn denote both the number of partial
orders and the number of diagrams on n elements, as directed graphs diagrams
are characterized by the exclusion of two types of configurations. Namely, a
directed graph is a diagram of a partial order if and only if it contains no set of
(directed) edges Ex, E2, • • • , Ek, E0 such that the terminal vertex of E¡ is the
initial vertex of El+X, 1 <i< 
Jfc— 1, and such that E0 is incident with both the
initial vertex of Ex and the terminal vertex of Ek (in either direction).  That is,
diagrams contain no directed cycles and no cycles with all but one edge cyclically
directed. In particular, diagrams contain no triangles.  We say that two vertices
a and b are adjacent or connected if there is an edge incident with both (that is,
if a covers ft or ft covers a). For any set S of vertices, C(S) will denote the set
of all vertices adjacent to any vertex in S.
We define levels of a diagram P as follows. Level 1 consists of all minimal
vertices of P (vertices covering no other vertex). For each /, level / is the set of
minimal vertices obtained by deleting all vertices in levels 1 ,•••,/- 
1. We
observe that if a is in level i and ft is in level /, and if i < /, then either a < ft or
a and ft are incomparable. Two vertices in the same level are necessarily incom-
parable.
A diagram P is bipartite if there are two parts A and B such that every edge
of P connects a vertex in A with one in B, and A n B = 0.
Consider a diagram P. Let 5 be a subset of V, the vertex set of P.  Then
P - S denotes the diagram obtained from P by deleting all vertices of S and all
edges incident to any of them. (The resulting diagram is not necessarily the same
as the diagram for the partially ordered set with elements V-S and order induced
from P.) The vertices of P - S may be contained in the same level of P - S as
they were in P, or they may be contained in lower levels than they were in P.
Let P have n vertices. Then a vertex it in P is called good if the number of vertices
in lower levels in P - {v} than in P is less than tj x I2. Similarly a set {vx, • • • , vk}
of vertices is good if deleting it affects the levels of fewer than nx¡2 other vertices.
Every subset of a good set is good. Clearly no vertex can have its level affected by
the deletion of vertices in higher levels. Also, if vx and v2 are in the same level oiP,
and Sx is the set of vertices with levels affected by deleting vx, and S2 by deleting v2,


ENUMERATION OF PARTIAL ORDERS 
207

then Sx n S2 = 0.  There can therefore be at most nxl2 vertices in any single
level which are not good. We call any vertex or set of vertices which is not good,
bad.

3. Statement of lemma and theorem. Since the several cases of the lemma
are rather technical, we will first state the lemma here. Then, in the next two
sections, we will use it to prove the theorem. Finally, we will prove the lemma
at the end.
In what follows, let ttj be an arbitrary positive integer, and let F be a set of
m + 1 vertices. We define a (v, Q)-set in a diagram P on the set V of vertices to
be a good vertex v adjacent to a set Q of [ttj1'2] vertices, either all covering it or
all covered by it, such that the level of each element of Q is not affected by the
deletion of v. We write P = Sx V S2 V • • • V Sk for a diagram P to indicate
that V = Sx U S2 U • • • U Sk, S¡ fî S,- - 0 if i ^ /, and vertices of S¡+ x can
cover only vertices of S¡, i = 1, 2, • • • , k - 1. (The S¡ are not necessarily the
levels of P. Consider for instance the diagram P0 with no edges. Any partition
of the vertices Sx, • • • , Sk satisfies P = Sx V • • • V Sk, even though there is
only one level.)
We consider the following classes of diagrams on V:
A(V): Diagrams with some vertex u adjacent to at most ttj/64 other vertices.

UtAm + x = \A(V)\.
B(V): Diagrams with a (v, 0-set with \C(Q)\ > m(l + m~3/8)/2.  Let

Bm + i = \B(V)\.
D(V): Diagrams with a (v, ß>set with \C(Q)\ < t?j(1 - ttj~3/8)/2.  Let

Dm + l = \D(V)l
E(V): Diagrams with at least 30 nonempty levels.  Let Em + X = |Zr(I0l.
F(V): Diagrams with a (v, Q)-set with \C(Q)\ > m(l - m~3,8)/2, such that
the smallest set R of vertices incident with every edge connecting two vertices in
V- (M U C(Q)) satisfies \R\ > 2m3/4.  Let Fm + X = \F(V)\.
G(V): Diagrams not in E(V) with a (v, Q)-set satisfying ttj(1 - ttj~3/8)/2 <
\C(Q)\ < ttj(1 + T72-3/8)/2; with a set R of at most 2ttj3/4 vertices the deletion
of which leaves no edge connecting two vertices of V— ({v} U C(Q) U R); and
such that the smallest set S of vertices incident with all edges of C(Q) satisfies
\S\>2m1'8. 
LetGm + 1 = \G(V)\-
H(V): Diagrams P satisfying the following properties: There is a set TQ of
at most 3T7i7yl8 
vertices such that P - T0 is bipartite; the parts U and W of P - T0
have at least ttj/2 - 3ttj7/8 and at most t?j/2 + 3tt27/8 vertices; P- T0 has at
most 29 levels, Lx, L2, • • • , Lk, k < 29; there is some level L¡ and a set {x, y}
in P - T0 such that {x, y}   is a good set in P - T0 and L¡ n C(x) n C(y) = 0;


208
D. J. KLEITMAN AND B. L. ROTHSCHILD

either \L¡ CtU\> m15'16 and {x, y} C W, or \L¡ DW\> 
m15/16 and {x, y} E U.
UtHm + x = \H(V)\.
I(V): Diagrams P not in A(V) with a set T of at most 102ttj1s/16 vertices
satisfying the following properties: P- T = Lx\l L2V L3 where Lx, L2, L3 are
the levels of P- T (L3 possibly empty); both \LX U L3\ and \L2\ are between
ttj/2 - 102T?jls/16 and ttj/2 + 102ttj1s/16; every two vertices in W = L2 have a
common adjacent vertex in U= Lx U L3, and vice versa; there is a t E T adjacent
both to a vertex x in Lx U L3 and a vertex y EL2. 
Let Im + X = \I(V)\.
J(V): Diagrams P with a set T of at most 102ttj15/16 vertices satisfying the
following properties: P - T is a three level bipartite diagram with parts U and W;
ttj/2 - 102m15/16 < \U\ <T?j/2 + 10277J1S/16 and similarly for \W\; every two
vertices in U (resp. W) have a common adjacent vertex in W (resp. U); there are
two adjacent vertices x, y in T with C(x) and C(y) either both disjoint from U,
or both disjoint from W.   Let /m + 1 = |/(K)|.
Ä<F): Bipartite diagrams P not in A(V) with a subset T of at most 102mls/16
vertices satisfying the following: P- T isa three level biparitite diagram with
levels Lx, L2, L3, and parts U = Lx U /,3, W = X2; |i/| and |iV| are between
ttj/2 - 102T7ils/16 and t?j/2 + 102ttj15/16; for each t E T and each / either no
vertex in L¡ covers / or no vertex in L¡ is covered by t; there are vertices x and y
in T such that C(x) -TELXUL3, 
C(y) -TEL2 
and no vertex of C(x) - T
is adjacent to any vertex of C(y) - T.   LetKm + x = \K(V)\.
L(V): Diagrams P with a subset T of at most lO2!?!1 s^ 6 vertices such that
P-Thas 
three levels, Lv L2, L3, is bipartite, ttj/2 - 102ttj1s/16 < \L2\ < ttj/2 +
102T?215/16, and such that either there is an x in T covered only by vertices in
Lx U T and covering none, with \LX I < tti/2 - ttj31/32, or there is an x in T cover-
ing only vertices in L3 U T and covered by none, with \L3\ < ttj/2 - ttj31'32.
LetLm + x = \L(V)\.
M(V): Diagrams P such that P = Sx V S2 V 53 V 54 and |52| and |53| are
at least m/2-rn31'32. 
Let Mm + X = \M(V)\.
N(V): Diagrams P = Sx V S2 V S3 where at least one of the following in-
equalities does not hold: (ttj + l)/2 - log ttj < |52| < (ttj + l)/2 + log m, and
for i = 1, 3, (ttj -f- l)/4 - ttj1/2 log m < \S¡\ <(m + l)/4 + ttj1/2 log ttj.  Let

X(V): Diagrams P = SXV S2V S3 which are not in N(V).  Let Xn + X =
\X(V)l
0(V): Diagrams in X(V) with not all of the following inequalities valid:
(ttj + l)/4 - m7/8 < |C(u) ns2\<(m 
+ l)/4 + ttj7/8, for all it in Sx U S3, and
(ttj 4- l)/8 - T727/8 < \C(v) n S¡\ < (772 + l)/8 + T7J7/8, for i = 1, 3 and all it in
S2. Let 0m + 1 = |0(J/)|.


ENUMERATION OF PARTIAL ORDERS
209

Q(V): Diagrams in X(V) - 0(V).  That is, each diagram P in Q(V) satisfies
P = LXM L2\l L3, where Lx, L2, L3 are the levels of P, (m + l)/2 - log m <
\L2\< (ttj + l)/2 -f- log ttj, (ttj + l)/4 - ttj1/2 log ttj < \L¡\ < (m + l)/4 +
ttj1'2 log ttj for i = 1, 3, and for each u ELX U L3 and w E L2, (m + l)/4 -
ttj7/8 < \C(u) DL2\<(m 
+ l)/4 + ttj7/8, and (ttj + l)/8 - ttj7/8 < \C(w) n L¡\
< (m + l)/8 +7T27/8, Z=l, 
3.  Let ßm + 1 = \Q(V)\.

Lemma. 77rere is a number v such that for n>v 
all of the following in-
equalities hold:
(1) log (An + JPn) <n/4,
(2) \og(Bn + x/Pn)<nl2-n5l*l4,
(3) log(Dn + 1/Pn_[nX/2])<n3/2l2-n9l*l4,

(4) log(En+x/Pn_29)<9n,
(5) 10g(F„+1//>„)<T2/2-T23/4/5,
(6) log (Gn+X/P„_x)< n -tj7/8/5,
(7) log(//„+1//>„_1)<T2-i2ls/16/4,

(8) log(In + X/Pn)<72/2 -tj/300,
(9) log(Jn+x/Pn_x)< 
7T2/8,
(10) log(Kn + 1/Pn_x)< 9972/100,
(11) l0g(i„ + 1//>„)<T2/2-T231/32/2,
(12) log(A/„ + 1/Z„ + 1)<-Ti/4,
(13) log(A„ + 1/X„ + 1)<-(logT2)2/6,
(14) tj2/4 + 3tt/2 - 3 log tj < log Xn < n2/4 + 3ri/2 + log tj,
(15) log (0„ + X/Pn)< T2/2-T23/4/10.

Theorem. Pn = (1 + 0(l¡n))Qn.

Corollary. 
  Pn = (1 + 0(l/n))f(n), 
where

m = t (") z (" J *)& ~ w - ir~H-

The proof of the corollary is given at the end of the paper, after the proof
of the lemma (§7).

4.  Proof of theorem.  I. The proof is given in two parts.  In part I we show
that the classes A(V) throughN(V), 0(V) and Q(V) are exhaustive. In part II we show
that all classes except Q(V) and X(V) are negligible.
In the remainder of this paper we will adopt the convention that any in-
equality or other statement about functions ofn will be meant to be true only
for all tj sufficiently large, where how large depends on the statement. This will


210
D. J. KLEITMAN AND B. L. ROTHSCHILD

be a convenience since there are so many such statements below.
Let P be a diagram on the set V of tj + 1 vertices, and let P be in none of
the classes described above except possibly X(V) or Q(V).  In what follows we
shall say "by A", "by G", etc., to mean "since P is not in A(V)", "since P is not
in G(Vy\ etc., respectively.
By E, P has at most 29 levels, and hence one level has at least tj/29 vertices.
Of these we know that at most tj1'2 are bad. There must be a good vertex in
this level, call it it.  By A, v must be adjacent to at least tj/64 other vertices, and
since u is good, at most tj1'2 of these have their levels affected by the deletion of
v. Of the remaining vertices (at least tj/64 - tj1'2 > 2«1/2 of them) adjacent to
u, u either covers or is covered by all vertices in a set ß of [tj1'2] vertices. Thus
we have a (v, Q)-set in P.
By B and D, \C(Q)\ must be between tj(1 - n-3/8)/2 and «(1 + tj_3/8)/2.
By F and G there are sets R and S with IK| < 2tj3/4 and \S\ < 2tj7/8 such that
P - (R U S) has no edges between two vertices of V - ({v} U C(Q) U R U S) =
W', or between two vertices of (C(Q) U {v}) - (R U S) = U'. Thus P-(RUS)
is bipartite with parts U' and W' and at most 29 levels.  \R U S\ < 3tj7/8.
Suppose there is a pah xx, yx of vertices such that [xx, yx} is a bad set in
P - (R U S). Then consider P - (R U S U {xx, yx}). At least (tj - 3tj7/8)1/2 of
the vertices of P - (R U S U {xv yx}) are in lower levels than in P - (R U S).
Now suppose {x2, y2} is bad in P - (R U S U {xx,yx}). Consider P -
(fiUSU 
{xx, yx, x2, y2}). At least (ti - 3tj7/8)1/2 vertices in P - (R U S U
{xx, yx, x2, y2}) are in lower levels than in P - (R U S U {xx, yx}). We con-
tinue this process one step at a time, choosingxx, yv x2, y2, • • • , xm, ym with
{f/> y¡} a bad set in P - (R U 5 U [xx, yx, • " , x*v y¡-X})- We proceed until
we can choose no more bad pairs {x, y}. For/ <T23'4, each step decreases the
levels of at least (tj - 3n1ls)x^2 vertices, since \R U S U {xlf yx, '•' , xy^ ,.>>,•_,} 
I
< 3tj7/8.  Since each vertex can decrease its level at most 28 times during this
process, and since tj3/4(tj - 3n1ls)xl2 > 28(tt + 1), the total number ttj of steps
before the process stops is at most tj3/4.
Let T0 = R U S U {xx, yx, • • • ,xm, ym}. Then P - T0 is bipartite with
parts U' - T0 and W' - T0, where |y0| < 3tj7/8, and \W' - T0\ and \U' - T0\
are between tj/2 - 3tt7/8 and tt/2 + 3tj7/8.  Let the levels of P - T0 be Lx, L2,
" ' , Lk, k < 29.  Let ft be the largest value of/ such that either \L, n U'\ >
tj15/16 or \L¡ n W'\ >nxs'16, 
say \Lh n U'\ > tj1s/16.

Then we claim ft < 3.  For suppose h> 4. Let u>x>z>.y 
be in levels
ft, ft - 1, ft - 2, ft - 3, respectively, with u E Lh C\ U'. Then rj6IC' 
and
z G ZJ', since P - T0 is bipartite.  Now by /Z, C(x) n C( v) DLH^0; 
let
«' G 0(x) n C(>») n /,,-.  Then «' >x > z > j, and u' also coversy, since it is


ENUMERATION OF PARTIAL ORDERS
211

adjacent and in a higher level.  But then u, x, z,y form an excluded configura-
tion, a contradiction. Hence ft < 3.
For Z = 1, 2, 3, we claim that if \L¡ n U'\ > nxs/X6 (respectively \L¡ n W\
> Tils/16), then L, n W' = 0 (respectively L¡ n U' = 0).  For let x e /,,. n W'
(respectively x E L¡ n Z7').  By H, as above, x must be adjacent to some vertex
in L¡ H U' (respectively L¡ n W1), a contradiction since no two vertices in L¡ can
be adjacent. Thus if \L¡\ > 2tj15/16, L¡ must be entirely in U' or entirely in W'.
Since \U' - T0\ and |W' - T0\ are both at least u/2 - 3tj7/8, and since
\LÁ < 2t21S/16 for/ > 3, we must have at least one of Lx, L2, L3 entirely in U'
with at least tj15'16 vertices, and one entirely in W' with at least tj15'16 vertices.
In particular, L2 is entirely in W' or entirely in U'. For if not, Lx would be
entirely in U' or entirely in W'. But then L2 would be entirely in W' or entirely
in U', since every vertex in L2 is adjacent to some vertex of Lx.  Similarly, since
L2 E W' or L2 Ç U', we must have L3 E U' or L3 Ç W'. Now either \LX\ <
2nX5/X6 or Lx EU' oiLxE 
W'.  Let   T= T0 U \Jj>3L¡ U ¿x if \LX\< 2nxs/l6,
and T=T0U 
\Jj>3L¡ ii \Lx\>2nX5IX(> (and thus Lx Çf/'orZ,, 
ç W')-
iri < 60TJ15/16, and /> - T is bipartite with parts U = U'- T and W =
W - T, with \U\ and |W| between n/2 - 60«ls/16 and n/2 + ÓOtj15'16. P-T
has two or three levels, Lx, L2, L3 (where L3 =0 in the two level case). Finally
U = Lx U ¿3, W = Z,2, or Í/ = L2, IV = Zj U ¿3. We assume, without loss of
generality, ¿,U¿3= 
U, L2 = W.  By construction of U and W, and by //, every
two vertices of U axe adjacent to a common vertex of W, and vice versa.  Also
|¿1|>2tj15/16.

By /, no vertex in T is adjacent both to vertices of W and U.   Hence T is
divided into two subsets, Ttj and Tw, where C(TW) C\W = 0. 0(7^) n {/ = 0.
By /, no two vertices of Tu are adjacent, and no two vertices of Tw are adjacent.
Thus P itself is bipartite with parts U U Tv and W U 7V
Suppose Z G T, x, y G /,,-, i=l,2 
or 3, and t is adjacent to x and to y.
Then either t covers both x and y or f is covered by both. For if t covers x and
V covers t, by construction of Z7 and W we can let u be a vertex in L¡_x or Li+X
to which both x and y are adjacent.  Then t, x, y, v form an excluded configura-
tion, a contradiction.
Suppose t E T is adjacent to vertices in x and y in different levels of P - T.
Then these levels must be Lx and L3 (by /). x and .y are adjacent to a common
vertex v in L2. Let x be the vertex in Lx, y E L3. Then y covers v, v covers x,
and we must have that y covers t and r covers x, or else x, ,y, u, í form an ex-
cluded configuration.  So if t is adjacent to vertices in Lx and L3, it covers those
in Lx and is covered by those in Ly
All vertices of T, therefore, are in one of the following subsets:


212 
D. J. KLEITMAN AND B. L. ROTHSCHILD

T¡+ = {t \t covers only vertices in L¡ and is covered by none in V - T},

TJ = {t 11 is covered only by vertices in L¡ and covers none in V - T}

for i = 1, 2, 3,

T2 = {t\t covers vertices in Lx and is covered by vertices in L3, and is

adjacent to no others in V-T}.

We now claim that

P = (77) V (Lx U T2) V (L2 U Tx+ U T3 U T°) V (L3 U T+) V (7-+).

To show this we must show that no vertex of T3 is adjacent to any in T2, no
vertex of Tx~ is adjacent to any in T2 , and all other adjacencies are in the "right
direction." (We already know that there are no edges between two vertices of
rf U Tx+ U 77 U T3+ U T% or between two vertices of T2 U T2+.)
If x S r^, y S 77, are adjacent, there can be no edge between C(x)■- T
and C(y) - T or we would have an excluded configuration. Thus by K, x and .y
cannot be adjacent.  Similarly, x ETX and y ET2  cannot be adjacent.
Now suppose x E T¡~, y E TJ+ x, 1 = 1 or 2.  If x coversy, C(x) - T and
C(y) - T must have no edge between them, or an excluded configuration would
result.  Hence, by K, x cannot cover y.  Similarly, if x E T¡, y E T¡~+x, Z = 1 or
2, then y cannot cover x.
Finally, if x E T2 and y E T2  (oty E T2, x ET2, resp.) and if x covers
y (respectively x is covered by y), then no vertex of C(x) - T is adjacent to any
vertex of C(y) - T, or an excluded configuration would result. Thus, by K, x
cannot cover y (respectively y cannot cover x).  This completes the elimination of
all possible connections which would contradict the claim. Thus we have shown
that

P = (77) V (77 U Lx) V (L2 U Tx+ U 77 U r2°) V (L2 U 7+) V <fâ).

(We recall that L3 = 0 is possible here, in which case T3, T3, T2 are all empty
as well.)
Since |¿2|>T2/2-102T215/16, 
we must have |Z,3| <tj/2 
-tj31'32 
or |L,|<
n/2 - tj31/32. Then by L, either Tx = 0 or Tf = 0, or both. But if Tx =£ 0,
by L we must have \LX\ > n/2-n31'32; 
or if J+ # 0, \L3\ > n/2-n31'32.
By M, neither of these possibilities occurs.  Hence Tx = T3  = 0.
This gives us P = Sx V 52 V 53, where SX=LXU 
T2, S2=I2ur2°U
Ti+UT3, 53 = L3ur2+. 
Finally, then, by AT and 0, P must be in Q(V). In
particular, since every vertex of S2 covers some (at least tj/8 - tj7'8) vertices of


ENUMERATION OF PARTIAL ORDERS 
213

Sj, and every vertex of S3 covers some (at least tt/4 - t27/8) vertices of S2, the
S¡ are in fact levels in P. Part I of the proof of the theorem is now complete.

5. Proof of theorem. II. We shall use the results of the last section, together with
the lemma, to show that.P„ <(1 + 0(l/72))ß„. First we show thatP„ <(1 + 0(llri))Xn.
Let v be the number guaranteed by the lemma, and let N = max(2i>, 109).
Let C0 be a number large enough so that Pn < (1 + (C0)¡n)Xn for all n <N, and
let C= max(C0, 109). We claim that/>„ < (1 + C/n)Xn for alln.
The proof of this claim is by induction on tj. For tj < N it is true by choice
of C We assume that it is true for all tj < ttj, for some m>N, and show that
Bm +1 ^ 0 + C/(m + l))Xm + x as well. Since, by the last section, we have Pm + x <
Am + i +Bm + i +^m + i +•" 
+ #«+i 
+ Xm+l> we need onlV ^ow that
(Am + i + "' 
+Nm + OI(Xm + 0 < cKm + 0-  To do this we sha11 employ the

inequalities of the lemma to show that each of the terms Am + X¡(Xm + j),
Bm + xliXm + x), • • • , Nm + xl(Xm + x) is at most 1/13 • C/(ttj + 1) (there are 13
terms here).  These arguments are all similar, and we illustrate a few typical ones.

(D^B+l.ds+i 
^L^S- 
<2-/4(l + C/TT2)2-'"/2 
+ sl0^<-4l 
• ^,
Xm + X        *m      XmXm + \ 
772+1     1J

Dm + l _       Dm+1 
m-jm1/2] 
       m-[mxl2] 
Xm

Xm + 1      Pm-\mW\Xm-\m*tl\ 
Xm-[mlf2\+l 
Xfn + 1

(3) 
<2m3l2l2-'Am9l8il 
+_Ç._\ 
2-(m/2-lm1/2]/2)([m1/2l 
+ l)
i/2-%m9/8f/]
m —   \wi *
[m1'2]

. 2S([m1/2] +1)log TTJ

<^ 
C
13   TT7 
+ r

(13)

Nm + 1

Xm + X
<2_(,ogm)2/6>    bythelemmaj

<A       C
13/71 + 1'

These and similar arguments, then, for the other cases complete the induction.

We thus have Pn < (1 + C/n)Xn for all 72.
By the lemma, On + l/Pn < 2("/2)-(1/io)n3/4 
for „ >N^ 
aiSO) by the
definitions of 0(V), X(V) and Q(V), we have Xn+X = On + x + Qn+l. These
facts lead to


214
D. J. KLEITMAN AND B. L. ROTHSCHILD

<   f 1 +        1 )ßn + i    for « sufficiently large.

This establishes .Pn = (1 + 0(l¡n))Qn and completes the proof of the
theorem.

6. Proof of lemma. We let V be a set of tt + 1 vertices. We recall our
convention, that all statements in inequalities asserted below are meant to be
valid only for n sufficiently large. More specifically, for each statement below
there is a number N' such that the statement is valid for tj > N'. We can then
let v be the maximum of all of these N'. The numbered paragraphs below cor-
respond to the numbered inequalities of the lemma.
For the sake of brevity, we include only a few of the cases in detail. The
rest of them are represented only by the final inequalities of the arguments, from
which one can obtain a hint as to the order in which things are constructed. We
choose one simple case, and the most complicated ones to do in detail.
(1) This inequality is Lemma 2 of [7].  It is proved like those below.
(2) This and (3) below correspond to Lemmas 3 and 4 of [7].
We obtain all diagrams in B(V) from diagrams on tj vertices by choosing
v E V, choosing a diagram on V - {v}, and then adjoining v to the diagram so
as to satisfy the conditions for B(V). We will obtain upper bounds for the num-
ber of possible choices by counting some possibilities which cannot satisfy the
conditions for B(V) as well as all those that do. This is the general method used
below, where instead of just choosing a single v, we may need to choose a sub-
set S E V, a diagram on V - S, and then to adjoin S to the diagram.
To obtain diagrams in B(V), then, we choose vE V (n + 1 ways to
choose v) and a diagram on V - {v} (at most Pn ways to do this). Now v will
be taken as the vertex of a (v, ß)-set.
To connect v, we first choose a level for v to be in (at most « + 1 possibil-
ities). Then we choose ß (at most „C[„i/2j ways, where many of the sets of [tj1'2]
vertices in V - {it} included in this number will not be valid candidates for ß,
depending on which diagram was chosen for V - {v}). The directions of the
connections between v and ß are now determined, because in order to be in


ENUMERATION OF PARTIAL ORDERS 
215

B(V), the levels of vertices in ß must be unaffected by the addition of it. Hence
v covers all vertices of ß if its level is higher than all of them, and is covered by
all vertices if its level is lower. (One of these two possibilities must occur, or we
would have an invalid choice for Q.)
Since ß will satisfy conditions for B(V), we have \C(Q)\ > n(l + n~3/s)/2.
Since there are no triangles, v can be connected to at most «(1 - ti_3/8)/2 remain-
ing vertices.  Since v must be a good vertex, at most tj1'2 of these vertices can
have then levels affected by the addition of v. The vertices which can have their
levels changed can be chosen in at most

'"¿n'(Kl-»-'">«l)<«W2?'''
/=o    ^ 
l

1 /2
ways,  v can then be connected to these vertices in at most 3"      ways (the 3 is
for the choices: v covers x, x covers it, and x and v not connected).  Finally, the
other vertices to which v can be connected can be chosen in at most 2"*1-"      ^2
ways. The directions of these connections are determined by the levels relative to
the level of v.  All connections of it are now completed. Multiplying all these
numbers of possible choices gives the following:

log (^A 
   < l0g(TJ + 1) + l0g(7J +  1) + log   ("/2]

+ log (72(72/2)" 1/2) + nl'2l0g 
3 + 72(1 -T2"3/8)/2

< 2 log (77 + 1) + T21/2  log TJ + log TJ + T21/2 log Tl/2

+ TJ1/2 log 3+ T2/2- 72S/8/2

<«/2-TI5/8/4.

This completes (2). We used one of two basic relations here, which will be used
repeatedly below.

.eg (;,,,) 
<„° iog.

The other is Stirling's formula or the normal approximation, which gives
(recall, for tj sufficiently large, here depending on the ß):

log ( "   J < - T2(oi 
log a + (1 - a) log(l - a))

for 0 < ß < a < lA, and ß fixed (independent of ti).


216 
D. J. KLEITMAN AND B. L. ROTHSCHILD

loS (r „   '   ^M,1 < " - M™2    for 0 < ot < 0 < 1, and 0 fixed.
\[tj(1 -a)/2]J

<iog(«+D+iog ([wr/2])+i
n-ln1/2]

+ l0g(|^"2]| 
+ (l+«1/2)(Tj/2-T2S/8/2)+T2l0g3

<T23/2/2-T29/8/4.

(4) 
log [pJ1±L)   < log i" *M + log(30!) + (72 - 29) log 496 < 9«.

(5) 
loH~p) 
<3n1l2\ogn+n(l+n-3ls)l2-2n3'4+n3l4log3

<n/2-n3'4IS.

(6) log (j^A 
< 15n3'4 log 72 + | + | - 2n7/8 + tj7/8 log 3 <tj -ti7/8/5.

Hn +
(7) 
log -~ 
  < 10nllB log tj + « - 2A + A log 3 < « - tj1 5/! 6/4.
P.n-X

(8) We obtain all diagrams in I(V) by considering two subclasses l'(V) and
l"(V). I'(V) will be the class of diagrams in I(V) such that T contains a vertex t
and a set S E C(t) n W (respectively, C(i) n ZJ) of [tj16/17] vertices such that
C(S) n ZJ (respectively, C(S) n W) has at most tt/2 - tj/300 vertices. l"(V) =
I(V)-I'(V).
We obtain diagrams in I'(V) by choosing T, t, Lx, L2 (and L3), S, C(S) n Z7
(respectively C(5) n iV) (there are at most 26" ways to make these choices), and
then connecting the vertices of Lx, L2, L3 and T.   Tcan be connected to Fin
at most 31o2/!15/16«.  j^ 
ieaves ^e connections of U to W to be made. The
directions of these connections are already determined by the choice of Lx, L2
and L3.   S can be connected to U (respectively W), then, in at most

2/»16/17(«/2-n/300) waySj and the rest 0f w to U in at most

2(n/2+102n1S/16-n16/17)(«/2 
+ 102n1S/16)

ways.  This gives:


ENUMERATION OF PARTIAL ORDERS
217

log|/(I0| < 6tj + lO2«31'16 log 3 +tj2/4-tj33/17/400.

We know from [7], or trivially by direct observation, that Pn > 2"2/4 (also
from paragraph (14) below). Thus

log|/(HI/P„<-ri33/17/500.

We obtain diagrams in l"(V) as follows: We choose t (n + 1 ways) and
a diagram on V- {t} so that there is a set T' with T = T' U {t} satisfying con-
ditions for I(V) (at most Pn ways, and at most

1„1S/16]J
Jl027

ways to choose T'). Then, since every two vertices in U (respectively, W) are
adjacent to a common vertex of W (respectively, Z7), t can be connected to each
level in only one direction or an excluded configuration results (at most 23 choices
for directions for t).  í can be connected to r'at 
most 3lo2"ls'16 
ways. To
satisfy the conditions on I(V) there must be vertices x E U and y E W adjacent
to t (at most ti2 ways to choose x and y, and 4 ways to connect them to t).
By A, t must be adjacent to tj/64 other vertices at least, and of those to at
least T216/17 in U, or n16'11 in W, say W. There are at most

1ti/2 + 102tj15/16]\

[„16/17! 
)

ways to choose a set S of [ti16'17] vertices in W to be included in C(t) n W.
But by the conditions for l"(V), \C(S) C\ U\> n/2 - ti/300. x must thus be in
U - (C(S) n U) and C(x) n W must be at least nl65, by A.   The remaining
vertices of C(t) must be chosen from ((W-S)- 
C(x)) U(U- 
C(S)), of which
there are at most

(n/2 + lOV5'16 
- [ir16'17] -tj/65 +TJ/2 + lOV5'16 
-n/2 + ri/300)

<tj/2-72/130.

Thus there are at most 2"/2-"/130 
ways to complete the connections of t.
This all gives

loJ\[^)<6ni6ii7x 
      +rL_jn_<n__n_
\pn    / 
-°g"^2    130    2    200'
Thus

,       A. + A        .       f\l'(V)\+\In(V)\\    _„.       (\I\V)\      .    A     „72 
72
l0SUrj=l0g 
  -Bn-J 
 <l0S [— 
+1    <2"3ÖÖ-


218 
D. J. KLEITMAN AND B. L. ROTHSCHILD

(9) 
log (¿^ 
 < 9 • 10V5'16 log Ti + | log 3 < I n.

(10) 
log (g±£} < 10-«-/- 
log TJ + | + \ - f6 < ^ 
n.

(11) logC^) 
   <|-«31/32 
+5 .  102„1S/16 log„<|_l„31/32

(14) We now estimate Xn so we can use it ior Mn + X and A„ + 1. We
obtain a lower bound for Xn by considering the subclass consisting of all three
level diagramsP = Lx V ¿2 V L3 with \L2\ = [n/2],  \LX\ = [n/4],  \L3\ =
ti - [tj/2] - [n/4]. We can choose L2 in ([„"21) ways, and then Lx in ("fjp/2 ')•
Each vertex in L2 can be connected to Lx in 2^"/4] - 1 ways. (The -1 is neces-
sary because L2 is a level and thus each vertex in L2 must be adjacent to at least
one in Lx.) Each vertex in L3 can be connected to L2 in (2S"I2X - 1) ways.
Thus we can choose the edges of P in (2*"^ - 1y>-1"/21-["/41(2["/41 _ tfn/2]
ways. We only get diagrams counted by Xn here, and we get no diagrams twice.
Thus

log X„ > log (^ 
 + log (" " j^1) 
 +  [T2/2] (72 - [T2/2]   - [T2/4] )

+ [n/2] [72/4] + [n/2] log(l - 1/2Í"/4!)

+ (n - [n/2] - [tj/4]) log(l - 1/2Í"/2»)

>l0g(l/T2  •  2") + l0g(l/T2 • 2"/2)

+ (TJ - [ti/2])[t2/2]   - 1 > T22/4 + 3T2/2 - 3 log 72.

We find an upper bound for Xn equally easily. Let V be a set of tt elements.
Diagrams in X(V') are obtained as follows. We choose S2 (at most 2" ways); Sx
from V - S2 (at most 2"/2+log " ways); and connections from Sx U S3 to S2 (at
most 2" I4 ways).  This gives

log(X„) < ti2/4 + 3n/2 + log n.

Together with the lower bound for Xn+X we get \og(Xn/Xn + x) < - n/2 + 5 log 72.

(12) 
log(Mn + x)<(n + l)2/4 + (tj + 1) + 2 log« + 4«31/32log«.

From the lower bound on!n + 1 we get log(M„ + X/Xn + x) <-n/4.


ENUMERATION OF PARTIAL ORDERS 
219

(13) We obtain diagrams in N(V) by considering two cases. In the first case,
we suppose that not both of the inequalities (72 + l)/2 - log tj < \S2\ < (n + l)/2
+ log « hold. This gives a number N'n+X of choices with

^og(N'n+1)<2(n + 1)+ 1 -\S2\ + \S2\(n + 1 -\S2\)

O3) 
^(T2 + l)2   ,  3(72 4-1)      1
<■     4       ■       2

In the second case, we assume that

fOogTî)2

T2 + 1      . 
^ ip   i  ^72 + 1      ,   ,
—2-log 
n < |521 <—2— +1°g">

and that either

ls«l>ZHrL + »1/2log7j   or   |sy<i+l.l|i/al0iJ(>

for 1 = 1 or 3. This gives a number N¡¡+ x of choices with

l0g«+1) 
= 2 + (72 + 1) + log TJ + (T2 + l)2/4

[(« + l)/2 + log 72]
(14) 
+ log ,
\[(" + l)/44-«1/2logn]

< (72 + l)2/4 + 3(tj + l)/2 - y4 (log TJ)2.

We get

n+X/ 
\ 
Xn + X
108 O 
<* ""fe" 
<- 5 <*■>*•

log -fr1"   < l0g(» + 1) + 25t21/2 log T2 + log TJ
"n

(15) 
8\U(« 
+ l)/4 + 727/8]

+ 2(«+1)/4+ni/2log„ + 1A(" + 1)/4+«1/2/1°g"A\
log "     V [(» + D/8 + «7/8]    ))

* 2    IO"     '

7. Proof of corollary.  For a set K of tj vertices, let 7(10 De the class of
diagrams P such that P = LXV L2V L3, where Lx, L2, L3 are the levels of P.


220
D. J. KLEITMAN AND B. L. ROTHSCHILD

Let Yn = \Y(V)\. We obtain all diagrams in Y(V) by first choosing Lx, then L2
and then connecting L2 to Lx and L3 to L2. There are exactly (2IL2' - 1) ways
to connect each vertex in L3 to L2 (there must be at least one connection since
L3 is a level), and exactly (2   * - 1) ways to connect each vertex of L2 to Lv
This gives

Yn - t (") Z (" y '") (2'' - D'C - I)""'"-''.

Since Y(V) > Q(V), we have

Y„ <P„ = (1 + 0(1/Ti))ß„ < (1 + 0(1/T2))7„.

Thus.?,, = (1 + 0(l/n))Yn, 
and the corollary is proved.

REFERENCES

1. K. K.-H. Butler, The number of finite partially ordered sets, Notices Amer. Math.
Soc. 18 (1971), 1092. Abstract #71T-A250.
2. S. D. Chatterji, The number of topologies on n points, Kent State University, NASA
Technical Report, 1966.
3. L. Comptet, Recouvrements, 
bases de filtre et topologies d'un ensemble fini, C. R.
Acad. Sei. Paris Ser. A-B 262 (1966), A 1091-A 1094.     MR 34 #1209.
4. J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration 
of finite
topologies, Comm. ACM 10 (1967), 295-298.
5. D. Klarner, The number of graded partially ordered sets, J. Combinatorial Theory
6 (1969), 12-19.    MR 38 #4333.
6.-, 
The number of classes of isomorphic graded partially ordered sets, J.
Combinatorial Theory 9 (1970), 412-419.    MR 42 #2989.
7. D.  Kleitman  and  B.  Rothschild, 
The number 
of finite 
topologies, 
Proc. Amer. Math.
Soc. 25 (1970), 276-282.    MR 40 #7157.
8. V. Krishnamurthy, 
On the number of topologies on a finite set, Amer. Math. Monthly
73 (1966), 154-157.    MR 34 #1208.
9. A. Shafaat, On the number of topologies definable on a finite set, J. Austral. Math.
Soc. 8 (1968), 194-198.    MR 37 #1263.

DEPARTMENT OF MATHEMATICS, MASSACHUSETTS INSTITUTE OF TECH-
NOLOGY, CAMBRIDGE, MASSACHUSETTS 02139

DEPARTMENT OF MATHEMATICS, UNIVERSITY OF CALIFORNIA, LOS
ANGELES, CALIFORNIA 90024