Finite lattice congruences, interval endpoints and descending rooted-chain labels

Let $L$ be a finite lattice (Lattices, distributive lattices, and order ideals) with meet $\wedge$ and join $\vee$, and let $P$ be a finite graded poset (Graded poset, rank function, and rank levels) with rank function $\rho$ (Partial order and partially ordered set).

(1) Lattice congruences and projected endpoints. An equivalence relation $\theta$ on $L$ is a lattice congruence if $x{\equiv }_{\theta }{x}^{\mathrm{\prime }}$ and $y{\equiv }_{\theta }{y}^{\mathrm{\prime }}$ imply $x\wedge y{\equiv }_{\theta }{x}^{\mathrm{\prime }}\wedge y^{\mathrm{\prime }}$ and $x\vee y{\equiv }_{\theta }{x}^{\mathrm{\prime }}\vee y^{\mathrm{\prime }}$. For $x\in L$ write $[x{]}_{\theta }$ for the class of $x$. On classes this defines the proposed quotient operations $[x{]}_{\theta }\vee [y{]}_{\theta }:=[x\vee y{]}_{\theta }$ and $[x{]}_{\theta }\wedge [y{]}_{\theta }:=[x\wedge y{]}_{\theta }$; the proposed lower endpoint ${\pi }_{\downarrow }(x)$ and upper endpoint ${\pi }_{\uparrow }(x)$ of a class are its least and greatest members. The definition asserts neither that the quotient operations are independent of representatives nor that endpoints exist; both are proved in Lattice quotient descent, class intervals and monotone endpoints.

(2) Descending rooted-chain labels. Let $x\le y$ in $P$, let $[x,y]=\{z\in P:x\le z\le y\}$ be the closed interval (Intervals in a poset; locally finite, lower-finite and upper-finite posets) and put $\rho (x,y):=\rho (y)-\rho (x)$. A descending rooted-chain labeling of $[x,y]$ with values in a linearly ordered set $(\mathrm{\Lambda },<)$ assigns to every pair $(c,v⋖w)$ consisting of a descending chain $c=(y=z_0⋗z_1⋗\cdots ⋗z_j=w)$ in $[x,y]$ and a cover $v⋖w$ (Graded poset, rank function, and rank levels) a label $\lambda (c;v⋖w)\in \mathrm{\Lambda }$; the label may depend on the chain $c$ above $w$, not only on the cover. A maximal chain of $[x,y]$ is a chain of the form $y=m_0⋗m_1⋗\cdots ⋗m_n=x$ with $n=\rho (x,y)$ (equivalently: a chain of $[x,y]$ contained in no larger chain of $[x,y]$); note $\mathrm{\mid }m\mathrm{\mid }=n+1$ for every maximal chain $m$ of $[x,y]$. Its label word is the $n$-tuple $\lambda (m)=({\lambda }_1(m),\dots ,{\lambda }_n(m))$ with ${\lambda }_i(m):=\lambda (m_0⋗\cdots ⋗m_{i-1};m_i⋖m_{i-1})$: as one descends the chain, each step is labeled relative to the chain already traversed above it. Given $x\le v\le w\le y$ and a descending chain $c$ from $y$ to $w$, the rooted interval $([v,w],c)$ carries the labeling induced by keeping the root chain fixed: a maximal chain $v=w_0⋖w_1⋖\cdots ⋖w_k=w$ of $[v,w]$ has label word whose $i$-th entry is the label of its $i$-th step counted from the top, the cover $w_{k-i}⋖w_{k-i+1}$, paired with the root chain $c$ extended by $w_{k-1}⋗\cdots ⋗w_{k-i+1}$ (an empty extension when $i=1$), that is, $\lambda (c+w_{k-1}⋗\cdots ⋗w_{k-i+1};w_{k-i}⋖w_{k-i+1})$. An ordinary edge labeling is the special case in which $\lambda (c;v⋖w)$ does not depend on $c$.

(3) Increasing and falling chains, descents, lexicographic order. A maximal chain $m$ of $[x,y]$ is increasing if ${\lambda }_1(m)<{\lambda }_2(m)<\cdots <{\lambda }_n(m)$; it is falling if ${\lambda }_1(m)\ge {\lambda }_2(m)\ge \cdots \ge {\lambda }_n(m)$ and strictly falling if ${\lambda }_1(m)>{\lambda }_2(m)>\cdots >{\lambda }_n(m)$. Its descent set is $D(m):=\{i\in \{1,\dots ,n-1\}:{\lambda }_i(m)>{\lambda }_{i+1}(m)\}$, so that $m$ is strictly falling exactly when $D(m)=\{1,\dots ,n-1\}$. Label words are compared lexicographically: $\lambda (m^{\mathrm{\prime }})\prec \lambda (m)$ if at the least index $i$ with ${\lambda }_i(m^{\mathrm{\prime }})\mathrm{\ne }{\lambda }_i(m)$ one has ${\lambda }_i(m^{\mathrm{\prime }})<{\lambda }_i(m)$.

(4) No-tie and lex-increasing hypotheses. The labeling satisfies the no-tie condition (N) if in every rooted interval $([v,w],c)$ of $[x,y]$ the labels of any maximal chain of $[v,w]$ are pairwise distinct; then falling and strictly falling coincide on each maximal chain. It satisfies the lex-increasing property (L) if in every rooted interval $([v,w],c)$ of $[x,y]$ there is exactly one increasing maximal chain, and its label word is lexicographically first among the label words of all maximal chains of $([v,w],c)$. The rank-zero and rank-one cases give (L) its expected vacuous meaning: a rank-zero interval has one maximal chain, consisting of its single element and having an empty label word, and a rank-one interval has a single chain whose one-term label word is increasing.