CHAIN DECOMPOSITION THEOREMS FOR ORDERED SETS

AND OTHER MUSINGS

Jonathan David Farley

This paper is dedicated to the memory of Prof. Garrett Birkhoff

Abstract. A brief introduction to the theory of ordered sets and lattice theory is given. To illustrate proof techniques in the theory of ordered sets, a generalization of a conjecture of Daykin and Daykin, concerning the structure of posets that can be partitioned into chains in a “strong” way, is proved. The result is motivated by a conjecture of Graham’s concerning probability correlation inequalities for linear extensions of finite posets.

1. Introduction

Order has played a rôle in human civilization for as long as the North Star has hung above our heads. The theory of ordered sets, however, is a relatively new discipline.

Lattice theory and the theory of ordered sets are exciting areas with a number of surprising connections with other branches of mathematics, including algebraic topology, differential equations, group theory, commutative algebra, graph theory, logic, and universal algebra. Both fields have many important applications, for example, to scheduling problems, the semantics of programming languages, the logic of quantum mechanics, mathematical morphology and image analysis, circuit design, and cryptography [2], [10], [14], [21].

Below we present a sampling of theorems — some famous, some not — dealing with decompositions of ordered sets into chains. We will expand upon our own original work (presented in §7) in a future note.

1991 Mathematics Subject Classification. Primary 06A07, 05A18; Secondary 06-02, 06-06, 05-02, 05-06.

The author would like to thank Dr. William Massey and Dr. Nathaniel Dean for inviting him to speak at the Second Conference for African-American Researchers in the Mathematical Sciences. The author would also like to thank Prof. Bill Sands for permitting him to publish his theorem. This paper is based on a lecture given at the Institute for Advanced Study in Princeton, New Jersey, on June 27, 1996.

Typeset by AMS-TEX

2. Basic terminology, notation, and examples

A partially ordered set, or poset, is a set with a binary relation ⩽ that is reflexive, transitive, and antisymmetric. Elements a, b ∈ P are comparable, denoted a ∼ b, if a ⩽ b or a ⩾ b; otherwise they are incomparable, denoted a ∥ b. An element a is a lower cover of b if a < b and a < c ⩽ b implies b = c for all c ∈ P; in this case, b is an upper cover of a, which we denote by a ≺ b. The Hasse diagram of a finite poset is a graph in which each vertex represents an element, and an edge drawn upward from a to b means that a ≺ b. Hence a ⩽ b if and only if one can go from a to b by tracing the edges upward.

A chain is a subset C of P such that a ∼ b for all a, b ∈ C. A chain c_{1} < c_{2} < ⋯ < c_{n} is saturated if c_{1} ≺ c_{2} ≺ ⋯ ≺ c_{n}. The length of a finite chain is #C − 1 (where #C is the cardinality of C). The height ht x of an element x is the supremum of the lengths of the finite chains with greatest element x. The height ht P of a poset is the supremum of the heights of its elements. A finite poset is ranked if, for all x ∈ P, every chain with greatest element x is contained in a chain of length ht x with greatest element x. A saturated chain c_{1} ≺ c_{2} ≺ ⋯ ≺ c_{n} in a ranked poset is symmetric if ht c_{1} = ht P − ht c_{n}.

An antichain is a subset A of P such that a ∥ b for distinct a, b ∈ A. The width of a poset is the supremum of the cardinalities of its antichains.

For all p ∈ P, let ↑ p := { q ∈ P | p ⩽ q } and ↓ p := { q ∈ P | p ⩾ q }. An element p is maximal if ↑p = {p}; let Max P denote the set of maximal elements. An up-set of P is a subset U such that, for all u ∈ U, ↑u ⊆ U.

The disjoint sum of two posets P and Q is the poset with underlying set P ∪ Q and the inherited order on P and Q, but no comparabilities between elements of P and elements of Q. The ordinal sum of P and Q is the poset with underlying set P ∪ Q and the inherited order on P and Q, but with p < q for all p ∈ P and q ∈ Q. It is denoted P ⊕ Q.

A lattice is a non-empty poset L such that, for all a, b ∈ L, the least upper bound of a and b exists, called the join of a and b (denoted a ∨ b), and the greatest lower bound of a and b exists, called the meet of a and b (denoted a ∧ b). A sublattice is a non-empty subset closed under join and meet. A lattice is distributive if, for all a, b, c ∈ L, a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) [equivalently, for all a, b, c ∈ L, a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)].

An example of a chain is the real line with the usual ordering. The power set of a set is a distributive lattice; here join corresponds to set union and meet to set intersection. The collection of all subsets with 42 elements is an antichain. The collection of subsets of {x, y, z} containing either {x, y} or {z} is an up-set of the power set of {x, y, z}.

The left and right sides of Figure 1 are the Hasse diagrams of the four-element fence P and the four-element crown Q, respectively. Their disjoint sum and ordinal sum are shown in Figures 1 and 2.

Another example of a distributive lattice is the set of natural numbers ordered by divisibility (a ⩽ b if a divides b). In this lattice, a ∨ b is the least common multiple of a and b, and a ∧ b is the greatest common divisor of a and b.

CHAIN DECOMPOSITION THEOREMS FOR ORDERED SETS AND OTHER MUSINGS 3

[figure: P; Q]

Figure 1. The disjoint sum of P and Q.

[figure]

Figure 2. The ordinal sum P ⊕ Q.

The lattice of equivalence classes of propositions in propositional logic is a distributive lattice when ordered by implication (the class [p] of the proposition p is less than or equal to [q] if p implies q). In this lattice, [p] ∨ [q] = [p or q] and [p] ∧ [q] = [p and q].

The lattice of subspaces of a vector space is not distributive if the dimension of the space is at least 2. The five-element lattices M_{3} and N_{5} of Figure 3 are also non-distributive.

[figure]

Figure 3. The lattices M_{3} and N_{5}.

Figure 4 shows the Hasse diagram of a poset that is not a lattice.

[figure: a; b]

Figure 4. A non-lattice.

The elements a and b have common upper bounds, but not a least upper bound, so the poset is not a lattice.

Basic references on lattice theory and the theory of ordered sets are [1] and [4].

3. Dilworth’s theorem

Even mathematicians who know very little about the theory of ordered sets have heard of Dilworth’s Theorem. (R. P. Dilworth actually proved many beautiful and important theorems in the theory of ordered sets, all of them called “Dilworth’s Theorem.” We, in particular, should note that Dilworth helped to develop mathematics programs on the Continent [3].)

Suppose one desires to partition a poset into chains, using the smallest number possible. (For instance, one would want such a partition for some scheduling applications.) If P has finite width w, then clearly we cannot do better than w chains. Dilworth’s Theorem asserts that we can achieve this bound ([8], Theorem 1.1).

Dilworth’s Theorem. Let P be a poset of finite width w. Then there exists a partition of P into w chains, and this is best possible.

Note that we are not assuming P is finite; Dilworth’s Theorem fails, however, for posets of infinite width, even if every antichain is finite [17].

For example, in Figure 5, the poset has width 4 ({a, b, e, f} is an antichain), and can be partitioned into 4 chains (e.g., {0, a, d, 1}, {b}, {e}, {c, f}).

[figure: a; b; c; 0; d; e; f; 1]

Figure 5. An illustration of Dilworth’s Theorem.

For more on Dilworth’s work, see [9].

4. Birkhoff’s theorem

Garrett Birkhoff was one of the pioneers of lattice theory and universal algebra. Two of his many significant contributions involve distributive lattices.

Birkhoff characterized distributive lattices in terms of forbidden sublattices [analogous to Kuratowski’s characterization of planar graphs in terms of forbidden subgraphs ([11], Theorem 6.2.1)].

Theorem (Birkhoff–Dedekind). A lattice is distributive if and only if neither M_{3} nor N_{5} is a sublattice.

The theorem makes it easy to spot non-distributive lattices. For instance, the lattice of Figure 5 is not distributive. For a proof of the theorem, see [4], 6.10.

Now we know what lattices are not distributive. Which lattices are distributive? Here is one way to construct distributive lattices: Take a finite poset, and order

its up-sets by inclusion. This procedure yields a finite distributive lattice, in which join and meet are given by union and intersection, respectively.

For example, if Abubakari is the three-element fence (Figure 6), its lattice of up-sets is shown in Figure 7.

[figure: a; b; c]

Figure 6. The poset Abubakari.

[figure: {a}; {a, b}; {a, c}; {a, b, c}; ∅]

Figure 7. The distributive lattice of up-sets of Abubakari.

Another theorem of Birkhoff’s asserts that all finite distributive lattices arise in this way ([4], 8.17). One consequence, which we shall need later, is that finite distributive lattices are ranked.

Theorem (Birkhoff). Every finite distributive lattice is the lattice of up-sets of a finite poset.

There is an analogous theorem for infinite distributive lattices, but, instead of finite posets, one must use compact Hausdorff partially ordered spaces, called Priestley spaces [18].

5. Sands’ matching theorem

Now we may prove an amusing theorem due to Bill Sands [20]:

Theorem (Sands, 197∗). Every finite distributive lattice with an even number of elements can be partitioned into two-element chains.

In the terminology of graph theory, the theorem asserts that the comparability graph of a finite distributive lattice with an even number of elements [in which (a, b) is an edge if a ∼ b] has a perfect matching without loops ([11], §7.1).

The reader might like to attempt his or her own proof before proceeding.

Proof. We prove the theorem by induction on the size of L. If #L is odd, and L has greatest element 1, we prove that L \ {1} can be partitioned into two-element chains.

Represent the lattice as the lattice of up-sets of a finite poset P. Pick p ∈ P, and consider the the elements a :=↑p and b := P \ ↓p of L. Then L is partitioned into the finite distributive lattices ↑ a and ↓ b. There are four cases to consider, depending on the parities of # ↑a and # ↓b. □

The theorem is interesting because most chain-decomposition theorems apply either to arbitrary posets (e.g., Dilworth’s Theorem) or only to power set lattices (e.g., [16]). Sands’ Matching Theorem is obvious for power set lattices, but does not apply to all posets, not even all lattices. For example, M_{4} (Figure 8) is non-distributive, by Birkhoff’s theorem; it cannot be partitioned into two-element chains. (This example is due to Sands.)

[figure]

Figure 8. The lattice M_{4} cannot be partitioned into two-element chains.

6. The parable of the tennis players

Our main theorem is a generalization of a conjecture of Daykin and Daykin that deals with special sorts of chain-partitions. The motivation for the conjecture comes from a parable, due to Graham, Yao, and Yao ([13], §1):

Imagine there are two teams of tennis players, A and B. The players of Team A are linearly ranked from best to worst, as are the players from Team B, but we know only in a few cases how individual players from Team A compare with individuals from Team B.

We may describe this set-up using a poset: The players are the elements, and a relation p < q means that player p is worse than player q. Hence the subset corresponding to Team A is a chain, as is the subset corresponding to Team B (so that we have a poset of width at most 2). For an example, see Figure 9.

In Figure 9, we do not know whether Asmodeus (in Team A) is better or worse than Beezelbub (in Team B). We might ask for the probability that Asmodeus is worse than Beezelbub, P r(Asmodeus<Beezelbub). We calculate this probability by looking at all the possible linear rankings of the players in both teams that are consistent with what we already know about which players are better than which.

Formally, we are looking at all the possible linear extensions of the poset, the bijective order-preserving maps from P into a chain of cardinality #P. By counting the number of these in which (the image of) Asmodeus is below (the image of) Beezelbub, and dividing by the total number of linear extensions (assuming all are equally likely), we have P r(Asmodeus<Beezelbub).

[figure: A; B; Asmodeus; Beezelbub]

Figure 9. A tale of two tennis teams.

Now suppose we are given additional information. Namely, suppose we learn that certain players from Team A are worse than certain players from Team B. (Perhaps the two teams have just finished playing a tournament.) This information supports the idea that the players from Team A are worse than the players from Team B, making it more likely that Asmodeus is, in fact, worse than Beezelbub.

Formally, we would expect:

P r(Asmodeus<Beezelbub) ⩽ P r(Asmodeus<Beezelbub | a < b & ⋯ & a′ < b′),

the conditional probability that Asmodeus is worse than Beezelbub given that a is worse than b, a′ worse than b′, etc. (See Figure 10.)

[figure: a; a′; b; b′; A; B; Asmodeus; Beezelbub]

Figure 10. The poset of tennis players after a tournament.

We can formalize a more general situation. Let P be a poset partitioned into subsets A and B (not necessarily chains). Suppose that, whenever x and y are disjunctions of statements of the form

a < b & ⋯ & a′ < b′

we know that

P r(x)P r(y) ⩽ P r(x&y).

Then we say the partition has the positive correlation property.

Using a result of Daykin and Daykin ([5], Theorem 9.1), a question of Graham’s ([12], pp. 232-233) becomes:

Question (Graham). Let P = A ∪ B be a partition of a finite poset such that, for all a ∈ A and b ∈ B,

a < b implies P = ↑a ∪ ↓b

and

a > b implies P = ↓a ∪ ↑b.

Does the partition have the positive correlation property?

7. A conjecture of Daykin and Daykin

In light of Graham’s question, Daykin and Daykin ([5], §9) conjectured the following:

Conjecture (Daykin–Daykin). Let P be a finite poset partitioned into chains T_{1}, T_{2}, and T_{3} such that, if p and q are in different chains and p < q, then P = ↑p∪↓q.

Then P is an ordinal sum R_{1} ⊕ ⋯ ⊕ R_{n} such that, for 1 ⩽ i ⩽ n, either

(1) R_{i} is disjoint from some T_{j}, j ∈ {1, 2, 3}, or

(2) for all p, q ∈ R_{i}, if p and q are in different chains, then p ∥ q.

With this conjecture, Daykin and Daykin asserted that certain correlation inequalities would follow.

Figure 11 shows an example of a poset satisfying the hypotheses of the conjecture. Let T_{1} be the chain of all the elements on the left, T_{2} all the elements on the right, and T_{3} the remainder.

[figure]

Figure 11. A poset satisfying the hypotheses of the Daykin–Daykin conjecture.

Note that the conclusion of the conjecture implies that P is the ordinal sum of width 2 posets and disjoint sums of chains.

Tseng and Horng [23] claim to have a proof, but their proof rests on a mistaken assertion. The author has proven a more general statement, with a much simpler proof, which applies to infinite posets; we shall write another note on this theorem. (Incidentally, although the fact was not publicized, it is reported in [6], p. 84 that J. M. Robson proved the Daykin–Daykin conjecture by an inductive argument.)

The results in the sequel are due to the author.

By P (R_{1}, …, R_{n}; T_{1}, …, T_{s}), we mean:

(1) P is a finite poset;

(2) P = R_{1} ⊕ ⋯ ⊕ R_{n};

(3) P = T_{1} ∪ ⋯ ∪ T_{s};

(4) { T_{j} | j = 1, …, s } are disjoint chains;

(5) for i ∈ {1, …, n}, either R_{i} is disjoint from T_{j} for some j ∈ {1, …, s} or

p ∥ q for all p ∈ R_{i} ∩ T_{j} and q ∈ R_{i} ∩ T_{k} (1 ⩽ j < k ⩽ s).

Lemma. Let P′(R′_{1}, …, R′_{m}; T′_{1}, T_{2}, …, T_{s}) where s ⩾ 3. Suppose that P = P′ ∪ {x} is a poset with a new element x, ht x = ht P and for all p ∈ P such that ht p = ht P,

#{ q ∈ P | q ≺ p } ⩽ #{ q ∈ P | q ≺ x }.

Assume that T_{1} := T′_{1} ∪{x} is a chain. Finally, assume that, for all p ∈ T_{j}, q ∈ T_{k}, 1 ⩽ j, k ⩽ s, j ≠ k, p < q implies P = ↑p ∪ ↓q.

Then P (R_{1}, …, R_{n}; T_{1}, …, T_{s}) for some R_{1}, …, R_{n} ⊆ P.

Proof. If Max P = {x}, let R_{i} := R′_{i} (1 ⩽ i ⩽ m) and R_{m+1} := {x}. We may thus assume that Max P ≠ {x}.

We claim that p ⩽ x for all p ∈ R′_{m−1}.

For if p ⩽̸ x, where p ∈ R′_{m−1} ∩ T_{k}, then ↑ p ⊆ T_{k}; in particular, R′_{m} ⊆ T_{k}. If C ⊆ P is a chain containing x, then C ∪ {y} \ {x} is a chain for all y ∈ R′_{m}, so that, for some y ∈ R′_{m}, ht y = ht P. Hence y has more lower covers than x, a contradiction.

If R′_{m} ∪ {x} is disjoint from some T_{j}, we finish by letting R_{i} := R′_{i} (1 ⩽ i < m) and R_{m} := R′_{m} ∪ {x}.

We may therefore assume that (R′_{m} ∪ {x}) ∩ T_{j} ≠ ∅ for j = 1, …, s.

Case 1. For 1 ⩽ j ⩽ s, R′_{m} ∩ T_{j} ≠ ∅.

Assume there exists p ∈ T_{2} ∩ R′_{m} such that p < x. Then R′_{m} ⊆ ↑p ∪ ↓x and ↑ p ⊆ T_{2} ∪ {x}, so that (Max P) \ {x} ⊆ T_{2}. Hence R′_{m} ∩ T_{3}∩ ↓ x ≠ ∅, so that (Max P) \ {x} ⊆ T_{3}. Hence Max P = {x}.

Case 2. For some j ∈ {1, …, s}, R′_{m} ∩ T_{j} = ∅.

Clearly j = 1. If x has no lower covers in R′_{m}, then R′_{m} is an antichain and we are done. Otherwise, let p ∈ R′_{m} be such that p ≺ x and {p, x} belongs to a chain of length ht P. Then for all y ∈ Max P, p ≺ y, and every lower cover of y is below x.

Now let q ∈ R′_{m} be a lower cover of x. For all y ∈ Max P, there exists z ∈ P such that q ≺ z ⩽ y and p < z, so that z = y. Therefore we may let R_{i} := R′_{i} (1 ⩽ i < m), R_{m} := R′_{m} \ Max P, and R_{m+1} := Max P. □

Theorem. Let P be a finite poset and T_{1}, …, T_{s} disjoint chains covering P (s ⩾ 3). Assume that, for all p ∈ T_{j}, q ∈ T_{k} such that p < q, P = ↑p ∪ ↓q whenever 1 ⩽ j, k ⩽ s and j ≠ k.

Then there exist subsets R_{1}, …, R_{n} of P such that P = R_{1} ⊕ ⋯ ⊕ R_{n} and, for i = 1, …, n, either

(1) R_{i} ∩ T_{j} = ∅ for some j ∈ {1, …, s}, or

(2) p ∥ q whenever p ∈ R_{i} ∩ T_{j}, q ∈ R_{i} ∩ T_{k}, and j ≠ k.

Proof. The theorem follows from the lemma by induction. □

The theorem will be generalized in a future note.

8. An open problem regarding chain decompositions of distributive lattices

Dilworth’s Theorem asserts that, for every width w poset, there exists a partition into w chains. Both practical and philosophically-minded persons might prefer an explicit construction for such a minimal partition.

It is clear that any partition of a ranked poset into symmetric chains is a minimal chain-partition. Such a decomposition also tells us that the width of the poset is the number of elements of height ⌊\frac{1}{2} ht P ⌋.

Examples of distributive lattices admitting such symmetric chain decompositions are finite power set lattices and lattices of divisors of positive integers [7].

Let L(m, n) denote the poset of m-tuples (x_{1}, …, x_{m}) where 0 ⩽ x_{1} ⩽ ⋯ ⩽ x_{m} ⩽ n, ordered as follows: (x_{1}, …, x_{m}) ⩽ (y_{1}, …, y_{m}) if x_{i} ⩽ y_{i} for i = 1, …, m. This poset is a distributive lattice. Figure 12 shows L(2, 3).

[figure: 00; 01; 02; 11; 03; 12; 13; 22; 23; 33]

Figure 12. The lattice L(2, 3).

Conjecture (Stanley). The lattice L(m, n) admits a symmetric chain decomposition.

It is known that the conjecture holds for L(3, n) and L(4, n) [15], [19], [24]; it is also known that the width of L(m, n) is indeed the number of elements of height ⌊\frac{1}{2} ht L(m, n)⌋, but the proof relies on heavy machinery from algebraic geometry ([22], §7). It would be interesting to have an elementary proof even of this fact.

9. Afterglow

“The Universe,” said the philosopher with a glint in his eye, “is a big place.” One might make a similar remark regarding the theory of ordered sets. What we have done is survey a tiny portion of the night sky. We hope that we have instilled in you, the reader, the desire to explore the constellations of lattice theory and the theory of ordered sets. Just perhaps, you may discover a star of your own.

References

1. Garrett Birkhoff, Lattice Theory, American Mathematical Society, Providence, Rhode Island, 1967.

2. Garrett Birkhoff and John von Neumann, The logic of quantum mechanics, Annals of Mathematics 37 (1936), 823–843.

3. Kenneth P. Bogart, Obituary: R. P. Dilworth, Order 12 (1995), 1–4.

4. B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, Cambridge, 1990.

5. David E. Daykin and Jacqueline W. Daykin, Order preserving maps and linear extensions of a finite poset, SIAM Journal on Algebraic and Discrete Methods 6 (1985), 738–748.

6. Jacqueline Wendy Daykin, Monotonic Functions of Finite Posets, Ph. D. Thesis, University of Warwick, 1984.

7. N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, and D. Kruyswijk, On the set of divisors of a number, Nieuw Archief voor Wiskunde 23 (1951), 191–193.

8. R. P. Dilworth, A decomposition theorem for partially ordered sets, Annals of Mathematics 51 (1950), 161–166.

9. Robert P. Dilworth, The Dilworth Theorems: Selected Papers of Robert P. Dilworth, Kenneth P. Bogart, Ralph Freese, and Joseph P. S. Kung (eds.), Birkhauser Boston, Inc., Boston, 1990.

10. B. Ganter and R. Wille, Formale Begriffsanalyse: Mathematische Grundlagen, Springer, 1996.

11. Ronald Gould, Graph Theory, The Benjamin/Cummings Publishing Company, Inc., Menlo Park, California, 1988.

12. R. L. Graham, Linear extensions of partial orders and the FKG inequality, Ordered Sets, Ivan Rival (ed.), D. Reidel Publishing Company, Dordrecht, Holland, 1982, pp. 213–236.

13. R. L. Graham, A. C. Yao, and F. F. Yao, Some monotonicity properties of partial orders, SIAM Journal on Algebraic and Discrete Methods 1 (1980), 251–258.

14. Henk J. A. M. Heijmans, Morphological Image Operators, Academic Press, Inc., Boston, 1994.

15. Bernt Lindström, A partition of L(3, n) into saturated symmetric chains, European Journal of Combinatorics 1 (1980), 61–63.

16. Zbigniew Lonc, Proof of a conjecture on partitions of a Boolean lattice, Order 8 (1991), 17–27.

17. Micha A. Perles, On Dilworth’s theorem in the infinite case, Israel Journal of Mathematics 1 (1963), 108–109.

18. H. A. Priestley, Ordered topological spaces and the representation of distributive lattices, Proceedings of the London Mathematical Society 24 (1972), 507–530.

19. W. Riess, Zwei Optimierungsprobleme auf Ordnungen, Arbeitsberichte des Instituts für Mathematische Maschinen und Datenverarbeitung (Informatik) 11 (1978).

20. Bill Sands, personal communication (1996).

21. Dana Scott, Data types as lattices, SIAM Journal on Computing 5 (1976), 522–587.

22. Richard P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM Journal on Algebraic and Discrete Methods 1 (1980), 168–184.

23. Shiojenn Tseng and Muh-Chyi Horng, Partitions of a finite three-complete poset, Discrete Mathematics 148 (1996), 205–216.

24. Douglas B. West, A symmetric chain decomposition of L(4, n), European Journal of Combinatorics 1 (1980), 379–383.

Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, California 94720

Department of Mathematics, Vanderbilt University, Nashville, Tennessee 37240

   E-mail address: farley@msri.org