4. Problems

Problem G-1. Reduce to canonical form for distributive lattices (as a join of meets, where no part is superfluous):

(a) $(x \vee y) \wedge (x \vee z) \wedge (y \vee z)$;

(b) $x \vee (y \wedge (z \vee x) )$.

Problem G-2. For $L =$   FDL$(3)$, find the partially ordered set $P =$   JI$(L)$ and construct the lattice Downsets$(P)$, which of course is isomorphic to $L$.

Problem G-3. The $length$ of a chain is the number of coverings in it (one less than the number of elements). As you know, a maximal chain in a partially ordered set is a chain that is not contained in any other chain.

Show that if $L$ is a finite distributive lattice, then all its maximal chains have the same length, namely, the number of join-irreducibles in $L$.

Problem G-4. A group is generated by elements $a,b,\dots$ if all its elements are obtained by starting with $a,b,\dots$ and then repeatedly taking products and inverses. Likewise, a lattice is generated by elements $a,b,\dots$ if all its elements are obtainable from $a,b,\dots$ by repeatedly taking meets and joins.

(a) FDL$(3)$ can be generated by three elements. Assuming this is true, decide which three.

(b) Let $a,b,c$ be the generators of FDL$(3)$. Write each element of FDL$(3)$ as an expression in the generators.

(c) Rewriting expressions from (b) where necessary, write each element of FDL$(3)$ as an expression in the generators in canonical form.

Problem G-5. You know that a finite distributive lattice can be represented by sets of its own join-irreducibles, so that it is embedded in a power-set lattice. What similar statement holds if meet-irreducibles are used instead?

Problem G-6. For finite distributive lattices, you know various facts involving meet-irreducibles, meet-prime elements, prime ideals, join-irreducibles, join-prime elements, prime dual ideals, and prime ideals versus their complements. Use this information to show that in any finite distributive lattice $L$, we have MI$(L) \cong$   JI$(L)$, where MI$(L)$ and JI$(L)$ are the partially ordered sets of meet-irreducibles and of join-irreducibles, respectively.

Problem G-7. For a distributive lattice $L$ with partially ordered set $J$ of join-irreducibles, sometimes we write

$\log_{\mbox{\bf 2}} L = J$.

(a) Why is this reasonable?

(b) The ordinary log function obeys $\log(xy) = \log(x) + \log(y)$. Is there an analogous rule for finite distributive lattices?

(c) What about the rule $\log(x^y) = y \log(x)$?

Problem G-8. A map $\phi: L\rightarrow M$ of lattices is a homomorphism if

$\phi(x \vee y) = \phi(x) \vee \phi(y)$ and
$\phi(x \wedge y) = \phi(x) \wedge \phi(y)$.

(a) Let $a$ be an element of a distributive lattice $L$. Show that the map $x \mapsto a \wedge x$ is a lattice homomorphism.

(b) Let $[a,b]$ be an interval of a distributive lattice $L$ (so $a \leq b$). Show that the map $x \mapsto (x \vee a) \wedge b$ is a lattice homomorphism of $L$ onto $[a,b]$.

(c) Describe the set of fixed points of this map.

Problem G-9. Suppose that in a finite distributive $L$, the elements $a _ 1,\dots, a _ n$ are distinct and cover $c$. Show that $c$, the elements $a _ i$, and the joins of two or more of the $a _ i$ form a sublattice of $L$ isomorphic to 2$^ n$.

Problem G-10. Suppose that $P$ is a finite partially ordered set of width $w$. Show that Downsets$(P)$ has a sublattice isomorphic to 2$^w$. (Notice that it doesn't work just to restrict downsets to an antichain--that results in a lattice-homomorphic image rather than a sublattice!)

Problem G-11. The dimension of a partially ordered set $Q$ is the least integer $d$ such that $Q$ is isomorphic to a subset of a product of $d$ chains. Show that the dimension of 2$^ n$ is $n$. (Suggestion: Look at the atoms--the elements that cover the bottom element--and the co-atoms--the elements that are covered by the top element.)

Problem G-12. The dimension of a partially ordered set is defined in Problem G-. Show that the dimension of a finite distributive lattice $L$ is equal to the width of JI$(L)$, the partially ordered set of join-irreducibles, and that moreover $L$ can be lattice-embedded in the product of that many chains, not just embedded as a partially ordered set. (Intuitively, $L$ can be drawn as a lattice on $w$-dimensional graph paper if JI$(L)$ has width $w$.)

Problem G-13. In trying to prove a statement about a finite distributive lattice, it is always wise to see whether the statement can be translated into a statement about the partially ordered set of join-irreducibles. Translate these statements:

(a) $L$ is the direct product of two chains. (Here ``is'' really means ``is isomorphic to''.)

(b) $L$ is Boolean (i.e., every element $x$ has a complementary element $y$ so that $x \vee y = 1$, $x \wedge y = 0$).

In each case, your answer should be a statement that makes sense for an abstract partially ordered set.

Problem G-14. Let $P$ be a finite partially ordered set of width $w$. Show that if $D$ and $E$ are downsets of $P$ each with exactly $w$ maximal elements, then the same is true of $D \cup E$ and $D \cap E$.

Problem G-15. By Theorem , any finite distributive lattice $L$, $L$ is isomorphic to    Downsets$($   JI$(L))$. Show that for any finite partially ordered set $P$, $P$ is isomorphic to    JI$($Downsets$(P))$. (These two statements together show a correspondence between finite distributive lattices and finite partially ordered sets.)

Problem G-16. Let $P$ be a finite partially ordered set of width $w$. Let $L$ be the set of all antichains of $P$ that have $w$ elements. For $A,B \in L$, write $A \leq B$ if each element of $A$ is $\leq$ some element of $B$. A theorem of Dilworth states that $L$ is a distributive lattice. Prove this theorem. (Suggestion: Relate to Problem G-.)

Problem G-17. Recall that Pascal's Triangle is the triangular table whose entries are the binomial coefficients. Typical rows of Pascal's Triangle are $1, 4, 6, 4, 1$, and $1,5,10,10,5,1$. The largest of the binomial coefficients $\left[\begin{array}{c}n\\ k\end{array}\right]$ for given $n$ is the middle one ($n$ odd) or the middle two ($n$ even).

(a) Explain why in    2$^ n$ there are $\left[\begin{array}{c}n\\ k\end{array}\right]$ elements of ``rank'' $k$ for each $k$.

(b) The width of    2$^ n$ is clearly at least $\left[\begin{array}{c}n\\ {[n/2]}\end{array}\right]$. For    2$^ 4$ show that this is exactly the width. (Method: Exhibit that number of chains whose union is the whole partially ordered set.)

Problem G-18. For a partially ordered set $P$, an automorphism of $P$ is an isomorphism of $P$ onto itself. As usual, a subset $S$ of $P$ is invariant under an automorphism $\sigma$ if $\sigma (S) = S$.

(a) Show that a finite partially ordered set of width $w$ has an antichain of $w$ elements that is invariant under all automorphisms.

(b) Prove Sperner's Theorem: For a finite set $X$, a maximum-sized antichain in    Pow$(X)$ can be obtained from elements of fixed rank (i.e., all subsets of some fixed cardinality, namely, $[n/2]$).

(Suggestions: For (a): Consider the lattice of antichains from Problem G-. Could some one of its elements be expected to be invariant? For (b) use (a). This nice way of looking at Sperner's Theorem was discovered some time after earlier lengthy proofs and more awkward generalizations.)

Problem G-19. Show that every element of a finite distribute lattice is uniquely an irredundant join of join-irreducibles. (``Unique'' means up to rearrangement. An expression $p_1 \vee p_2 \vee \cdots \vee p_k$ is redundant if some $p_i$ can be deleted without changing the value. Method: As for unique factorization of integers. Note: This problem concerns elements, but by using free distributive lattices it can be seen that the same fact is true for expressions, as in §.)