검색
Article Search

JMB Journal of Microbiolog and Biotechnology

OPEN ACCESS eISSN 0454-8124
pISSN 1225-6951
QR Code

Article

Kyungpook Mathematical Journal 2020; 60(1): 1-20

Published online March 31, 2020

Copyright © Kyungpook Mathematical Journal.

On the Representations of Finite Distributive Lattices

Mark Siggers

Department of Mathematics, Kyungpook National University, Daegu 41566, Republic of Korea
e-mail : mhsiggers@knu.ac.kr

Received: January 24, 2017; Revised: January 16, 2020; Accepted: January 16, 2020

Abstract

Go to

A simple but elegant result of Rival states that every sublattice L of a finite distributive lattice ℘ can be constructed from ℘ by removing a particular family ℐL of its irreducible intervals.

Applying this in the case that ℘ is a product of a finite set of chains, we get a one-to-one correspondence between the sublattices of ℘ and the preorders spanned by a canonical sublattice of ℘.

We then show that L is a tight sublattice of the product of chains ℘ if and only if is asymmetric. This yields a one-to-one correspondence between the tight sublattices of ℘ and the posets spanned by its poset J(℘) of non-zero join-irreducible elements.

With this we recover and extend, among other classical results, the correspondence derived from results of Birkhoff and Dilworth, between the tight embeddings of a finite distributive lattice L into products of chains, and the chain decompositions of its poset J(L) of non-zero join-irreducible elements.

Keywords: finite distributive lattice, representation, embedding, product of chains.

1. Introduction

Go to

All lattices considered in this paper are finite and distributive. For very basic notation, definitions, and concepts we refer the reader to [4]; many basic definitions are also given at the start of Section 2.

Classical results of Birkhoff and Dilworth, which we review in more detail in Section 2, show that any finite distributive lattice L can be embedded, as a sublattice, into a product of chains. They further yield a one-to-one correspondence (Corollary 2.5) between the tight such embeddings and chain decompositions of the poset J(L) of non-zero irreducible elements of L.

Our main goal in this paper is to reverse the point of view of this correspondence: instead of cataloguing the various embeddings of a particular lattice L into products of chains, we catalogue the various sublattices of a given product ℘ of chains.

Starting with the product of a set of chains, J(℘) is the parallel sum of the chains we get from the chains of by removing their minimum elements. One main idea is that, for a tight sublattice L of ℘, J(L) is isomorphic to an extension of J(℘). See Figure 1 for an example. If we consider only tight sublattices of ℘, this is the whole picture: in Remark 4.4, we observe that L ↦ J(L) gives a one-to-one correspondence between the tight sublattices of ℘ and the spanned poset extensions of J(℘)–extensions with the same set of elements as J(℘).

But what if we consider non-tight embeddings/sublattices? One can see two examples of non-tight embeddings in the bottom half of Figure 2. As every lattice has a tight embedding into products of chains, non-tight embeddings are seldom considered. However, when we look to catalogue the sublattices of given product of chains, it is natural to consider them. In the paper [9], out of which this paper grew, we found it useful to consider non-tight sublattices of products of chains. We needed a characterisation of all sublattices of a product of chains.

In Section 3, we use a result of Rival [8] which characterises the sublattices of ℘, to construct, for each sublattice of ℘, a preorder (reflexive transitive relation) D℘(L) which contains J(℘). In fact, D℘(L) is a refinement of the poset that we get from J(℘) by appending a new zero and unit.

This preorder is an analogue of J(L) in the sense that our main theorem, Theorem 4.1 is an analogue of Theorem 2.1, representing L as the appropriatly defined lattice of ‘downsets’ of D℘(L). Using this, we prove Corollary 4.2 in Section 4, and so acheive our main goal of cataloguing the sublattices of ℘, by giving a correspondence between them and the so-called spanned preorder extensions of . Results similar to those is this section can by found with a different presentation in the recent article [7] of Retakh and Saks.

In Section 5, we return to the point of view of embeddings of a given lattice, and extend Birkhoff’s classical correspondence between the tight embeddings of a lattice L into products of chains and the chain decompositions of J(L). Birkhoff’s correspondence is categorical, and so is our extension, extending the correspondence between morphisms, but we avoid talk of categories. We get, in Theorem 5.3, a one-to-one correspondence between embeddings of a lattice L into products of chains, and ‘pointed chain covers’ of an extension J⋄(L) of J(L). Similar results can by found with a different presentation in the recent article [7].

In [5], Koh used a clever construction to show that any distributive lattice L can be represented as the lattice of maximal antichains of some poset P. We finish off, in Section 6, by showing that his construction arises naturally from our point of view, and extend it to determine, in Corollary 6.12, all posets P such that for a given L.

2. Notation and Background

Go to

A lattice embedding e : L → L′ is a {0, 1}-embedding if it preserves the zero and unit elements: e(0L) = 0L′ and e(1L) = 1L′. It is tight if it is a {0, 1}-embedding and preserves covers: x ≺ y implies that e(x) ≺ e(y). An element x of a lattice L is join-irreducible if x = a ∨ b implies that x = a or x = b. Meet-irreducible elements are defined analogously. The set of non-zero join-irreducible elements of L is denoted J(L). It induces a subposet of L which is also denoted by J(L). For a subset S of a lattice L, we let ∨S = ∨x∈S x be the join of the elements of S. We often write ∨L S to specify that the join takes place in L. A subset S of a poset is a downset or ideal if x ∈ S and y ≤ x implies y ∈ S. The minimum downset containing an element x is denoted 〈x]. A chain C of length n in a poset P is subposet isomorphic to the linear order Zn+1 on the n + 1 elements {0, 1, . . . , n}. A chain decomposition of a poset P is a partition of its elements into a family of chains C1, . . . , Cd. For a family of disjoint chains, the product ∏C:=∏i=1dCi consists of all d-tuples x = (x1, . . . , xd) where xi ∈ Ci for each i ∈ [d]. It is ordered by x ≤ y if xi ≤ yi for each i.

In his famous representation theorem in [1], Birkhoff showed that where , for a poset P, is the family of downsets of P ordered by inclusion. Specifically, he showed the following.

Theorem 2.1.([1])

Let L be a finite distributive lattice. The map

S:L→D(J(L)):x↦〈x]∩J(L)

is a lattice isomorphism. Its inverse is S ↦ → ∨L S.

Observing that a downset in is join-irreducible if and only if it has a unique maximal element, one can easily show that is an isomorphism. Thus P ≅ Q if . This immediatly yields a one-to-one correspondence, L ↦ J(L), between finite distributive lattices and finite posets.

For a chain decomposition of a poset let be the family of chains we get from the chains in by adding a new minimum element to each. In [2], Dilworth proved the following embedding theorem.

Theorem 2.2.([2])

For any chain decompositionof a poset P the map S ↦ ∨℘S is an embedding ofinto.

With Theorem 2.1, this immediately gives the following.

Corollary 2.3

For any decompositionof J(L) into chains, the map

eC:L→∏C0:x↦⋁℘S(x)

is an embedding of L into.

In [6], Larson makes explicit a converse to Corollary 2.3, showing essentially the following.

Theorem 2.4.([6])

The embeddingsof Corollary 2.3 are tight, and for every tight embedding e there is a chain decompositionof J(L) such that.

It is a trivial observation that different chain decompositions of J(L) yield different embeddings of L into products of chains, so with Corollary 2.3, this yields the following correspondence.

Corollary 2.5

Let L be a finite distributive lattice. The mapis a one-to-one correspondence between the chain decompositions of J(L) and the tight embeddings of L into products of chains.

3. The Rival Construction D℘(L)

Go to

Recalling a result of Rival in the first subsection, we use it in the second subsection to construct the preorder D℘(L) and the appropriate notion of a downset lattice. We then give an immediate restatement of Theorem 2.1 in terms of our new definitions. This will be a special case of our main theorem, which will be put off until the next section. In the third subsection, we look at some examples to try to give intuition to the construction. In the fourth subsection, we clean up some technical details of the construction.

3.1. Rival’s Theorem

An irreducible interval of a lattice L is the set [α, β] = {x ∈ L | α ≤ x ≤ β} for any join-irreducible element α of L and any meet-irreducible element β. For a set ℐ of irreducible intervals of L we let ∪ℐ = ∪I∈ℐI. The set ℐ is closed if I ⊆ ∪ℐ implies I ∈ ℐ. The key to our results is the following theorem of Rival.

Theorem 3.1.([8])

If L is a sublattice of a finite distributive lattice L′, then

L=L′⋃J

for some (closed) family ℐ of irreducible intervals of L′.

3.2. Setup and The Definition of D℘(L)

For the rest of the paper ℘ is always a product of finite chains . We will denote the elements of a chain Ci by integers, so that α + 1 will denote the cover of an element α in Ci; but we still refer to the maximum element of Ci as 1Ci. The subscript differentiates it from the element 1 that is occasionally used in examples to label the first or second element of a chain. We let 0 = (0C1, . . . , 0Cd) and 1 = (1C1, . . . , 1Cd) denote the zero and unit of ℘. When L is a sublattice of ℘, Theorem 3.1 yields a unique closed family ℐL such that L = ℘ ℐL. The join-irreducible elements of ℘ are clearly of the form

αi=(α)i:=(0C1,0C2,…,0Ci-1,α,0Ci+1,…,0Cd)

for i ∈ [d] and α ∈ Ci and the meet-irreducible elements are

βj=(β)j:=(1C1,1C2,…,1Cj-1,β,1Cj+1,…,1Cd)

for j ∈ [d] and β ∈ Cj. We generally use the notation αi and βj but add the parentheses when needed for clarity, in particular, we do this when α has or β has a subscript. The irreducible intervals of ℘ are exactly the intervals [αi, βj] for i, j ∈ [d], α ∈ Ci, and β ∈ Cj, where α ≤ β if i = j. Though an empty set is not technically an interval of a poset, it will be useful to consider the empty set [αi, βi], when α > β, as an irreducible interval of ℘.

Given and , let be the subposet of ℘ induced by J(℘) ∪ {0, 1}. Occasionally, in arguments, we will let (α + 1)i refer to 1 when α = 1Ci. This is consistant with viewing 1 as a new unit of Ci. Dually, we will occasionally let (β − 1)j refer to 0 when β = 0Cj. These shortcuts will help us avoid having to deal seperately with the extremal cases of α and β in arguments.

Recall that a poset, and in particular , is a reflexive relation. We refer to a reflexive relation simply as a reflexive digraph, and view posets as reflexive digraphs, saying (x, y) is an arc, or writing x → y, to mean x ≤ y. A spanned extension of is any digraph on the elements of , which contains it. A preorder is a transitive reflexive digraph.

The following is our extension of J(L), we chose to label it with a D rather than a J to emphasise the fact that it is a digraph, and not necessarily a poset.

Definition 3.2. (D℘(ℐ) and D℘(L))

For any family of chains and any family of irreducible intervals ℐ of , let D℘(ℐ) be the spanned extension of that we get from by letting (β + 1)j → αi for each [αi, βj] ∈ ℐ. For a sublattice L of ℘, let D℘(L) = D℘(ℐL).

An (x, y)-path v1 → v2 → · · · → vℓ in a digraph D is a sequence of elements x = v1, v2, . . . , vℓ = y such that vi → vi+1 for each i. The following is a straightforward extension, to digraphs, of the definition of downset of a poset.

Definition 3.3

A subset S ⊆ D of vertices of a digraph D is a downset (or an initial set) if for all y in S and all (x, y)-paths in D, x is also in S. A downset set S of D is a non-trivial downset if it is a non-empty proper subset of D. For a vertex x of D let 〈x] be the smallest downset of D containing x.

Definition 3.4. ( and )

For any digraph D, let be the family of downsets of D ordered by inclusion, and be the subfamily of non-trivial downsets.

As with posets, it is clear for digraphs that unions and intersections of downsets are downsets, so is indeed a poset for any digraph D. In ourmain theorem we will see that is, in fact, the lattice L when D is the spanned extension D℘(L) of .

For a poset P let P∨ be the poset we get from P by adding a new minimum element and let P⋄ be the poset we get from P∨ by adding a new maximum element. It has been observed in several places, (see, for example, [6]), that

Dnt(P⋄)≅D(P).

Indeed, the isomorphism is the map that drops the appended unit. As implies P ≅ P′ we have

Dnt(P⋄)≅Dnt(Q⋄)⇒P⋄≅Q⋄.

With (3.1), the following base case of our main theorem is immediate from Theorem 2.1. It will also be clear from the top example in Figure 2 of the next subsection.

Lemma 3.5

Where ℘ is a product of chains, the map

T:℘→Dnt(C⋄):x↦〈x]∩C∨

is an isomorphism. Its inverse is S ↦ ∨℘S.

Proof

Indeed ℘ is a lattice, so we may apply Theorem 2.1, and then (3.1), to get the isomorphism

℘≅D(J(℘))≅Dnt(J⋄(℘))=Dnt(C⋄).

Before we prove our main theorem, that T is an isomorphism from L to for any sublattice of ℘, we will need, in Proposition 3.7 to show that because ℐL is closed, D℘(L) is a preorder.

First though, let’s explain our definition of D℘(L) with a couple of examples.

3.3. Some Examples

Go to

A directed graph that extends a poset can be depicted by adding arcs to the Hasse diagram of the poset, though direction must be made explicit on these arcs, as they need not all go up. As the digraphs D℘(L) that we depict thus will be preorders, so transitive, we maintain the convention of not drawing the transitively impied arcs.

The top half of Figure 2 shows the same lattices ℘ = Z5×Z6 and L1 = ℘[32, 21] as are shown in Figure 1, but now, instead of J(℘) and J(L1), it shows with them the digraph and its spanned extension D℘(L1).

The construction of D℘(L) arises from observing what we must do to so that T remains an isomorphism when we remove some irreducible interval [αi, βj] from ℘. Referring to the second example in Figure 2, when we remove [32, 21] from ℘, we see that we should add the 32 ≥ 31 to to maintain the isomorphism. Indeed, this ensures that, for example, the set T((2, 3)) = {21, 11, 0, 12, 22, 32} is no longer a downset. In general it ‘kills’ any downset S containing 32 but not 31. These are exactly the downsets T(x) for x ∈ [32, 21].

The third example in the figure shows a non-tight sublattice L2 of ℘, observe that the corresponding extension D℘(L2) of is not a poset. The fourth example exhibits the necessity of 0 and 1 in D℘.

3.4. The Closure of ℐ and Transitivity of D℘(ℐ)

Go to

In this subsection we show that D℘(ℐ) is closed if and only if ℐ is transitive. It is a pretty intuitive notion, but we prove it via a technical lemma that we be quite useful later.

Recall that we included the empty intervals of the form [αi, βi], where α > β, as irreducible intervals of . By definition then, these are thus contained in any closed family ℐ of irreducible intervals. This is consistant with D℘(ℐ) containing . In particular, we assume for any sublattice L of ℘ that the closed family ℐL such that L = ℘ ∪ℐL provided by Theorem 3.1, contains these elements.

Now our technical lemma.

Lemma 3.6

Let D = D℘(ℐ) for some sublattice L = ℘ ∪ℐ of. The following are equivalent forand.

  • [αi, βj ] ⊆ ∪ℐ.

  • For all x ∈ L, xi ≥ α ⇒ xj > β.

  • There is a ((β + 1)j, αi)-path in D.

Proof

The equivalence of (i) and (ii) is immediate as both are equivalent to the statement that there are no elements x ∈ L with α ≤ xi and xj ≤ β. So we show the equivalence of (ii) and (iii).

On the one hand, consider an ((β +1)sℓ, (α1)s1)-path in D. As ℐ is assumed to contain all empty intervals, we can write this as

(β+1)sℓ=(αℓ)sℓ→⋯→(α2)s2→(α1)s1.

By the definition of D this means that [(αi)si, (αi+1 − 1)si+1] ∈ ℐ for each i. Let x ∈ L be such that xs1 ≥ α1. By the equivalence of (i) and (ii) this implies xs2> α2 − 1, which in turn implies xs3> α3 − 1, etc., until we get that xsℓ> αℓ −1 = β, as needed.

On the other hand, assume that there is no such path from (αℓ)sℓ to (α1)s1. We will find x in L with xs1 ≥ α1 and xsℓ< αℓ = β + 1. Indeed, for k ∈ [d] let xk be the maximum value for which there is a path in D from (xk)k to (α1)s1. If no such path exists, let xk be 0. Clearly xs1 ≥ α1, and by the assumption that there is no path from (αℓ)sℓ to (α1)s1 we have that xsℓ< αℓ. We have just to show that x is in L.

If x is not in L, then it is in some [(α)i, (β)j ] ∈ ℐ. As [(α)i, (β)j ] ∈ ℐ, we have that (β + 1)j → (α)i is in D. As x ∈ [(α)i, (β)j], we have that α ≤ xi and xj ≤ β. Now by the choice of x, α ≤ xi implies that there is an path from (α)i to (α1)s1, so the arc ((β+1)j, (α)i) gives us a path from (βj+1)sj to (α1)s1. But then βj+1 ≤ xj which contradicts xj ≤ βj.

As ℐL is closed, the following proposition allows us to assume that the digraph D℘(L), for any sublattice L of ℘, is a preorder.

Proposition 3.7

Let D = D℘(ℐ) for some sublattice ℘∪ℐ of ℘. Then ℐ is closed if and only if D is transitive.

Proof

On the one hand, assume that ℐ is closed. Then we can replace (i) of Lemma 3.6 with [αi, βj ] ∈ ℐ. Now that γk → βj and βj → αi in D gives, by Lemma 3.6, that [αi, γk] ∈ ℐ which means γk → αi in D. So D is transitive.

On the other hand, assume that ℐ is not closed. Then there is some [αi, βj] in ∪ℐ but not in ℐ. So there is a (αi, βj)-path in D, while (αi, βj) is not in D.

4. Main Results

Go to

In this section we give our main results corresponding the sublattices of product of chains to the spanned preorder extensions of . In the first subsection, we give our main theorem, extending Birkhoff’s representation theorem from J(L) to the more general construction D℘(L). In the second subsection, we explicitly state the one-to-one correspondence. In the final subsection, we classify the sublattices of ℘ in terms of the properties of the corresponding preorder extensions.

4.1. Main Theorem

Generalising Theorem 2.1 we have the following.

Theorem 4.1

Let L be a sublattice of a productof chains, and let D = D℘(L). The map

T:L→Dnt(D):x↦〈x]∩C⋄

is a lattice isomorphism. Its inverse is S ↦ ∨℘S.

Proof

As it simplifies induction, we prove the slightly more general result that T is an isomorphism for D = D℘(ℐ) where ℐ is any family of irreducible intervals of ℘ such that L = ℘ ∪ℐ. In the case that ℐ is empty, or contains only empty families, we have L = ℘ and , so the isomorphism is given in Lemma 3.5.

In the general case, we first observe that is a subposet of . Indeed, as D ia a spanned extension of , any downset of D is a downset of , so is a subset of . Since both are ordered by inclusion .

Now it is enough to show that a bijection. We do this by induction on the size of ℐ. Let [αi, βj ] ∈ ℐ, ℐ′ = ℐ[αi, βj ], L′ = ℘ ∪ℐ′, and D′ = D℘(ℐ′). By induction we have that is a bijection.

We must show for , that if and only if x ∈ [αi, βj ]. Now T(x) being a downset in D′, but not in D which we get from D′ by adding the arc ((β + 1)j, αi), means exactly that αi ∈ T(x) and (β + 1)j ∉ T(x). This is to say α ≤ xi but (β + 1) > xj, which means that x ∈ [αi, βj ], as needed.

To see that T−1 = S ↦ ∨℘S just observe that T is defined by its definition on irreducible elements, and for irreducible x, the downset is the principle downset in , so

⋁℘〈x]∩C⋄=⋁℘〈x]C⋄=⋁C⋄〈x]C⋄=x.

4.2. One-to-one Correspondence

Go to

By Theorem 4.1 we have that any sublattice of ℘ can be expressed as the lattice of non-trivial downsets of some spanned extension D of . On the other hand, it is clear that for a spanned extension D of the family

JD={[αi,βj]∣((β+1)j,αi)∈DC⋄}

is such that is the sublattice ℘ ∪ℐD of ℘. While several digraphs D may yield the same sublattice of ℘, as may families of intervals have the same union, it is clear that there is a unique closed family of intervals defining a given sublattice. So by Proposition 3.7 we get the following.

Corollary 4.2

Letbe a product of chains. The map L ↦ D℘(L) gives a one-to-one correspondence between the sublattices of ℘ and the spanned preorder extensions of.

This solves one of our main goals, ‘reversing the point of view’ of correspondence given in Corollary 2.5.

4.3. Classification of Sublattices

Go to

Recall that a sublattice L of ℘ is a {0, 1}-sublattice if it contains the extremal elements 0 and 1 of ℘. It is subdirect if for each i ∈ [d], the projection πi : L → Ci is surjective; this is necessarily a {0, 1}-sublattice. A {0, 1}-sublattice is tight if its covers are covers of ℘.

It was shown in [6] that every tight sublattice of a product of chains is subdirect. The converse was also claimed, but the proof was flawed: indeed, the lattice L = Z3 × Z3 ([21, 12] ∪ [22, 11]) shown in Figure 3 is a subdirect sublattice of Z3 × Z3, but not tight. One notices in this example that D℘(L) has a cycle. We will see that this is indicative of non-tight sublattices.

The height of a finite lattice is the maximum number of elements in chain of the lattice. It is well known that for a distributive lattice, every cover is in a maximum chain. It follows that a sublattice L of ℘ is tight if and only if L and ℘ have the same height. An arc (x, y) in a digraph D is an in-arc of y and an out-arc of x.

Lemma 4.3

Let L be a sublattice of ℘ and D = D℘(L).

  • L is a {0, 1}-sublattice if and only if0is a source (has no in-arcs) in D and1is a sink (has no out-arcs).

  • L is subdirect if and only if D has no down edges: those of the form αi → (α − 1)i.

  • L is tight if and only if D is a poset.

Proof

We have by Theorem 4.1 that is an isomorphism.

  • Clearly T(0) = {0} is a downset of D if and only if 0 is a source in D. Just as clearly, is a downset if and only if 1 is a sink. The result follows.

  • We have αi → (α − 1)i in D if and only if there is no downset T(x) of D containing (α−1)i but not αi. This is if and only if there is no element x ∈ L such that xi = α − 1.

  • First assume that L is tight, and assume, towards contradiction that D contains a cycle (α1)i1 → (α2)i2 · · · → (αℓ)iℓ → (α1)i1, for some ℓ ≥ 2. We show that no vertex x in L has xi1 = α1, which contradicts the fact that L is tight. Indeed, if x did have xi1 = α1, then xi1 ≥ α1 so by Lemma 3.6 xi2> α2 so xi3> α3 etc., and we get that xi1> α1, a contradiction.

On the other hand, assume that D has no cycles. Then its vertices can be ordered so that all arcs go up. Visiting vertices from the bottom of this ordering, one at a time, we get an ascending walk in from 0 to 1 of size |D|, showing that L has height equal to the height of ℘. Thus L is a tight sublattice.

Remark 4.4

Though our goal was a correspondence including all sublattices of a product ℘ of chains, there is some satisfication in restricting now to {0, 1}-sublattices so that the sublattices are corresponded to spanned extensions of J(℘) rather than of .

For any preorder D with named elements 0 and 1, let D* be the subgraph induced by D {0, 1}. For a {0, 1}-sublattice L of ℘ it is a simple matter to extend (3.1) and show that the map Dnt(D℘(L))→D(D℘*(L)):S↦S{1} is an isomorphism. Composing this with , Theorem ?? tells us that

S:L→D(D℘(L)*):x↦〈x]∩C

is a lattice isomorphism. When L is a tight sublattice of ℘, we have by Lemma 4.3 that D℘(L), and so D℘(L)*, is a poset. It follows that D℘(L)* = J(L) in this case. So this restriction of Theorem 4.1 is even symbolically an extension of Theorem 2.1.

Observing that a spanned extension D℘(L) of yields a spanned extension D℘*(L)

of , Corollary 4.2 says that the map L↦D℘*(L) gives a one-to-one correspondence between the {0, 1}-sublattices of ℘ and the spanned preorder extensions of J(℘). Tight sublattices of ℘ correspond to spanned poset extensions of J(℘).

5. Back to Embeddings

Go to

We would now like to extend Corollary 2.5 by fixing a finite distributive lattice L, and cataloging all embeddings into products of chains. An embedding e : L → ℘, defines a sublattice e(L) of ℘ so gives, by Corollary 4.2, a preorder extension D = D℘(e(L)) of such that . But as neither D or are canonical for L, this is a little unwieldy for our purposes. Luckily all such D have a canonical quotient that turns out to be J(L). Viewing an extension D of rather as a bijective homomorphism , we get a surjective homomorphism of by passing to the quotient. As such, every embedding e of L into a product of chains corresponds to a surjective homomorphism of some structure to J(L). Giving the proper definitions now, we show in this section that this correspondence is one-to-one.

A pointed union of chains is any poset that can be represented as for some product of chains. (Recalling this construction, we get a pointed union of chains from the parallel sum of the chains of a family of chains by appending a new zero 0 and unit 1. A homomorphism (relation preserving map) of a pointed union of chains to a preorder D is a pointed chain cover if it is surjective, and a pointed chain decomposition if it is bijective.

5.1. The Canonical Quotient of D℘(L)

The non-preference relation ’~’ defined on a preorder D by letting x ~ y if x and y are in a directed cycle, is an equivalence relation. The quotient D̃ := D/~ is well known to be a poset. Classes of D̃ satisfy [a] ≤ [b] if and only if a ≤ b. The quotient homomorphism q : D → D̃ : a ↦ [a] induces set maps between the power-sets 2D and 2D̃ of D and D̃. For T ⊆ D, we let [T] := {[x] | x ∈ T} ⊆ D̃, and for S ⊆ D̃ we let ∪S = ∪[x]∈S[x].

Lemma 5.1

Let D be a preorder, thenis an isomorphism with inverse S ↦ ∪S. Thus D̃ ~= J⋄(L), where.

Proof

As [x] contains only elements in the downset of x, for a downset T, [T] is a partition of T and so is a downset of D̃. Thus T ↦ [T] is a well-defined map from to , and S ↦ ∪S is its inverse. As T → [T] is clearly a bijection, it is also the inverse of S ↦ ∪S. That it preserves order is also clear as the order on both posets is inclusion, and [T] partitions T with respect to an underlying fixed partition of D.

As , the second fact follows by (3.2).

Now for any pointed chain decomposition of a preorder D we get a surjective homomorphism by composing with the quotient map. And while the quotient map q : D → D̃ : a ↦ [a] is not invertible, the homomorphism φ̃ tells us what elements were identified in passing from D to D̃. As identified elements induce a complete digraph in the transitive digraph D, we can uniquely resolve the pair (φ̃, D̃) back to the pair (φ, D) they came from.

Thus we have the following.

Fact 5.2

The map (φ, D) ↦ (φ̃, D̃) is a one-to-one correspondence between pointed chain decompositions of preorders, and pointed chain covers of posets.

5.2. The Full Correspondence Extending Corollary 2.5

Go to

Fix a lattice L and let J⋄ = J⋄(L). An embedding e : L → ℘ of L yields by Corollary 4.2 a spanned preorder extension D = D℘(e(L)) of , which we view as a pointed chain decomposition ϕe′:C⋄→D. Extending this by the quotient q : D → D̃ gives a homomorphism of a pointed union of chains to D̃ = J⋄.

Using the isomorphism that we get from Theorem 4.1, we will see that we can write φe explicitly as

φe-1(x)=(〈e〈x]]℘〈e〈x)]℘)∩C⋄.

On the other hand, for any surjective homomorphism from a pointed union of chains, we get, by Fact 5.2, a unique pointed chain decomposition of a preorder D such that φ = q ∘ φ′ and D̃ = J⋄. By Lemma 5.1 we have and Theorem 4.1 gives us an embedding

T-1:Dnt(D)→℘:S↦⋁℘(φ′)-1(S)

of L into ℘, wherewewrite (φ′)−1(S) in place of S as S is only considered a subset of ℘ via the bijection φ′. As q induces an isomorphism , this is an embedding

eφ:=(T∘q)-1:Dnt(J⋄)→℘:S↦⋁℘φ-1(S)

of L into a product of chains.

We are ready for our generalisation of Corollary 2.5. Recall that a pointed chain cover of J⋄(L) is a surjective map from a pointed union of chains to J⋄(L).

Theorem 5.3

For any finite distributive lattice L, the maps e → φe and φ → eφ defined in equations(5.1) and(5.2) give a one-to-one correspondence between pointed chain covers of J⋄(L), and embeddings ofinto products of chains.

Proof

It is enough to show that the maps e → φe and φ → eφ are inverses. For a downset S of J⋄ we have that φe-1(S)=⋃x∈Sφe-1(x). But this is just , because anything in 〈e 〈x)]℘ is in 〈e 〈x′]]℘ for some other x′ ∈ S. It follows that e = eφe ; indeed, recalling for the last equality that and S → ∨S are inverse :

eφe〈x]=⋁φe-1〈x]=⋁〈e〈x]]℘∩C⋄=e〈x].

To see that φeφ = φ, let x be in J⋄. Using in the third line that 〈p]℘ 〈p)℘ = p for any p, we get

φeφ-1(x)=(〈eφ〈x]]℘〈eφ〈x])℘)∩C⋄=(〈⋁φ-1〈x]∣℘〈⋁φ-1〈x])℘)∩C⋄=(⋁φ-1〈x])∩C⋄=φ-1(x).

Remark 5.4

When removing 0 and 1, it is not hard to see that this yields a one-to-one correspondence between full embeddings of L into product of chains, and chain covers of J(L)–surjective homomorphisms from a disjoint unions of chains to J(L). Subdirect embeddings yield homomorphisms that are injective on each chain; and tight embeddings correspond with bijections–so-called chain decompositions.

6. Lattices of Independent Sets

Go to

Adjusting our construction, we extend and complement results of Koh from [5].

6.1. Background

The correspondence taking a downset of a poset P to its subset of maximal elements gives one-to-one correspondence between the downsets of P and the antichains of P. It is not hard to see that by defining the following ordering on , the correspondence can be extended to a lattice isomorphism: for antichains I, , set I ≤ I′ if for all a ∈ I there is some a′ ∈ I′ such that a ≤ a′. The width of a poset is the size of its maximum antichain. In [3], Dilworth, using his famous chain decomposition theorem to decompose a poset P of width d into d chains, showed the following.

Theorem 6.1.([3])

The posetof all maximum sized antichains of a poset P is a distributive lattice.

In [5], Koh showed a converse: every finite distributive lattice L is for some poset P. In doing so he showed something stronger. Koh defines a construction which yields a poset for every chain decomposition of the poset J(L). He then showed the following.

Theorem 6.2.([5])

For every finite distributive lattice L, and every chain decompositionof J(L), .

There are posets P for which that are not accounted for by Koh’s construction. A small alteration of the reverse point of view of this paper yields a simple generalisation of Koh’s construction. With this we show that every poset P for which arises from a chain cover of J(L). In fact, the generalisation gives a digraph in place of P for every embedding of L into a product of chains, and this digraph is a poset if and only if the embedding is subdirect.

The alteration of the reverse pont of view yields transitive digraph extensions of a union of tournaments rather than preorder extensions of a pointed union of sets. We start with definitions required to define the antichain lattice of such digraphs.

6.2. Definitions and Setup

A directed path x1 → x2 → ·· ·→xd in a digraph is non-trivial if d ≥ 2. Note that a loopless vertex induces a trivial path, while a vertex x with a loop induces the non-trivial directed path x → x.

Definition 6.3

A subset I of a digraph D is independent if there is no non-trivial xy-path in D for x and y in I.

This is a much stronger notion of independence than is usually defined for digraphs, it implies independence in the transitive closure of the graph. In fact, no vertex that is in a cycle, including a looped vertex, can be in an independent set.

Definition 6.4.( )

Let be the family of independent sets of size d of a digraph A, and order it as follows. For I, , let I ≤ I′ if for each a′ ∈ I′ there is an aa′-path in A with a ∈ I.

Remark 6.5

For a poset P let A be transitive acycle digraph that we get from P by removing loops. It is easy to see that when d is the width of P. As it will simplify exposition, we will translate Koh’s results into our notation, and remind the reader of this by saying he essentially proved such and such.

Our basic setup now is as follows. Given a product of a family of d chains, will be the (disjoint) union of tournaments we get from the parallel sum of the chains in by removing the loops from all vertices. As we will now be referring to elements of a chain Ci individually, we afix a superscript, for example, denoting the element 3 or xj, of Ci by 3(i) or xj(i) respectively. For a vertex x = (x1, . . . , xd) of ℘, let Ix be the set

Ix:={x1(1),…,xd(d)}.

By Remark 6.5 the d element independent sets of are exactly Ix for x ∈ ℘.

A digraph A is a spanned extension of if is a spanning subgraph of A. For such digraphs all d-element independent sets are of the form Ix, and so the ordering on defined in Definition 6.4 has a simpler definition, essentially observed in [5] in the case that A is a poset.

Lemma 6.6

Let A be a spanned extension of a unionof d tournaments. For Ix, Iy ∈ , we have Ix ≤ Iy if and only xi ≤ yi for all i.

Proof

The ‘if’ direction is immediate from Definition 6.4 as all arcs of are in A. For the ‘only if’ direction, assume that Ix ≤ Iy, and let i ∈ [d]. We must show that xi ≤ yi. Assume that it is not, so yi < xi, and so there is a directed path in A from yi to xi. As Ix ≤ Iy there is a path in A from xi to yj for some j ∈ [d]. If i = j the xi and yi are in a directed cycle, contradicting the fact that xi is in an independent set. If i ≠ j then there is a path from yi to xi and one from xi to yj, contradicting the fact that yi and yj are in an independent set.

From here, given a digraph D of appropriately defined width d, it is not hard, adapting Dilworth’s chain decomposition theorem to digraphs to find as a spanning subgraph a union of d tournaments. Then one can prove that the set is a lattice under the above ordering. We will use Dilworth’s chain decomposition in this way in Corollary 6.11, but for now we follow our reverse point of view, and relate such digraphs D to sublattices of a given product of chains.

6.3. The Alternate Rival Construction A℘(L)

Go to

Compare the following to Definition 3.2.

Definition 6.7. (A℘(ℐ) and A℘(L))

For a family of chains and any family of irreducible intervals ℐ of , let A℘(ℐ) be the spanned extension of that we get from by letting β(j) → α(i) for each [αi, βj ] ∈ ℐ. For a sublattice L of ℘, let A℘(L) = A℘(ℐL).

See Figure 4 for examples of A℘(L) corresponding to the sublattices L of ℘ in Figure 2. The digraph A℘(L) is still the transitive closure of the depicted digraph, where all unoriented arcs are oriented up, but it is no longer reflexive. Note that in the fourth figure in Figure 4 corresponding to L3 = ℘ [32, 41], we have both of the arcs (4(1), 3(2)) and (5(2), 3(2)), as the intervals [32, 41] and [32, 52] are the same. The graphs in Figure 4 are all irreflexive except A℘(L3) which, because it is transitive, has loops on the vertices 3(2), 4(2), and 5(3).

It is easy to see that where is the first picture in Figure 4. This an example of the base case of Theorem 6.8. To prove Theorem 6.8 we simply observe what we must do to to maintain this isomorphism when we remove an irreducible interval from ℘. Remove the interval [31, 32] as we do to get the second lattice L2 = L1 [31, 32] of Figure 2. The second figure of Figure 4 shows what we must add to . To ensure that, for example, I(2,3) = {2(1), 3(2)} is no longer independent, we add the arc (2(1), 3(2)) to . This also ensures that such sets as I(2,4) and I(1,5) are no longer independent.

Theorem 6.8

Let L be a sublattice of, whereis a family of disjoint chains, and let A = A℘(L). The map

I:L→Ad(A):x↦Ix:={x1(1),…,xd(d)}

is a lattice isomorphism.

Proof

The theorem holds by Lemma 6.6 in the simplest case where L = ℘ and so . We proceed by induction on the size of A, by adding arcs. As adding arcs to or any spanned extension cannot not create new independent sets, we have that is a subset of ℘ = ; and so by Lemma 6.6 it is a subposet.

Thus it is enough to show, inductively, that is a bijection. We must show that an independent set is not in if and only if x is in [αi, βj ]. That is, we must show that if and only if xi ≥ α and β ≥ xj. For , clearly if and only if (β(j), α(i)) completes a path between xj and xi, so if and only if xi ≥ α and β ≥ xj, as needed.

Observe that this is essentially a generalisation of Koh’s Theorem 6.2. Indeed, as a tight embedding of L into a product of chains ℘ corresponds to a chain decomposition of J(L) by Corollary 4.2 and Remark 4.4, Theorem 6.8 gives, for any chain decomposition of J(L), a digraph A such that . As Dilworth’s decomposition theorem assures there is such a decomposition when d is the width of J(L), this essentially gives Theorem 6.2.

We continue, and complement Theorem 6.2 by finding every poset P such that . As per Remark 6.5, this is done by finding every acyclic transitive graph A such that . The main elements required are anti-chain analogues of Corollary 4.2 and Lemma 4.3. Instead of ‘repeating’ the proofs of these earlier sections, we observe that the anti-chain analogues follow from the results of Section 4 by comparing the constructions of D℘(A) and A℘(L).

6.4. Properties of A℘(L) via Koh’s Construction

Go to

Comparing definitions, or comparing Figure 2 to Figure 4, it is easy to see how to get A℘(L) directly from D℘(L). Indeed for a spanned preorder extension D of , let A = K℘(D) be the digraph on the vertices of with arcset

{(β(j),α(i))∈J2∣((β+1)j,αi)∈D}.

One can easily check that , and more generally that K℘(D℘(ℐ)) = A℘(ℐ) for any closed family ℐ of irreducible intervals. (We require that ℐ is closed for this as an out-arc of 1 in D yields several arcs in K℘(D), as is seen in the fourth figure in Figure 4).

It is a simple matter to show the transitivity of K℘(D) from that of D, and so get from Proposition 3.7 that A℘(ℐ) is transitive if ℐ is closed. Observing that the construction D ↦ K℘(D) invertible when considering only transitive extensions A of , (i.e. tournament decompositions of A) we see that its inverse is essentially a generalisation of Koh’s construction from [5]. The only difference is that Koh’s construction would always have loops on . As he considered only posets, this difference would be cosmetic for him, but it is significant for us. The construction can be used to easily translate statments about D℘(L) to statements about A℘(L). We give two examples, omitting the simple proofs.

Using Corollary 4.2, we get the following analogue.

Corollary 6.9

Letbe product of chains. The map L ↦ A℘(L) gives a one-to-one correspondence between the sublattices of ℘ and the spanned transitive digraph extensions of.

The classification lemma, Lemma 4.3, yields the following analogue.

Lemma 6.10

Let L be a sublattice of ℘ and A = A℘(L).

  • L is a {0, 1}-sublattice if and only if the minimum and maximum element of each tournament T inare loopless in A.

  • L is a subdirect sublattice if and only if A is loopless, which holds if and only if contains no directed cycles.

  • L is a tight sublattice if and only if A contains no directed cycle or alternating cycle: v1 → u1 ← v2 → u2 ← ·· ·→uℓ ← v1.

For tight sublattices L we have that D℘(L) = J⋄ (L) and so A = K℘(J⋄). An important part of Koh’s proof from [5] was that his version of K℘(J⋄) contains no crown, which is essentially what item (iii) says.

6.5. Complement to Koh

Go to

For a lattice L, and an embedding e of L into a product ℘ of chains, Theorem 5.3 gives a pointed chain cover . This gives, by Fact 5.2, a pointed chain decomposition of some preorder De with D℘(De) = L. Viewing De as a preorder extension of , we can apply construction K℘(J⋄ (L)) to get a transitive digraph extension Ae = K℘(De) of . By Theorem 6.8 we have . In particular, if the embedding e was subdirect, then by Lemma 6.10 Ae is essentially a poset–we simply have to add loops to get Koh’s poset.

As a complement to Koh’s theorem, we want to show that for any poset P such that , there is some e such that Ae is P with loops removed. More generally, we have the following.

Corollary 6.11

Let L be a finite distrubitive lattice. For any transitive digraph A such thatwhere d is the width of A, there is an embedding e of L into a product of chains ℘ such that A = Ae.

Proof

Let A be a transitive digraph with . The main task is to find a tournament decomposition of A into d tournaments.

Where Ar is the preorder we get from A by making it reflexive, and P = q(Ar) is the poset we get by quotienting by the non-preference relation, we have by Dilworth’s Decomposition Theorem that P has a decomposition into d chains. Removing loops from , we alter φ ′ to a tournament cover φ̃ of P so that it lifts to a tournament decomposition φ of A by Fact 5.2, which clearly holds with loops removed. This is easy: for any vertex such that φ′(x) = [y], add |[y]|–1 new elements to C just above x and let φ̃ map x and all of these vertices to [y]. By Fact 5.2 (φ̃, P) lifts to some (φ, A′) where to get A′ we replace an element y of P with a transitive cycle of size q−1(y). So A′ = A, and φ is a tournament decomposition of A. Thus A = Aeφ where eφ is the embedding of L we get by Theorem 5.3.

Corollary 6.12

For every finite poset P such thatthere is a subdirect embedding of L into a product of chains ℘ such that P=A℘r(L).

Fig. 1. Product of chains ℘, sublattice L, and their posets J(℘) and J(L)
Fig. 2. Sublattices of ℘ = Z5 × Z6 and their digraphs D℘
Fig. 3. Non-tight subdirect sublattice of Z3 × Z3
Fig. 4. Digraphs A℘ for sublattices of ℘ = Z5 × Z6 from
  1. G. Birkhoff. Rings of sets. Duke Math J., 3(3)(1937), 443-454.
    CrossRef
  2. R. Dilworth. A decomposition theorem for partially ordered sets. Ann of Math., 51(1950), 161-166.
    CrossRef
  3. R. Dilworth. Some combinatorial problems on partially ordered sets. Proc Sympos Appl Math, 10, (1960), 85–90.(American Mathematical Society, Providence, R. I.)
    CrossRef
  4. G. Grätzer. Lattice theory: foundation, , Birkhäuser/Springer Basel AG, Basel, 2011.
    CrossRef
  5. KM. Koh. On the lattice of maximum-sized antichains of a finite poset. Alg Universalis., 17(1983), 73-86.
    CrossRef
  6. RN. Larson. Embeddings of finite distributive lattices into products of chains. Semi-group Forum., 56(1998), 70-77.
    CrossRef
  7. V. Retakh, and M. Saks. On the rational relationships among pseudo-roots of a non-commutative polynomial., arXiv:2001.04856 [math.RA].
  8. I. Rival. Maximal sublattices of finite distributive lattices II. Proc Amer Math Soc., 44(1974), 263-268.
    CrossRef
  9. M. Siggers. Distributive lattice polymorphisms on reflexive graphs. Bull Korean Math Soc., 55(2018), 81-105.