Finite Lattice Projections and Coxeter Chain Labels — Examples

The cover labeling is well defined and ordinary: by [F1] the covers of $B_3$ are exactly the covers $S⋖S\cup \{i\}$ with $i\mathrm{\notin }S$, so the assignment is a labeling of all covers, and the label $i$ of a cover depends only on that cover, not on any descending chain above it; hence it is an ordinary edge labeling and so, in particular, a descending rooted-chain labeling of $[\mathrm{\varnothing },\{1,2,3\}]$ in the sense of [F2].

(N) and (L). Let $\mathrm{\varnothing }\subseteq S\subseteq T\subseteq \{1,2,3\}$ and let $m$ be a maximal chain of $[S,T]$; its steps add the elements of $T\setminus S$ one at a time, so the labels on $m$ are exactly the distinct elements of $T\setminus S$ and are pairwise distinct, which is (N) for the rooted interval $([S,T],c)$. Every maximal chain of $[S,T]$ corresponds to just such an order of adding the $r:=\mathrm{\mid }T\setminus S\mathrm{\mid }$ elements of $T\setminus S$, and its word read from the top is the reverse addition order; hence increasing words correspond exactly to adding the elements of $T\setminus S$ in decreasing order, and the increasing arrangement of $T\setminus S$ is the lexicographically first of the words; so there is exactly one increasing maximal chain, namely the one that adds the elements in decreasing order, and it is lexicographically first, which is (L). Since $S,T$ and $c$ were arbitrary, (N) and (L) hold on every rooted interval of $[\mathrm{\varnothing },\{1,2,3\}]$.

The six maximal chains. A maximal chain of $[\mathrm{\varnothing },\{1,2,3\}]$ is an order of adding $1,2,3$, and its word is the reverse of that order; hence there are exactly $6$ maximal chains and their words are the six permutations, obtained as follows: adding $2,3,1$ gives $\{1,2,3\}⋗\{2,3\}⋗\{2\}⋗\mathrm{\varnothing }$ with word $(1,3,2)$; adding $3,1,2$ gives $\{1,2,3\}⋗\{1,3\}⋗\{3\}⋗\mathrm{\varnothing }$ with word $(2,1,3)$; adding $1,3,2$ gives $\{1,2,3\}⋗\{1,3\}⋗\{1\}⋗\mathrm{\varnothing }$ with word $(2,3,1)$; adding $2,1,3$ gives $\{1,2,3\}⋗\{1,2\}⋗\{2\}⋗\mathrm{\varnothing }$ with word $(3,1,2)$; adding $1,2,3$ gives $\{1,2,3\}⋗\{1,2\}⋗\{1\}⋗\mathrm{\varnothing }$ with word $(3,2,1)$; and adding $3,2,1$ gives $\{1,2,3\}⋗\{2,3\}⋗\{3\}⋗\mathrm{\varnothing }$ with word $(1,2,3)$. Among the six permutations only $(1,2,3)$ is increasing and only $(3,2,1)$ is (strictly) falling, so the increasing chain is $\{1,2,3\}⋗\{2,3\}⋗\{3\}⋗\mathrm{\varnothing }$ and the strictly falling chain is $\{1,2,3\}⋗\{1,2\}⋗\{1\}⋗\mathrm{\varnothing }$, as stated.

Facets of the open interval. By [F6] the facets of $\mathrm{\Delta }((\mathrm{\varnothing },\{1,2,3\}))$ are the maximal chains of the open interval, that is, the sets obtained from the six maximal chains of step 2.1 by deleting the two endpoints: $(1,2,3)\mapsto \{2,3\}\supset \{3\}$, $(1,3,2)\mapsto \{2,3\}\supset \{2\}$, $(2,1,3)\mapsto \{1,3\}\supset \{3\}$, $(2,3,1)\mapsto \{1,3\}\supset \{1\}$, $(3,1,2)\mapsto \{1,2\}\supset \{2\}$ and $(3,2,1)\mapsto \{1,2\}\supset \{1\}$, ordered by the words of their parent chains: this is the list of six two-element chains in the stated order.

The Möbius value. Since $(3,2,1)$ is the only falling word among the six by step 2.1, the falling-chain formula of [F5] gives $\mu (\mathrm{\varnothing },\{1,2,3\})=(-1{)}^3\cdot 1=-1$ in $B_3$. The recurrence [F7] gives $\mu (\mathrm{\varnothing },\mathrm{\varnothing })=1$, $\mu (\mathrm{\varnothing },\{i\})=-\mu (\mathrm{\varnothing },\mathrm{\varnothing })=-1$ for each singleton, $\mu (\mathrm{\varnothing },\{i,j\})=-(\mu (\mathrm{\varnothing },\mathrm{\varnothing })+\mu (\mathrm{\varnothing },\{i\})+\mu (\mathrm{\varnothing },\{j\}))=-(1-1-1)=1$ for each two-element subset, and $\mu (\mathrm{\varnothing },\{1,2,3\})=-(1+3\cdot (-1)+3\cdot 1)=-1$, in agreement with the formula.

The replacement step. Take $m^{\mathrm{\prime }}$ the chain with word $(1,3,2)$, namely $\{1,2,3\}⋗\{2,3\}⋗\{2\}⋗\mathrm{\varnothing }$, and $m$ the chain with word $(2,1,3)$, namely $\{1,2,3\}⋗\{1,3\}⋗\{3\}⋗\mathrm{\varnothing }$; then $\lambda (m^{\mathrm{\prime }})\prec \lambda (m)$. The first divergence is at index $1$ and the first reunion at index $3$, so $d=0$, $g=3$, the window word of $m$ is $(2,1,3)$, and $m^{\mathrm{\prime }}$ and $m$ share exactly the vertices $\{1,2,3\}$ and $\mathrm{\varnothing }$, i.e. $m^{\mathrm{\prime }}\cap m=\{\{1,2,3\},\mathrm{\varnothing }\}$. The window word has its descent at position $e=1$: ${\lambda }_1(m)=2>1={\lambda }_2(m)$; the rooted rank-two interval $([\{3\},\{1,2,3\}],\{1,2,3\})$ has the two maximal chains $\{1,2,3\}⋗\{1,3\}⋗\{3\}$ and $\{1,2,3\}⋗\{2,3\}⋗\{3\}$ with words $(2,1)$ and $(1,2)$, so the increasing one is $\{1,2,3\}⋗\{2,3\}⋗\{3\}$ and replacing the segment $\{1,2,3\}⋗\{1,3\}⋗\{3\}$ of $m$ by it gives $k=\{1,2,3\}⋗\{2,3\}⋗\{3\}⋗\mathrm{\varnothing }$, the chain with word $(1,2,3)$. Then $\lambda (k)=(1,2,3)\prec (2,1,3)=\lambda (m)$, the intersection $k\cap m=\{\{1,2,3\},\{3\},\mathrm{\varnothing }\}$ has $\mathrm{\mid }k\cap m\mathrm{\mid }=3=\mathrm{\mid }m\mathrm{\mid }-1$, and $m^{\mathrm{\prime }}\cap m=\{\{1,2,3\},\mathrm{\varnothing }\}\subseteq k\cap m$; the replaced two-step segment is $\{1,2,3\}⋗\{1,3\}⋗\{3\}$, as in the shelling lemma [F4].

The computations verify every claim of the Example: the element-added cover labeling is an ordinary edge labeling and hence a descending rooted-chain labeling; it satisfies (N) and (L) on every rooted interval of $[\mathrm{\varnothing },\{1,2,3\}]$; the six maximal chains have the six permutation words, with $(\{1,2,3\}⋗\{2,3\}⋗\{3\}⋗\mathrm{\varnothing })$ the unique increasing chain and $(\{1,2,3\}⋗\{1,2\}⋗\{1\}⋗\mathrm{\varnothing })$ the unique strictly falling chain; the facets of $\mathrm{\Delta }((\mathrm{\varnothing },\{1,2,3\}))$ are the six listed two-element chains in the stated order; the exhibited chain $k$ realizes the shelling replacement for the pair $(1,3,2)\prec (2,1,3)$; and the falling-chain formula returns $\mu (\mathrm{\varnothing },\{1,2,3\})=-1$, which the recurrence confirms.

The three blocks are intervals with their endpoints in the block: $\{0,a\}=\{z:0\le z\le a\}=[0,a]$, $\{b\}=[b,b]$ and $\{1\}=[1,1]$; they are nonempty, pairwise disjoint, and their union is $\{0,a,b,1\}=D$. By [F2] they form a set partition of $D$, and calling its blocks classes gives the equivalence relation $\theta$ with $0\equiv a$, $b\equiv b$, $1\equiv 1$ and $0\equiv ̸b$, $0\equiv ̸1$, $a\equiv ̸b$, $a\equiv ̸1$, $b\equiv ̸1$.

The relation $\theta$ is not a lattice congruence: $0\equiv a$ and $b\equiv b$ hold, but by [F1] one has $0\vee b=b$ and $a\vee b=1$, and $b\equiv ̸1$ because $b$ and $1$ lie in the distinct blocks $\{b\}$ and $\{1\}$; so the congruentiality requirement of [F3] for joins fails, and $\theta$ is not a lattice congruence.

The upper endpoint map of the partition is not order-preserving: $u(0)=a$ and $u(b)=b$ by step 1.1, and $0\le b$ in $D$ while $a\le ̸b$ because $a$ and $b$ are incomparable; hence $u(0)\le ̸u(b)$.

Conclusion. The partition of $D$ into $\{0,a\}$, $\{b\}$, $\{1\}$ is a partition into intervals with endpoints in the class (step 1.1) and its upper endpoint map is not order-preserving (step 2.2), so by the criterion [F4] it is not a lattice congruence, in agreement with the direct failure of step 2.1; this refutes the displayed statement and shows that the monotonicity hypothesis of the criterion cannot be dropped.

The interval partitions of $C$. By [F1] the intervals of $C$ are $\{0\},\{a\},\{1\},\{0,a\},\{a,1\}$ and $C$, so a partition of $C$ into intervals is a family of pairwise disjoint of these sets with union $C$. The possibilities are: the three singletons; $\{0,a\}$ with $\{1\}$; $\{0\}$ with $\{a,1\}$; and $C$ itself. There is no other: any such partition other than these would have to contain a two-element block $\{0,1\}$, but $\{0,1\}$ is not an interval because $0<1$ and $a$ lies strictly between, while $a\mathrm{\notin }\{0,1\}$. Hence there are exactly four interval partitions of $C$, the four listed in the Example.

The interval partitions of $D$. By [F2] the intervals of $D$ are the four singletons, the four two-element sets $\{0,a\},\{0,b\},\{a,1\},\{b,1\}$, and $D$. No three-element subset of $D$ is an interval: a block of the form $[d,u]$ contains its least element $d$ and its greatest element $u$, but $\{0,a,b\}$ has no greatest element and $\{a,b,1\}$ has no least element, while the two remaining three-element subsets $\{0,a,1\}$ and $\{0,b,1\}$ have least element $0$ and greatest element $1$ with $[0,1]=D$ strictly larger than either. A partition of $D$ into intervals therefore consists of the four singletons ($1$ way), or one two-element interval and two singletons ($4$ choices of the pair, the complement being two singletons), or two two-element intervals, of which the three pairings of $D$ contribute the admissible $\{0,a\}\mathrm{\mid }\{b,1\}$ and $\{0,b\}\mathrm{\mid }\{a,1\}$ but not $\{a,b\}\mathrm{\mid }\{0,1\}$ since neither $\{a,b\}$ nor $\{0,1\}$ is an interval, or $D$ itself ($1$ way): altogether $1+4+2+1=8$ interval partitions, the eight listed in the Example.

The four partitions of $C$ are congruences. For each of the four partitions of step 1.1 the endpoints $d(x)\le u(x)$ are the least and greatest members of the block of $x$: for the discrete partition $d=u=\mathrm{i}\mathrm{d}$, both maps order-preserving; for $\{0,a\}\mathrm{\mid }\{1\}$ one has $d(0)=d(a)=0$, $d(1)=1$ and $u(0)=u(a)=a$, $u(1)=1$, and both maps are nondecreasing along $0<a<1$; for $\{0\}\mathrm{\mid }\{a,1\}$ one has $d(0)=0$, $d(a)=d(1)=a$ and $u(0)=0$, $u(a)=u(1)=1$, again both nondecreasing; and for the all-one partition both maps are constant. By the criterion [F3] all four are lattice congruences. Their quotients, computed with [F4], are: $C$ for the discrete partition (the blocks are the elements and $[x]\vee [y]=[x\vee y]$ reproduces the order of $C$); the two-element chain $\{0,a\}<\{1\}$ for $\{0,a\}\mathrm{\mid }\{1\}$, since $0\vee 1=1$ makes $\{0,a\}\vee \{1\}=\{1\}$ and $\{0,a\}\le \{1\}$; the two-element chain $\{0\}<\{a,1\}$ for $\{0\}\mathrm{\mid }\{a,1\}$, since $0\vee 1=1$ makes $\{0\}\vee \{a,1\}=\{a,1\}$; and the one-element lattice for the all-one partition.

The criterion on the eight partitions of $D$. The endpoint maps of each partition of step 1.2 are read off from its blocks, and monotonicity is checked on the five comparable pairs $0\le a$, $0\le b$, $0\le 1$, $a\le 1$, $b\le 1$. The discrete partition has $d=u=\mathrm{i}\mathrm{d}$ and is monotone; the all-one partition has constant maps and is monotone; the partition $\{0,a\}\mathrm{\mid }\{b,1\}$ has $d(0)=d(a)=0$, $d(b)=d(1)=b$, $u(0)=u(a)=a$ and $u(b)=u(1)=1$, and on the five pairs: $0\le a$ gives $0\le 0$ and $a\le a$, $0\le b$ gives $0\le b$ and $a\le 1$, $0\le 1$ gives $0\le b$ and $a\le 1$, $a\le 1$ gives $0\le b$ and $a\le 1$, and $b\le 1$ gives $b\le b$ and $1\le 1$, so $d$ and $u$ are order-preserving; the partition $\{0,b\}\mathrm{\mid }\{a,1\}$ has $d(0)=d(b)=0$, $d(a)=d(1)=a$, $u(0)=u(b)=b$ and $u(a)=u(1)=1$, and on the five pairs: $0\le a$ gives $0\le a$ and $b\le 1$, $0\le b$ gives $0\le 0$ and $b\le b$, $0\le 1$ gives $0\le a$ and $b\le 1$, $a\le 1$ gives $a\le a$ and $1\le 1$, and $b\le 1$ gives $0\le a$ and $b\le 1$, so these maps are order-preserving too. These four partitions satisfy the criterion [F3]. The other four fail: $\{0,a\}\mathrm{\mid }\{b\}\mathrm{\mid }\{1\}$ has $u(0)=a$ and $u(b)=b$ with $0\le b$ but $a\le ̸b$; $\{0,b\}\mathrm{\mid }\{a\}\mathrm{\mid }\{1\}$ has $u(0)=b$ and $u(a)=a$ with $0\le a$ but $b\le ̸a$; $\{0\}\mathrm{\mid }\{a\}\mathrm{\mid }\{b,1\}$ has $d(a)=a$ and $d(1)=b$ with $a\le 1$ but $a\le ̸b$; and $\{0\}\mathrm{\mid }\{b\}\mathrm{\mid }\{a,1\}$ has $d(b)=b$ and $d(1)=a$ with $b\le 1$ but $b\le ̸a$. Every lattice congruence of $D$ has interval classes by [F4], so its partition occurs in step 1.2. Hence the four partitions satisfying [F3] are exactly the lattice congruences of $D$.

Quotients and the count. By [F4] the quotient of $\{0,a\}\mathrm{\mid }\{b,1\}$ is the two-element chain $\{0,a\}<\{b,1\}$: the blocks are distinct, and taking the representatives $0\in \{0,a\}$ and $b\in \{b,1\}$ the class operations give $\{0,a\}\vee \{b,1\}=[0\vee b]=[b]=\{b,1\}$ and $\{0,a\}\wedge \{b,1\}=[0\wedge b]=[0]=\{0,a\}$, so the order is total on the two classes. The quotient of $\{0,b\}\mathrm{\mid }\{a,1\}$ is likewise the two-element chain $\{0,b\}<\{a,1\}$, by the representatives $0$ and $a$. The quotient of the discrete partition is $D$ and the quotient of the all-one partition is the one-element lattice. Therefore $D$ has exactly four lattice congruences and the congruence lattice of $D$ has exactly four elements: order congruences by refinement, meaning that each class of the finer congruence is contained in a class of the coarser one. The discrete congruence is the least, the all-one congruence is the greatest, and the two 2+2 congruences are incomparable (one identifies $0$ with $a$ but not $b$, and the other identifies $0$ with $b$ but not $a$). Thus this order is a diamond: the two middle elements have meet the discrete congruence and join the all-one congruence; comparable pairs have meet the smaller and join the larger. This proves directly that the four congruences form a lattice. Together with steps 1.1, 1.2, 2.1 and 2.2 this verifies every claim of the Example: the four interval partitions of $C$ and their quotients, the eight interval partitions of $D$, the four surviving the criterion with their explicit failures, and the four-element congruence lattice of $D$.