Lexicographic chain shelling and the falling-chain Möbius formula

Rank preliminaries. If $u<u^{\mathrm{\prime }}$ in $P$, start with the chain $u<u^{\mathrm{\prime }}$ and insert an intermediate vertex whenever two consecutive vertices are not covers. Each insertion adds a new vertex of the finite interval $[u,u^{\mathrm{\prime }}]$, so the process stops at a saturated chain. Along it the rank increases by exactly one at each step by [F1], giving $\rho (u^{\mathrm{\prime }})=\rho (u)+s>\rho (u)$, where $s\ge 1$ is its number of steps. Consequently, for a strict chain $w=y_0>y_1>\cdots >y_t=v$ with $k:=\rho (v,w)$, the interior rank shifts $\rho (y_i)-\rho (v)$ are distinct members of $\{1,\dots ,k-1\}$. Their set has exactly $t-1$ elements, and $t\le k$.

Chain-sum identity. For $v<w$ put $c_t(v,w):=\mathrm{\#}\{$strict chains $w=y_0>y_1>\cdots >y_t=v\}$ and $A(v,w):={\sum }_{t=1}^{\mathrm{\mid }[v,w]\mathrm{\mid }-1}(-1{)}^t{c}_t(v,w)$; the sum includes every strict chain, since one with $t$ steps has $t+1$ distinct vertices of $[v,w]$ by [F9]. We prove $A(v,w)=\mu (v,w)$ by strong induction on $\mathrm{\mid }[v,w]\mathrm{\mid }$. The direct chain $w>v$ contributes $-1$. Every other chain has a unique first vertex $\zeta$ below $w$, with $v<\zeta <w$, and consists of the first step $w>\zeta$ followed by a strict chain from $\zeta$ to $v$. Thus $A(v,w)=-1-{\sum }_{v<\zeta <w}A(v,\zeta )$. Each $[v,\zeta ]$ is a proper subset of $[v,w]$, hence has smaller cardinality by [F9]; the induction hypothesis and [F6] give $A(v,w)=-1-{\sum }_{v<\zeta <w}\mu (v,\zeta )=-{\sum }_{v\le z<w}\mu (v,z)=\mu (v,w)$. When no intermediate vertex exists, the intermediate sum is empty and this is also the base case.

Setup of (i). Let $m^{\mathrm{\prime }},m$ be maximal chains of $[x,y]$ with $\lambda (m^{\mathrm{\prime }})\prec \lambda (m)$. Since $m_0=m_0^{\mathrm{\prime }}=y$ and $m_n=m_n^{\mathrm{\prime }}=x$, the index $d:=\max \{i:m_j=m_j^{\mathrm{\prime }}$ for all $j\le i\}$ and $g:=\min \{i>d:m_i=m_i^{\mathrm{\prime }}\}$ are defined, and $g\ge d+2$ because $m_{d+1}\mathrm{\ne }{m}_{d+1}^{\mathrm{\prime }}$. Each step of a maximal chain is a cover by [F2], so $\rho (m_i)=\rho (y)-i=\rho (m_i^{\mathrm{\prime }})$; hence a common vertex of the two chains is some $m_i=m_i^{\mathrm{\prime }}$, and $m_i\mathrm{\ne }{m}_i^{\mathrm{\prime }}$ for $d<i<g$ while $m_i=m_i^{\mathrm{\prime }}$ for $i\le d$ and $i=g$, so $m^{\mathrm{\prime }}\cap m=\{m_i:m_i=m_i^{\mathrm{\prime }}\}\subseteq \{m_i:i\le d\text{ or }i\ge g\}$. The subchains $m_d⋗\cdots ⋗m_g$ and $m_d^{\mathrm{\prime }}⋗\cdots ⋗m_g^{\mathrm{\prime }}$ are maximal chains of the rooted interval $([m_g,m_d],c)$ with $c=m_0⋗\cdots ⋗m_d$, and by [F2] their words there are the windows $\omega :=({\lambda }_{d+1}(m),\dots ,{\lambda }_g(m))$ and ${\omega }^{\mathrm{\prime }}:=({\lambda }_{d+1}(m^{\mathrm{\prime }}),\dots ,{\lambda }_g(m^{\mathrm{\prime }}))$. The window $\omega$ is not increasing: suppose it were; then the window subchain of $m$ is an increasing maximal chain of the rooted interval, hence the unique increasing one and lexicographically first by [F3], so $\omega ⪯{\omega }^{\mathrm{\prime }}$. If $\omega \prec {\omega }^{\mathrm{\prime }}$, then, the two full words agreeing in positions $1,\dots ,d$, their first difference lies in $\{d+1,\dots ,g\}$ and has ${\lambda }_i(m)<{\lambda }_i(m^{\mathrm{\prime }})$, so $\lambda (m)\prec \lambda (m^{\mathrm{\prime }})$, contradicting $\lambda (m^{\mathrm{\prime }})\prec \lambda (m)$; while if ${\omega }^{\mathrm{\prime }}=\omega$, then the window subchain of $m^{\mathrm{\prime }}$ is a maximal chain of the same rooted interval, distinct from that of $m$ because $m_{d+1}\mathrm{\ne }{m}_{d+1}^{\mathrm{\prime }}$, whose word $\omega$ is increasing, contradicting the uniqueness in (L). Therefore $\omega$ has an index $j\in \{1,\dots ,g-d-1\}$ with ${\omega }_j\ge {\omega }_{j+1}$, and ${\omega }_j\mathrm{\ne }{\omega }_{j+1}$ by (N) applied to the window chain, so with $e:=d+j\in \{d+1,\dots ,g-1\}$ we have ${\lambda }_e(m)>{\lambda }_{e+1}(m)$.

Replacement chain of (i). Put $c^{\mathrm{\prime }}:=m_0⋗\cdots ⋗m_{e-1}$. The segment $m_{e-1}⋗m_e⋗m_{e+1}$ is a maximal chain of the rooted interval $([m_{e+1},m_{e-1}],c^{\mathrm{\prime }})$, and by [F2] its word there is $({\lambda }_e(m),{\lambda }_{e+1}(m))$, which is falling by step 1.3, hence not increasing. By (L) of [F3] this rooted interval has exactly one increasing maximal chain; it is not the segment, so it has the form $m_{e-1}⋗y^{\mathrm{\prime }}⋗m_{e+1}$ with $m_{e+1}<y^{\mathrm{\prime }}<m_{e-1}$ and $y^{\mathrm{\prime }}\mathrm{\ne }{m}_e$, and its word $(a,b)$ satisfies $a<b$ and $(a,b)\prec ({\lambda }_e(m),{\lambda }_{e+1}(m))$ because it is lexicographically first. Define $k:=m_0⋗\cdots ⋗m_{e-1}⋗y^{\mathrm{\prime }}⋗m_{e+1}⋗\cdots ⋗m_n$.

Setup of (ii). Fix a rooted interval $([v,w],c)$ of $[x,y]$ and put $k:=\rho (v,w)$; we treat $k\ge 1$ and return to $k=0$ below. For a subset $S$ of $\{1,\dots ,k-1\}$ write $k-S:=\{k-s:s\in S\}$. For $T\subseteq \{1,\dots ,k-1\}$ let $f(T)$ be the number of maximal chains $m$ of $[v,w]$ (maximal in the poset $[v,w]$, carrying the labeling induced by the root chain $c$ as in [F2]) with $D(m)\subseteq T$, and for $S\subseteq \{1,\dots ,k-1\}$ let $\alpha (S)$ be the number of strict chains $w=y_0>y_1>\cdots >y_t=v$ with $t\ge 1$ whose rank set $\{\rho (y_i)-\rho (v):1\le i\le t-1\}$ equals $S$. Both are finite counts by [F9], and by step 1.1 the rank set of each such chain is a subset of $\{1,\dots ,k-1\}$.

Refinement construction. Given a strict chain $w=y_0>y_1>\cdots >y_t=v$ with rank set $S$, construct a maximal chain $m$ of $[v,w]$ top-down: starting from the top segment $[y_1,y_0]$ and continuing downwards, replace the segment $[y_i,y_{i-1}]$ by the unique increasing maximal chain of the rooted interval $([y_i,y_{i-1}],c_i)$, where $c_i$ is the original root $c$ extended by the part already constructed from $w$ down to $y_{i-1}$, so it ends at the upper endpoint $y_{i-1}$ (and $c_1=c$). Each replacement exists and is unique by (L) of [F3], and the resulting chain is a maximal chain of $[v,w]$. Inside each segment the word is increasing, so a descent of $\lambda (m)$ can occur only at a junction $y_i$, $1\le i\le t-1$, whose word position is $k-(\rho (y_i)-\rho (v))\in k-S$; hence $D(m)\subseteq k-S$.

Verification of the replacement. By [F2] the chain $k$ of step 2.1 is a maximal chain of $[x,y]$: it has length $n$, and each of its steps is a cover of $P$. Its word agrees with $\lambda (m)$ in positions $1,\dots ,e-1$ because $k$ and $m$ share the chain $m_0⋗\cdots ⋗m_{e-1}$ and the covers among these vertices, while at positions $e$ and $e+1$ the entries are $(a,b)$ and $({\lambda }_e(m),{\lambda }_{e+1}(m))$ with $(a,b)\prec ({\lambda }_e(m),{\lambda }_{e+1}(m))$; hence $\lambda (k)\prec \lambda (m)$. Moreover $k\cap m=m\setminus \{m_e\}$: the only vertex of $m$ strictly between $m_{e+1}$ and $m_{e-1}$ is $m_e$ and $y^{\mathrm{\prime }}\mathrm{\ne }{m}_e$, while every other vertex of $m$ lies outside that open interval, so $\mathrm{\mid }k\cap m\mathrm{\mid }=\mathrm{\mid }m\mathrm{\mid }-1$; and since $d<e<g$, step 1.3 gives $m^{\mathrm{\prime }}\cap m\subseteq \{m_i:i\le d\text{ or }i\ge g\}\subseteq m\setminus \{m_e\}=k\cap m$.

Truncation construction and the count. Conversely, given a maximal chain $m$ of $[v,w]$ with $D(m)\subseteq k-S$, keep the elements $m_j$ with $k-j\in S$; these are exactly $\mathrm{\mid }S\mathrm{\mid }$ indices in $\{1,\dots ,k-1\}$, and together with the endpoints $w=m_0$ and $v=m_k$ they form a strict chain of $\mathrm{\mid }S\mathrm{\mid }+1$ steps whose rank set is $S$. Between two consecutive kept elements there is no descent of $D(m)$: a junction $m_i$ strictly between two consecutive kept elements has $k-i\mathrm{\notin }S$, hence $i\mathrm{\notin }k-S$, and $D(m)\subseteq k-S$ gives $i\mathrm{\notin }D(m)$; so the word of each segment is weakly increasing, hence strictly increasing by (N), hence the segment is the unique increasing chain of its rooted interval by (L), so refining the kept chain returns $m$. Thus the constructions of step 3.1 and of this step are mutually inverse bijections, and $\alpha (S)=f(k-S)$ for every $S\subseteq \{1,\dots ,k-1\}$.

Facets and the open interval. Interpreting the maximal chains as facets of the order complex by [F5], step 3.2 says that for facets $C_{m^{\mathrm{\prime }}}$ preceding $C_m$ in the lexicographic order of label words there is a facet $C_k$ with $C_{m^{\mathrm{\prime }}}\cap C_m\subseteq C_k\cap C_m$ and $\mathrm{\mid }{C}_k\cap C_m\mathrm{\mid }=\mathrm{\mid }{C}_m\mathrm{\mid }-1$, and $\lambda (k)\prec \lambda (m)$ so that $C_k$ precedes $C_m$; this is the pairwise facet criterion of the statement. Indeed, every face of $C_m$ shared with an earlier facet lies in an earlier intersection obtained by deleting one vertex from $C_m$. Distinct facets have the same cardinality by [F2], so no earlier intersection is larger; hence the intersection of the simplex on $C_m$ with the union of earlier facet simplices is pure of codimension one, which is the shelling condition. A chain of the open interval $(x,y)$ is contained in no larger chain of $(x,y)$ precisely when, after adjoining $x$ and $y$, it becomes a maximal chain of $[x,y]$: if it could be enlarged inside $(x,y)$, so could the enlarged chain in $[x,y]$, and conversely an enlargement in $[x,y]$ of a chain already containing $x$ and $y$ lies in $(x,y)$. Hence the facets of $\mathrm{\Delta }((x,y))$ are the sets $m\setminus \{x,y\}$ for maximal chains $m$ of $[x,y]$, and since $x,y\in C_k\cap C_m$, deleting $x,y$ from all facets preserves $C_{m^{\mathrm{\prime }}}\cap C_m\subseteq C_k\cap C_m$ and gives $\mathrm{\mid }(C_k\cap C_m)\setminus \{x,y\}\mathrm{\mid }=\mathrm{\mid }{C}_m\setminus \{x,y\}\mathrm{\mid }-1$. For $n=0$ or $n=1$ there is only one maximal chain and one open-interval facet, the empty face, so the shelling condition is vacuous.

Tied words. Suppose instead that $\lambda (m^{\mathrm{\prime }})=\lambda (m)$ with $m^{\mathrm{\prime }}\mathrm{\ne }m$. The analysis of step 1.3 applies verbatim with the single change that the window words of $m$ and $m^{\mathrm{\prime }}$ coincide; that common window is again not increasing, since if it were increasing both window subchains would be increasing maximal chains of the same rooted interval and, being distinct because $m_i\mathrm{\ne }{m}_i^{\mathrm{\prime }}$ for $d<i<g$, would contradict the uniqueness in (L). So there is again a descent ${\lambda }_e(m)>{\lambda }_{e+1}(m)$ at some $e\in \{d+1,\dots ,g-1\}$, and steps 2.1 and 3.2 produce a maximal chain $k$ with $\lambda (k)\prec \lambda (m)=\lambda (m^{\mathrm{\prime }})$, $\mathrm{\mid }k\cap m\mathrm{\mid }=\mathrm{\mid }m\mathrm{\mid }-1$ and $m^{\mathrm{\prime }}\cap m\subseteq k\cap m$.

Möbius inversion on the Boolean lattice. Put $g(S):=\mathrm{\#}\{$maximal chains $m$ of $[v,w]$ with $D(m)=S\}$ for $S\subseteq \{1,\dots ,k-1\}$; then $f(T)={\sum }_{S\subseteq T}g(S)$ for every $T$, because each maximal chain has exactly one descent set and $D(m)\subseteq T$ if and only if $D(m)=S$ for some $S\subseteq T$. By the Möbius values of the Boolean lattice [F7] and Möbius inversion [F8], $g(S)={\sum }_{T\subseteq S}(-1{)}^{\mathrm{\mid }S\setminus T\mathrm{\mid }}f(T)$ for every $S$; at $S=\{1,\dots ,k-1\}$ this gives, using step 4.1 and the involution $T\mapsto k-T$ of the subsets of $\{1,\dots ,k-1\}$ (which is closed under $s\mapsto k-s$), $\mathrm{\#}\{m:D(m)=\{1,\dots ,k-1\}\}={\sum }_{U\subseteq \{1,\dots ,k-1\}}(-1{)}^{k-1-\mathrm{\mid }U\mathrm{\mid }}\alpha (U)\mathrm{.}$

Shelling order. Every linear order of the maximal chains of $[x,y]$ that extends the strict lexicographic order of their label words makes the complex $\mathrm{\Delta }([x,y])$ shellable in the pairwise criterion: given earlier $C_{m^{\mathrm{\prime }}}$ and later $C_m$, either $\lambda (m^{\mathrm{\prime }})\prec \lambda (m)$, when step 4.2 supplies $C_k$ with $\lambda (k)\prec \lambda (m)$ and hence before $C_m$, or $\lambda (m^{\mathrm{\prime }})=\lambda (m)$, when step 4.3 supplies such a $C_k$; the remaining possibility $\lambda (m)\prec \lambda (m^{\mathrm{\prime }})$ cannot occur in such an order. Deleting the endpoints $x,y$ from all maximal chains, the same order and the same replacements witness the pairwise facet criterion for $\mathrm{\Delta }((x,y))$, whose facets are the maximal chains of $(x,y)$ by step 4.2. In particular, ordering facets by their label words with ties broken arbitrarily is a shelling order, which is the statement of (i).

Evaluation and the formula in rank $k\ge 1$. By step 2.2 and 1.1, each strict chain with $t$ steps contributes to $\alpha (S)$ with $\mathrm{\mid }S\mathrm{\mid }=t-1$, so the alternating sum of step 5.1 equals ${\sum }_{t\ge 1}(-1{)}^{k-t}{c}_t(v,w)=(-1{)}^k{\sum }_{t\ge 1}(-1{)}^t{c}_t(v,w)=(-1{)}^k\mu (v,w)$ by the chain-sum identity of step 1.2; hence the number of maximal chains with $D(m)=\{1,\dots ,k-1\}$, that is, of strictly falling maximal chains by [F4], equals $(-1{)}^k\mu (v,w)$, which is the stated formula $\mu (v,w)=(-1{)}^{\rho (v,w)}\cdot \mathrm{\#}\{$strictly falling maximal chains$\}$ since $k=\rho (v,w)$. For $k=0$ we have $v=w$; then $\mu (v,v)=1$ by [F6] and the single rank-$0$ maximal chain has an empty label word and is vacuously falling, so the formula holds as well.

Both parts are proved. Part (i) is steps 4.2, 4.3 and 5.2, and part (ii) is steps 1.2 and 6.1 together with step 2.2 for the definition of the counted chains: since the rooted interval $([v,w],c)$ was arbitrary, the formula holds for every one of them, with $k=\rho (v,w)$; under (N) falling and strictly falling agree on each maximal chain by [F4], so 'falling' may replace 'strictly falling'; and the conventions $\mu (v,v)=1$ with the singleton maximal chain having an empty label word and being vacuously falling, and $\rho (v,w)=1$ with the open interval $(v,w)$ empty and the single maximal chain with one-term label word vacuously falling, are the rank-zero and rank-one cases of the formula. All counts are finite by [F9] and the argument uses no choice principle: the unique increasing chains and the single Boolean inversion are determined data, not selected from families.