5
$\begingroup$

In a finite distributive lattice $L$ one has $height(L) = |J(L)|$ i.e. the size of the largest chain equals the number of join-irreducible elements.

Briefly, this follows by arranging the subposet $J(L) = \{x_1,\dots,x_n\} \subset L$ so that $j > i \implies x_j \nleq x_i$, and then observing that $0 < x_1 < x_1 \lor x_2 < \dots < x_1 \lor \dots \lor x_n=1$ because join-irreducible elements are join-prime in distributive lattices.

What other natural classes of finite lattices $L$ satisfy $|J(L)| \leq height(L)$?

For example, do join-semidistributive lattices have this property?

Many thanks.

$\endgroup$
2
  • 3
    $\begingroup$ If your definition of "join-semidistributive lattice" agrees with what I would call a "join-distributive lattice," then the property $|J(L)|=\mathrm{height}(L)$ is the dual to Exercise 3.48 in Enumerative Combinatorics, vol. 1, second ed. $\endgroup$ Commented Jun 16, 2014 at 23:07
  • $\begingroup$ @RichardStanley: That's a great answer, thanks. By join-semidistributive lattices I meant the quasivariety of lattices defined by $x \lor y = x \lor z \implies x \lor y = x \lor (y \land z)$. A finite lattice lies in this class iff each of its elements has a canonical irredundant join representation. $\endgroup$
    – Rob Myers
    Commented Jun 17, 2014 at 9:14

2 Answers 2

4
$\begingroup$

Join semi-distributive lattices don't have this property because weak order on $S_n$ is join semi-distributive and doesn't have this property. (Eg, for $n=3$.)

Lattices satisfying the property you are interested in are called "join-extremal" by George Markowsky, in a paper Primes, irreducibles and extremal lattices. Order 9, 265–290 (1992).

The Tamari lattices, and their generalization, the Cambrian lattices, all have this property.

$\endgroup$
3
$\begingroup$

I shall prove a result allows one to effortlessly construct precisely the finite lattices $L$ such that $height(L)=|J(L)|$.

A closure system is a pair $(X,C)$ such that $C\subseteq P(X)$ and $C$ is closed under arbitrary intersection ($X\in C$ by taking the empty intersection). If $(X,C)$ is a closure system, then $C$ is clearly a complete lattice and elements in $L$ are said to be closed sets. It is easy to show that a pair $(X,C)$ with $C\subseteq P(X)$ is a closure system if and only if for each $R\subseteq X$ there is a smallest set $L\in C$ such that $R\subseteq L$. If $(X,C)$ is a closure system, then define $C^{*}:P(X)\rightarrow P(X)$ to be the mapping such that if $A\subseteq X$, then $C^{*}(A)$ is the smallest set in $C$ such that $A\subseteq C^{*}(A)$.

If $L$ is a finite lattice and $x\in L$, then let $J(x)$ denote the collection of all join-irreducible elements $a$ with $a\leq x$.

$\mathbf{Theorem}$ The finite lattices such that $height(L)=|J(L)|$ are up-to-isomorphism the finite lattices $C$ such that $(\{1,...,n\},C)$ is a closure system with $\emptyset,\{1\},...,\{1,...,n\}\in C$.

$\mathbf{Proof}$ Suppose that $(\{1,...,n\},C)$ is a closure system with $\emptyset,\{1\},...,\{1,...,n\}\in C$. Then $\emptyset,\{1\},...,\{1,...,n\}$ is a chain in $C$ of length $n+1$.

Now assume that $L\in C$ is join-irreducible in the lattice $C$. Then clearly $L=\bigvee_{a\in L}^{L}C^{*}(\{a\})$. Therefore, since $L$ is join-irreducible, we have $L=C^{*}(\{a\})$ for some $a\in\{1,...,n\}$. In particular, there can be at most $n$ join-irreducible elements in the lattice $C$. We conclude that $height(L)\geq|J(L)|$, so $height(L)=|J(L)|$, and $C^{*}(\{1\}),...,C^{*}(\{n\})$ are the join-irreducibles in $C$.

Now for the converse, assume that $L$ is a finite lattice such that $height(L)=|J(L)|$ and $J(L)=n$. Let $0=x_{0}<x_{1}<...<x_{n}=1$ be a chain of length $n+1$. Then $J(x_{0})\subset J(x_{1})\subset...\subset J(x_{n})$ (and each subset here is a proper subset). Since $J(x_{i})\subseteq J(L)$ for $0\leq i\leq n$ and $J(L)=n$, we conclude that there are $a_{1},...,a_{n}$ such that $J(x_{i})=\{a_{1},...,a_{i}\}$ for $1\leq i\leq n$. In this case, we have $J(L)=\{a_{1},...,a_{n}\}$. Now let $C=\{J(x)|x\in L\}$. If $a\in J(L)$, then $a\in\bigcap_{i\in I}J(x_{i})$ if and only if $a\leq x_{i}$ for $i\in I$ if and only if $a\leq\bigwedge_{i\in I}x_{i}$ if and only if $a\in J(\bigwedge_{i\in I}x_{i})$. Therefore $\bigcap_{i\in I}J(x_{i})=J(\bigwedge_{i\in I}x_{i})$. We conclude that $C$ is a closure system. Furthermore, we have $J(x_{i})=\{a_{1},...,a_{i}\}\in C$ whenever $0\leq i\leq n$. I now claim that the mapping $f:L\rightarrow C$ where $f(x)=J(x)$ for all $x\in L$ is a lattice isomorphism. By definition, the mapping $L$ is surjective. Furthermore, since each $x\in L$ is a join of join-irreducible elements, we have $x=\bigvee J(x)=\bigvee f(x)$. Therefore, if $f(x)=f(y)$, then $x=\bigvee f(x)=\bigvee f(y)=y$. Therefore, the mapping $f$ is a bijection. Now, if $x\leq y$, then clearly $f(x)\subseteq f(y)$, and if $f(x)\subseteq f(y)$, then $x=\bigvee f(x)\leq\bigvee f(y)=y$. Therefore, the mapping $f$ is an order-isomorphism, and hence a lattice isomorphism. $\mathbf{QED}$

In particular, if $L$ is a finite lattice with $height(L)=|J(L)|$ and $B\subseteq L$ is a chain of length $height(L)+1$, and $B\subseteq M\subseteq L$ is a subset closed under taking all meets, then $M$ is a finite lattice with $height(M)=|J(M)|$.

If $P$ is a poset and $x\in P$, then let $\downarrow x=\{y\in P|y\leq x\},\uparrow x=\{y\in P|y\geq x\}$.

If $L$ is a complete lattice, then let $C=\{\downarrow x|x\in L\}$. Then $(L,C)$ is a closure system and the lattices $L$ and $C$ are isomorphic.

In particular, for each finite lattice $L$, there is a closure system $(\{1,...,n-1\},C)$ such that the lattice $C$ is isomorphic to $L$.

Let $D$ be the collection of all sets $L\subseteq\{1,...,n\}$ such that if $n\in L$, then $L\cap\{1,...,n-1\}\in C$. Then it is easy to show that $D$ is a closure system with $\emptyset,\{1\},\{1,2\},...,\{1,2,...,n\}\in D$. Therefore $Height(D)=|J(D)|$.

Now define a mapping $\iota:C\rightarrow D$ by $\iota(L)=L\cup\{n\}$. Then $\iota$ is an injective lattice homomorphism and an isomorphism from $C$ to $\uparrow D^{*}(\{n\})$.

We therefore conclude that for each lattice $L$ there is a lattice $M$ with $Height(M)=|J(M)|$ and an $x\in M$ such that $L\simeq\uparrow x$.

In particular, if a universal sentence $\phi$ is satisfied by each finite lattice $L$ with $Height(L)=|J(L)|$, then $\phi$ is satisfied by every finite lattice (this is because universal sentences are preserved under taking subalgebras). Thus, the finite lattices with $Height(M)=|J(M)|$ do not satisfy any identities that are not satisfied by all finite lattices.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .