Order dimension of the lattice of all sublattices of a Boolean lattice

89 Views Asked by At

Let $B_n$ be the boolean lattice of subsets of $\{1,...,n \}$ and $W_n$ the lattice of all sublattices of $B_n$ ordered by the natural order. What is the order dimension of $W_n$?

1

There are 1 best solutions below

0
On

One easy observation is that the order dimension of $W_n$ is at most $2^n$.

Reason. If $S\in B_n$ is any subset, then there exists a linear extension $\leq_S$ of $\leq_{W_n}$ such that all elements of $W_n$ containing $S$ are $\leq_S$-above those that do not contain $S$. (Linearly order the elements of $W_n$ containing $S$ in any way that extends $\leq_{W_n}$, linearly order the elements of $W_n$ not containing $S$ in any way that extends $\leq_{W_n}$, then stack the first linear order on top of the second.)

It is not hard to see that the order on $W_n$ is the intersection of the linear extensions $\leq_S$. (If $A\not\leq_{W_n} B$, then there must exist $S\in A-B$, and then $A\not\leq_S B$.) This shows how to express $\leq_{W_n}$ as the intersection of $2^n$ linear extensions.