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$
  • 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$ – Richard Stanley Jun 16 '14 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 Jun 17 '14 at 9:14
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.