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
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
A simple but elegant result of Rival states that every sublattice
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
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
Keywords: finite distributive lattice, representation, embedding, product of chains.
1. Introduction
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
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
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
Starting with the product of a set of chains,
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
In Section 3, we use a result of Rival [8] which characterises the sublattices of ℘, to construct, for each sublattice of ℘, a
This preorder is an analogue of
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
In [5], Koh used a clever construction to show that any distributive lattice
2. Notation and Background
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
A lattice embedding
In his famous representation theorem in [1], Birkhoff showed that where , for a poset
Theorem 2.1.([1])
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
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])
With Theorem 2.1, this immediately gives the following.
Corollary 2.3
In [6], Larson makes explicit a converse to Corollary 2.3, showing essentially the following.
Theorem 2.4.([6])
It is a trivial observation that different chain decompositions of
Corollary 2.5
3. The Rival Construction D ℘(L )
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
Recalling a result of Rival in the first subsection, we use it in the second subsection to construct the preorder
3.1. Rival’s Theorem
An
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
for
for
Given and , let be the subposet of ℘ induced by
Recall that a poset, and in particular , is a reflexive relation. We refer to a reflexive relation simply as a
The following is our extension of
For any family of chains and any family of irreducible intervals ℐ of , let
An (
A subset
For any digraph
As with posets, it is clear for digraphs that unions and intersections of downsets are downsets, so is indeed a poset for any digraph
For a poset
Indeed, the isomorphism is the map that drops the appended unit. As implies
With
Indeed ℘ is a lattice, so we may apply Theorem 2.1, and then
Before we prove our main theorem, that
First though, let’s explain our definition of
3.3. Some Examples
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
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
The top half of Figure 2 shows the same lattices ℘ =
The construction of
The third example in the figure shows a non-tight sublattice
3.4. The Closure of ℐ and Transitivity of D ℘(ℐ)
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
In this subsection we show that
Recall that we included the empty intervals of the form [
Now our technical lemma.
Lemma 3.6
[
αi, βj ] ⊆ ∪ℐ.For all x ∈L, xi ≥α ⇒xj > β. There is a ((β + 1)j, αi )-path in D.
The equivalence of (i) and (ii) is immediate as both are equivalent to the statement that there are no elements
On the one hand, consider an ((
By the definition of
On the other hand, assume that there is no such path from (
If
As ℐ
Proposition 3.7
On the one hand, assume that ℐ is closed. Then we can replace (i) of Lemma 3.6 with [
On the other hand, assume that ℐ is not closed. Then there is some [
4. Main Results
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
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
4.1. Main Theorem
Generalising Theorem 2.1 we have the following.
As it simplifies induction, we prove the slightly more general result that
In the general case, we first observe that is a subposet of . Indeed, as
Now it is enough to show that a bijection. We do this by induction on the size of ℐ. Let [
We must show for , that if and only if
To see that
4.2. One-to-one Correspondence
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
By Theorem 4.1 we have that any sublattice of ℘ can be expressed as the lattice of non-trivial downsets of some spanned extension
is such that is the sublattice ℘ ∪ℐ
Corollary 4.2
This solves one of our main goals, ‘reversing the point of view’ of correspondence given in Corollary 2.5.
4.3. Classification of Sublattices
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
Recall that a sublattice
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
The
Lemma 4.3
L is a {0, 1}-sublattice if and only if 0 is a source (has no in-arcs) in D and 1 is 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.
We have by Theorem 4.1 that is an isomorphism.
Clearly
T (0 ) = {0 } is a downset ofD if and only if0 is a source inD . Just as clearly, is a downset if and only if1 is a sink. The result follows.We have
αi → (α − 1)i inD if and only if there is no downsetT (x ) ofD containing (α −1)i but notαi . This is if and only if there is no elementx ∈L such thatxi =α − 1.First assume that
L is tight, and assume, towards contradiction thatD contains a cycle (α 1)i 1 → (α 2)i 2 · · · → (αℓ )i ℓ → (α 1)i 1, for someℓ ≥ 2. We show that no vertexx inL hasxi 1 =α 1, which contradicts the fact thatL is tight. Indeed, ifx did havexi 1 =α 1, thenxi 1 ≥α 1 so by Lemma 3.6xi 2> α 2 soxi 3> α 3 etc., and we get thatxi 1> α 1, a contradiction.
On the other hand, assume that
Remark 4.4
Though our goal was a correspondence including
For any preorder
is a lattice isomorphism. When
Observing that a spanned extension
of , Corollary 4.2 says that the map
5. Back to Embeddings
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
We would now like to extend Corollary 2.5 by fixing a finite distributive lattice
A
5.1. The Canonical Quotient of D ℘(L )
The
As [
As , the second fact follows by
Now for any pointed chain decomposition of a preorder
Thus we have the following.
5.2. The Full Correspondence Extending Corollary 2.5
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
Fix a lattice
Using the isomorphism that we get from Theorem 4.1, we will see that we can write
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
of
of
We are ready for our generalisation of Corollary 2.5. Recall that a pointed chain cover of
Theorem 5.3
It is enough to show that the maps
To see that
Remark 5.4
When removing
6. Lattices of Independent Sets
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
Adjusting our construction, we extend and complement results of Koh from [5].
6.1. Background
The correspondence taking a downset of a poset
In [5], Koh showed a converse: every finite distributive lattice
There are posets
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
A subset
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.
Let be the family of independent sets of size
For a poset
Our basic setup now is as follows. Given a product of a family of
By Remark 6.5 the
A digraph
The ‘if’ direction is immediate from Definition 6.4 as all arcs of are in
From here, given a digraph
6.3. The Alternate Rival Construction A ℘(L )
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
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
See Figure 4 for examples of
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
Theorem 6.8
The theorem holds by Lemma 6.6 in the simplest case where
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
Observe that this is essentially a generalisation of Koh’s Theorem 6.2. Indeed, as a tight embedding of
We continue, and complement Theorem 6.2 by finding every poset
6.4. Properties of A ℘(L ) via Koh’s Construction
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
Comparing definitions, or comparing Figure 2 to Figure 4, it is easy to see how to get
One can easily check that , and more generally that
It is a simple matter to show the transitivity of
Using Corollary 4.2, we get the following analogue.
Corollary 6.9
The classification lemma, Lemma 4.3, yields the following analogue.
Lemma 6.10
L is a {0, 1}-sublattice if and only if the minimum and maximum element of each tournament T in are 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: v 1 →u 1 ←v 2 →u 2 ← ·· ·→uℓ ←v 1.
For tight sublattices
6.5. Complement to Koh
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
For a lattice
As a complement to Koh’s theorem, we want to show that for any poset
Corollary 6.11
Let
Where
Corollary 6.12
Acknowledgements
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
I thank the anonymous referees for their patience and their constructive comments.
Figures
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
References
- Abstract
- 1. Introduction
- 2. Notation and Background
- 3. The Rival Construction
D ℘(L ) - 3.3. Some Examples
- 3.4. The Closure of ℐ and Transitivity of
D ℘(ℐ) - 4. Main Results
- 4.2. One-to-one Correspondence
- 4.3. Classification of Sublattices
- 5. Back to Embeddings
- 5.2. The Full Correspondence Extending Corollary 2.5
- 6. Lattices of Independent Sets
- 6.3. The Alternate Rival Construction
A ℘(L ) - 6.4. Properties of
A ℘(L ) via Koh’s Construction - 6.5. Complement to Koh
- Acknowledgements
- Figures
- References
- G. Birkhoff.
Rings of sets . Duke Math J.,3 (3)(1937), 443-454. - R. Dilworth.
A decomposition theorem for partially ordered sets . Ann of Math.,51 (1950), 161-166. - R. Dilworth.
Some combinatorial problems on partially ordered sets . Proc Sympos Appl Math,10 , (1960), 85–90.(American Mathematical Society, Providence, R. I.) - G. Grätzer. Lattice theory: foundation,
, Birkhäuser/Springer Basel AG, Basel, 2011. - KM. Koh.
On the lattice of maximum-sized antichains of a finite poset . Alg Universalis.,17 (1983), 73-86. - RN. Larson.
Embeddings of finite distributive lattices into products of chains . Semi-group Forum.,56 (1998), 70-77. - V. Retakh, and M. Saks.
On the rational relationships among pseudo-roots of a non-commutative polynomial ., arXiv:2001.04856 [math.RA]. - I. Rival.
Maximal sublattices of finite distributive lattices II . Proc Amer Math Soc.,44 (1974), 263-268. - M. Siggers.
Distributive lattice polymorphisms on reflexive graphs . Bull Korean Math Soc.,55 (2018), 81-105.