SB-labelings and posets with each interval homotopy equivalent to a sphere or a ball
We introduce a new class of poset edge labelings for locally finite lattices which we call $SB$-labelings. We prove for finite lattices which admit an $SB$-labeling that each open interval has the homotopy type of a ball or of a sphere of some dimension. Natural examples include the weak order, the Tamari lattice, and the finite distributive lattices.
\section{Introduction}

Anders Bj\"orner and Curtis Greene have raised the following question (personal communication of Bj\"orner;  see also \cite{Gr} by Greene).

\begin{qn}
Why are there so many posets with the property that every interval has M\"obius function equalling $0, 1$ or $-1$?  Is there a unifying explanation?
\end{qn}


This paper introduces  a new type of edge labeling that  a finite lattice may have  which we dub an $SB$-labeling.  We prove for finite lattices admitting such a labeling that each  open interval has order complex that  is contractible or is  homotopy equivalent to a sphere of some dimension.  This immediately yields that the M\"obius functions only takes the values $0,\pm 1$ on all intervals of the lattice.  The construction and verification of validity of such labelings seems quite readily achievable on a variety of examples of interest.   The name  $SB$-labeling was chosen with $S$ and $B$  reflecting the possibility of spheres and balls, respectively.  
This method will easily  yield  that each interval in the weak Bruhat  order of a finite Coxeter group, in  the Tamari lattice, and in any finite distributive lattice  is  homotopy equivalent to a ball or a sphere of some dimension.    In particular, this method may be applied to non-shellable examples, as the weak Bruhat order for finite Coxeter groups will demonstrate.

Section ~\ref{disc-morse-bg-section} quickly reviews background that will be needed later in the paper.   Section ~\ref{labeling-section} introduces a new class of edge labelings that a finite lattice may have which we call $SB$-labelings.    This section gives two different formulations for  the definition of $SB$-labeling and shows  that the first of these two versions  of the definition for  $SB$-labeling will imply that each open interval $(u,w)$ in a finite lattice $L$   is homotopy equivalent to a ball or a sphere, with the homotopy type being that of a sphere if and only if $w$ is a join of atoms of the interval.   Section ~\ref{equivalence-section}  provides a proof that these two formulations of the definition for $SB$-labeling  are equivalent to each other.  The value in this may come from the fact that the second formulation is a local condition that appears to be more easily verifiable for families of posets of interest.    Section ~\ref{application-section} gives  applications, namely it provides   $SB$-labelings for  the finite distributive lattices, the weak order of any finite Coxeter group, and the Tamari lattices. 

\section{Background}
\label{disc-morse-bg-section}



   A  partially ordered set  (poset) $P$ is a {\bf lattice} if each pair of elements $x,y\in P$ has a unique least upper bound, which we denote $x\vee y$, and a unique greatest lower bound, which we denote $x\wedge y$.  In particular, we denote by $\hat{0}$ (resp. $\hat{1}$)  the unique minimal (resp. maximal)  element of a finite lattice.   A {\bf cover relation} $u\prec v  $ in a poset  $P$ is a pair of elements  $u <  v$ with the further requirement that $u\le z \le v$ implies either $u=z$ or $z=v$. 
  An {\bf open interval } in $P$, denoted $(u,v)$,  is the subposet of elements $z$ satisfying $u < z < v$.  Likewise, a {\bf closed interval} $[u,v]$ is the subposet comprised of those $z\in P$ such that $u\le z \le v$.  We will  sometimes refer to the open interval $(\hat{0},\hat{1})$ in a finite lattice $L$ as the {\bf proper part } of $L$.


The {\bf  M\"obius function}, denoted $\mu $,   of a finite partially ordered set  $P$ is defined recursively as follows.  
For each $u\in P$ we have $\mu_P (u,u) = 1$.  For each $u <  v$, $\mu_P(u,v) = -\sum_{u\le x < v} \mu_P(u,x)$.   M\"obius functions provide the coefficients in inclusion-exclusion counting formulas. 
The {\bf order complex} of a finite poset $P$  
is the simplicial complex, denoted 
$\Delta (P)$, whose $i$-faces
are chains 
$ v_0 < \cdots < v_i  $
of $i+1$ comparable poset 
elements.  It is well-known for each $u<v$ in $P$ 
that $\mu_P (u,v)  = \tilde{\chi }(\Delta (u,v))  $ where $\Delta (u,v)$ denotes the order 
complex of the open interval $(u,v)$.
Sometimes we will speak of the homotopy type of a  poset or poset interval, by which we  mean the homotopy type of the order complex of that poset or poset interval.  


Our focus throughout this paper  will be on posets
in which the order complex of each  open interval $(u,v)$ will turn out to  
be  homotopy equivalent to a ball or a 
sphere, implying that  $\tilde{\chi } (\Delta (u,v))$ and hence $\mu_P(u,v)$ equals $0, 1, $ or $-1$ 
for each pair $u<v$.  
A key tool underlying  our work will be 
the crosscut theorem, which we review next.


Recall  from \cite{bjorner-top-methods} (see also \cite{Bj-81}, \cite{Folkman}, \cite{Rota})
 that a subset $C$ of a poset $P$ is called a {\bf crosscut} if 
\begin{enumerate}
\item
$C$ is an antichain.  
\item
For every finite chain $\sigma $ in $P$ there exists an element of $C$ that is comparable to every element of $\sigma $.
\item
For each $A\subseteq C$ which is bounded, i.e. which has an upper (resp. lower) bound, then the join  (resp. meet) of the elements of $A$ exists as an element of $P$.
\end{enumerate}

Define the {\bf crosscut complex} given by a crosscut $C$ to be the simplicial complex whose faces are those subsets of $C$ which are bounded.

\begin{rk}
In a finite lattice $L$  (and hence  also in the proper part of $L$), the set of atoms is a crosscut.  Our focus in this paper will be on making use of the next theorem with the atoms as the chosen crosscut.
\end{rk}

\begin{thm}[Crosscut Theorem, Theorem 10.8 in \cite{bjorner-top-methods}]\label{crosscut-theorem}
The crosscut complex given by any crosscut of a finite poset $P$ is homotopy equivalent to the order complex of $P$.
\end{thm}

\begin{rk}
If one can prove that distinct sets of atoms have distinct joins, then the crosscut theorem will imply that the subposet of joins of atoms is homotopy equivalent to the entire poset.  We will use this in the special case where our poset is the proper part of a finite lattice.
 An $SB$-labeling, a new type of edge labeling which we introduce shortly, will guarantee that distinct sets of atoms have distinct joins.  
\end{rk}




\section{A new class of edge  labelings: $SB$-labelings}\label{labeling-section}


 
 Next we introduce a new class  of edge-labelings  which we call 
 $SB$-labelings.  We will call a lattice admitting such a labeling an $SB$-lattice.   We will give two different formulations of the definition of $SB$-labeling, and then  
 we will prove that these are equivalent to each other.   One formulation will be convenient for proving topological consequences of having an SB-labeling.  In particular, we use this to   prove that each open interval in a  finite lattice with an SB-labeling is homotopy equivalent to a ball or a sphere.  The other formulation seems likely to be more convenient for constructing SB-labelings on examples.  
 
 Later in the paper we will indeed demonstrate  that several well known lattices admit SB-labelings, in spite of the fact that some of these lattices cannot possibly be shellable.
 In particular, we  will apply this method to the weak Bruhat order of a finite Coxeter group, 
  the Tamari lattice,   and the  finite 
 distributive lattices, giving short, uniform proofs of this sort of topological structure in some cases which had already been handled in the past by other methods.  
  
  \begin{rk}
  It is natural to ask if  this notion for edge labelings may be extended to a more general notion for chain labelings (in the sense of  \cite{BW-on-lex}).  However, key properties of these $SB$ labelings in fact will  rely in an essential way on our usage of edge labelings rather than chain labelings.  Therefore, we confine ourselves to  considering edge labelings.
  \end{rk}
  
 
\begin{defn}\label{lattice-labeling}
An edge-labeling $\lambda $ of a finite lattice $L$ is a {\bf lower $SB$-labeling} if it may be constructed as follows.  Begin with a label set $S$ such that there is a subset  $\{ \lambda_a | a\in A(L) \}  $ of $S$  whose members are in bijection with the set $A(L)$ of atoms of  $L$.
\begin{enumerate}
\item
No two labels upward from $\hat{0}$ to  distinct atoms may  be equal. 
This allows us to define  the label $\lambda_a $  on each  cover relation $\hat{0}\prec a$ to be the label corresponding to that atom 
$a$.  
\item
The set of  labels $\lambda (M)$  occurring with positive multiplicity  on any
saturated chain $M$  on any interval that can be expressed as 
$[\hat{0}, a_{i_1}\vee \cdots \vee a_{i_r} ] $ for  $ \{  a_{i_1},\dots
,a_{i_r} \}  \subseteq A(L)$ is exactly $\{ \lambda_{a_{i_j}} | a_{i_j} \in A(L) \} $.
\end{enumerate}
When an edge labeling $\lambda $ for a finite lattice $L$  meets  these conditions upon restriction to each  closed interval of $L$, then we call such a labeling an {\bf $SB$-labeling}.  We call a lattice  with an $SB$-labeling an {\bf $SB$-lattice}. 
\end{defn}


\begin{rk}
Notice that condition (2) above implies for $S, T$ distinct sets of atoms, that the join of the set of atoms in $S$ does not equal the join of the set of atoms in $T$.  In particular, this implies that the subposet of joins of atoms is a Boolean algebra.
\end{rk}


Now we give what we call  the  ``index 2 formulation of  $SB$-labeling'', a type of labeling that we will prove is equivalent to the notion of $SB$-labeling in Theorem ~\ref{equivalent-definitions}.   In light of Theorem ~\ref{equivalent-definitions}, one may henceforth take either definition as a definition of $SB$-labeling.

\begin{defn}
 The {\bf index 2 formulation of   $SB$-labeling}  is an edge labeling on a  finite lattice $L$ satisfying the following conditions for each  $u,v,w \in L$ such that 
 $v$ and $w$  both cover $u$:
\begin{enumerate}
\item
$\lambda (u,v)\ne \lambda (u,w)$
\item
Each saturated chain on the interval $[u,v\vee w]$ uses both of these labels $\lambda (u,v)$ and $\lambda (u,w)$ a positive number of times.
\item
None of the saturated chains on the interval $[u,v\vee w]$ use any other types of labels besides $\lambda (u,v)$ and $\lambda (u,w)$.
\end{enumerate}
\end{defn}

\begin{thm}\label{equivalent-definitions}
An edge labeling on a finite lattice is an $SB$-labeling if and only if it satisfies the index 2 formulation for $SB$-labeling.
\end{thm}

\begin{proof}
Theorem ~\ref{cover-enough} proves that the  index 2 formulation of  $SB$-labeling will always give an $SB$-labeling. 
On the other hand, if $\lambda $ is an $SB$-labeling, then Condition (1) for $SB$-labelings  directly gives Condition (1) in the index 2 formulation for $SB$-labelings.    Condition (2)  for $SB$-labelings specialized to the  case of a join of two atoms yields exactly   conditions (2) and (3) of the index 2 formulation of  $SB$-labeling.  
\end{proof}



\begin{ex}
In the case of the weak Bruhat order of a finite Coxeter group, we will label each cover relation $u\prec s_i u$ with the label $s_i$ and will prove that this labeling  is an $SB$-labeling.  For instance, the weak order interval $[\hat{0},s_1s_2]$ has a single saturated chain, and it uses the labels $s_1$ and $s_2$.  The label $s_1$  corresponds to an atom while the label $s_2$ does not.
\end{ex}


\begin{thm}\label{homotopy-type-for-atom-labeled-lattices}
Suppose $L$ is a finite lattice admitting a lower  $SB$-labeling, and suppose  
$|L| > 2$.   If  $v\in L $ is a join of $d$  atoms for some $d>1$, 
  then  $(\hat{0} ,  v )$
   has order complex homotopy equivalent to  a sphere $S^{d-2}$.  Otherwise,  
   $(\hat{0},v)$ has order complex that is contractible.
\end{thm}

\begin{proof}
Each subset of the atoms  has a distinct join, by virtue of the fact that  the set of labels appearing on the edges of all of the  saturated chains upward to a join of atoms is exactly that set of atoms.  
But this implies  that the crosscut complex for $(\hat{0},v)$ given by the atoms is the boundary of a simplex if $v$ is a join of atoms and is the entire simplex otherwise.  In particular, this means that  the crosscut complex is homotopy equivalent to a sphere $S^{d-2}$ if $v$ is a join of atoms and is contractible otherwise.
Now the Crosscut Theorem (cf. Theorem ~\ref{crosscut-theorem}) yields the result.  
\end{proof}


\begin{thm} \label{thm:sb}
If $L$ is an SB-lattice, then  each open interval is homotopy equivalent to a ball or a sphere of some dimension.  Moreover,  $\Delta (u,v)$ is homotopy equivalent to a sphere if and only if $v$ is a join of atoms of the interval, in which case it is a sphere $S^{d-2}$ where $d$ is the number of atoms in the interval.
\end{thm}

\begin{proof}
This follows from Theorem  
~\ref{homotopy-type-for-atom-labeled-lattices}.
\end{proof}

We conclude this section with some relaxations that may be made in the hypotheses of our main results without changing the conclusions.

\begin{rk}\label{locally-finite-variant}
In the notion of $SB$-labeling, we may replace the finiteness requirement for our lattices by instead requiring them to be locally  finite  with  a unique minimal element.   
Our proofs all go through unchanged in such cases, allowing us to call such lattices $SB$-lattices and draw all of the same conclusions.  Young's lattice will provide one such example.  
\end{rk}


\begin{defn}
Let us say that a finite poset $P$ with unique minimal and maximal elements  is an {\bf atom-near-lattice} if each pair of elements $u,v \in P$ with $u<v$  has the property that each collection $S$  of atoms of the closed interval $[u,v]$ has a unique least upper bound $\vee_{a\in S} a$. 
\end{defn}

\begin{rk}
It is proven in Lemma 2.1 of  \cite{BEZ} that this atom-near-lattice property in fact implies that $P$ is a lattice.  
This property may be easier to check in examples of interest than the property of being a lattice.  Our proofs actually only rely upon this formulation of the lattice property.
\end{rk}


\section{Index 2 formulation is equivalent to $SB$-labeling}\label{equivalence-section}

This section proves the equivalence of our two different definitions for $SB$-labeling.
To this end, we will use the next  two  notions to prove that every labeling meeting the conditions in the index 2 formulation for $SB$-labeling is an $SB$-labeling.

\begin{defn}
We say that a pair of saturated chains $M_1, N_1$ in a finite lattice
are connected by a {\bf basic move} if $M_1$ and $N_1$  coincide except on an open interval $(u,v)$ where $u\prec x$ in $M_1$ and $u\prec y$ in $N_1$ with $x\ne y$ and with  $v = x\vee y$.  
\end{defn}

\begin{ex}\label{braid-special}
For example, in any interval $[u,wu]$ in the weak order the basic moves are given by the long and short braid moves on reduced expressions for the  Coxeter group element $w$. 
\end{ex}

\begin{defn}
Define the {\bf total length} of a closed interval $[u,v]$ to be the sum of the lengths of all the saturated chains in that interval.
\end{defn}





\begin{lem} \label{sat}  
Any two saturated chains on an interval $[a,b]$ in a finite lattice $L$ are  connected by a series of basic moves.
\end{lem}

\proof 
Suppose otherwise.    Then choose   an interval $[u,v]$ where this fails, making   the total length of the interval  as small as possible among all such examples.  Let $M_1$ and $N_1$ be two saturated chains on $[u,v]$ that are not connected by a series of basic moves.  Our minimality assumption on total length  ensures for $u\prec u_1$ in $M_1$ and $u\prec v_1$ in $N_1$ that we must have $u_1\ne v_1$.  We also may assume   $u_1\vee v_1 \ne v$, since otherwise there would be a single basic move connecting $M_1$ to $N_1$ by definition of basic move.
 

 Our plan in this case is to give a series of  steps $M_1\rightarrow M_2\rightarrow M_3\rightarrow N_1$ which convert $M_1$ to $N_1$ and to show that each of these three  steps may  be achieved through a series of basic moves, hence that their composition can as well. 
 Let $M_2$ be a saturated chain on $[u, v]$ which  agrees with $M_1$ except possibly on $(u_1,v)$;  $M_2$ is chosen to include $u_1\vee v_1$ (since $v\ne u_1\vee v_1$, we have $u_1\vee v_1 < v$). Since the  interval $[u_1, v]$ has strictly smaller total length than $[u,v]$ and $M_1$ agrees with $M_2$ except on  this interval, we can conclude  there is  a  series of  basic moves converting the restriction of $M_1$ to $[u_1,v ]$ to the restriction of $M_2$ to this same interval, which in turn gives basic moves converting $M_1$ to $M_2$ in $[u,v]$.  Now we similarly may convert $M_2$ to a chain $M_3$ which coincides with $M_2$ except on the interval $(u,u_1\vee v_1)$ and which has $u_1$ replaced by $v_1$;  this interval  also has strictly smaller total length than $[u,v]$, again implying the desired basic moves.  Finally, we note that $M_3$ only differs from $N_1$ on the proper part of the interval $[v_1,v]$, which yet again has strictly smaller total length than $[u,v]$, enabling us to find a series of basic moves converting $M_3$ to $N_1$, completing the result.
\qed

\begin{rk}
Lemma ~\ref{sat}  may be regarded as an abstraction of the idea that the lattice property for the weak Bruhat order of a finite Coxeter group  ensures that any two reduced expressions for the same Coxeter group element are connected by a series of long and short braid moves. 
 This implication in the case of the weak order appears as Theorem 3.3.1 in \cite{BB}.
\end{rk}


\begin{thm}\label{cover-enough}
If a finite lattice $L$ has an edge labeling that  satisfies the index 2 formulation for  an $SB$-labeling, then it is an $SB$-labeling.
\end{thm}

\begin{proof}
Let $\lambda $ be an edge-labeling for a finite lattice $L$ which meets the requirements for the index 2 formulation of an $SB$-labeling.  We will prove by induction on the number $r$ of atoms  that $\lambda $ also meets the requirements to be a lower $SB$-labeling.  In fact, this will imply it is an $SB$-labeling, by applying this argument to any closed interval to show we have a lower $SB$-labeling for each closed interval.

  The base case with 1 atom is tautologically true.  
  Let us suppose that   $\{ a_{i_1},\dots ,a_{i_r} \} $ is the set of atoms of $L$.  
 Now consider the interval  $L_{r-1} = [\hat{0},a_{i_1}\vee \cdots \vee a_{i_{r-1}}]$  within $L$.  By  induction, we may assume that  this  uses only the labels $\{ a_{i_1},\dots ,a_{i_{r-1}} \} $.  We will progressively build from $L_{r-1}$ a larger subposet $L_{r-1,1}$  of $L$ all of whose cover relations are cover relations of $L$ with the further property that it includes an upper bound $m$ for $\{ a_{i_1}\dots ,a_{i_r} \} $.  We will deduce from $a_{i_1}\vee \cdots \vee a_{i_r} \le m$ that $[\hat{0},a_{i_1}\vee\cdots\vee a_{i_r} ]$ also uses at most the labels $\{ a_{i_1},\dots ,a_{i_r}\} $.
 Finally, we will also  show that each saturated chain from $\hat{0}$ to 
$a_{i_1}\vee \cdots \vee a_{i_r}$ in fact uses all of these labels.

First we add to  $L_{r-1}$  the additional atom  $a_{i_r} $ as well as all elements belonging to  the closed interval $[\hat{0},  a_{i_1}\vee a_{i_r}]$   to obtain a new  poset  $L_{r-1}^{(1)}$.  By condition (3) in the index 2 formulation of $SB$-labeling, this slightly larger poset  still only uses the allowed edge labels, since all of the new cover relations are in the interval $[0,a_{i_1}\vee a_{i_r}]$ which only uses the labels $a_{i_1}$ and $a_{i_r}$.  Now either $a_{i_1}\vee a_{i_r}\in L_{r-1}$, in which case we are done constructing $L_{r-1,1}$, or there are at least two different maximal elements in
$L_{r-1}^{(1)}$.  For each maximal element $m_i^{(1)} \in L_{r-1}^{(1)}$, let $P_i$ be the subposet of elements  $x\in L_{r-1}^{(1)}$ satisfying $x\le m_i^{(1)}$.  Choose $u^{(1)}$ to be an element that is contained in both $P_j$ and $P_k$ for some  $j\ne k$ such that there are no elements strictly greater than $u^{(1)}$ also having the property of being contained in some $P_{j'}$ as well as some $P_{k'}$ for $j'\ne k'$; finiteness of $L_{r-1}^{(1)}$ guarantees the existence of such an element $u^{(1)}$.

 Now consider cover relations 
$u^{(1)}\prec x_1^{(1)}$ and $u^{(1)}\prec x_2^{(1)}$ in $L_{r-1}^{(1)}$  such that $x_1^{(1)} \le m_i^{(1)}$ and $x_2^{(1)} \le m_j^{(1)}$ in $L_{r-1}^{(1)}$.  Obtain from $L_{r-1}^{(1)}$ a strictly  larger poset $L_{r-1}^{(2)}$ by adding all elements and cover relations from the interval $[u^{(1)},x_1^{(1)} \vee x_2^{(1)} ]$.  Again by condition   (3), this cannot introduce any new labels.
 Again, we either have a unique maximal element or we  have two different maximal elements, allowing us to apply this same procedure and do so  repeatedly until we have a unique maximal element $m$.  Specifically, at the $k$-th iteration of the procedure, the input is a poset  $L_{r-1}^{(k-1)}$ having distinct  maximal elements.
  This allows us to find an element $u^{(k)}$ satisfying the same criterion at this step that  $u^{(1)}$ satisfied at the first step, now using distinct maximal elements $m_i^{(k-1)}$ and $m_j^{(k-1)}$.  This in turn ensures there are elements $x_1^{(k)}$ and $x_2^{(k)}$ with $u\prec x_1^{(k)} \le m_i^{(k-1)}$ and $u\prec x_2^{(k)} \le m_j^{(k-1)}$ such that $x_1^{(k)}$ is not less than or equal to any maximal element other than $m_i^{(k-1)}$ and
  $x_2^{(k)}$ is not less than or equal to any maximal element other than $m_j^{(k-1)}$.
 
  We obtain $L_{r-1}^{(k)}$ as the poset $L_{r-1}^{(k-1)}$  with the additional elements and cover relations from the  interval $[u^{(k)},x_1^{(k)} \vee x_2^{(k)}]$  added to it. 
 

 We  iterate  this process
   until it yields a poset $L_{r-1,1}$  with a unique maximal element $m$.
 This process must terminate within finitely many iterations due to finiteness of our original  lattice.
    By construction, the unique maximal element $m$  of $L_{r-1,1}$
         will  be an upper bound for $\{ a_{i_1},\dots ,a_{i_r} \} $, and we will  have only used the labels $a_{i_1},\dots ,a_{i_r}$ on the poset $L_{r-1,1}$  obtained by this process.   The fact that we only ever insert cover relations from the original lattice implies that each saturated chain in $L_{r-1,1}$  from $\hat{0}$ to $m$ is also a saturated chain in the original lattice $L$.    Since 
$a_{i_1}\vee\cdots \vee a_{i_r} \le m$ in $L$,   there is a saturated chain from $\hat{0} $ to $m$ in $L$ which includes the element $a_{i_1}\vee \cdots \vee a_{i_r}$.  By   Lemma ~\ref{same}, this  implies that  the set of labels on each saturated chain from $\hat{0}$  to $a_{i_1}\vee \cdots \vee a_{i_r}$  must be a subset of the set of labels on a saturated chain from $\hat{0}$ to $m$.  Thus,  no labels other than $a_{i_1},\dots ,a_{i_r}$ appear on any saturated chain  in $[\hat{0},a_{i_1}\vee\cdots \vee a_{i_r}]$. 

Now let us show  that each saturated chain from $\hat{0} $ to $a_{i_1}\vee \cdots \vee a_{i_r}$ uses each of the   labels $\{ a_{i_1}, \dots ,a_{i_r}\} $ a positive number of times.
 The point is that each atom $a_{i_j}$ for $1\le j\le r$  is in some saturated chain in $[\hat{0}, a_{i_1}\vee\cdots \vee a_{i_r}]$, implying that there exists a saturated chain using the label $a_{i_j}$;
   but this implies that all saturated chains use $a_{i_j}$ for each $1\le j\le r$, by Lemma ~\ref{same}. 
 In conclusion, we have shown that each saturated chain uses exactly the set of labels $\{ a_{i_1},\dots ,a_{i_r} \} $,  each with positive multiplicity.
\end{proof}


\begin{cor} \label{joins} If a finite lattice $L$ satisfies the  conditions for the index 2 formulation of $SB$-labeling, then 
for any collection $\{ a_{i_1},\dots ,a_{i_d} \} $ of atoms of $L$, the interval $[\hat{0}, a_{i_1}\vee \cdots \vee a_{i_d} ]$ has no atoms  
other than $\{ a_{i_1},\dots ,a_{i_d} \}  $.
\end{cor}


\begin{lem} \label{2a} 
Let  $L$ be a finite lattice with an edge labeling $\lambda $  which  satisfies the index 2 formulation for an $SB$-labeling.  Then for any $u,v,w\in L $ with $v$ and $w$ both covering $u$, the  interval $[u,v\vee w]$   cannot have any atoms other than $v$ and $w$.
\end{lem}

\proof
If there were another atom $x$ in $[u,v\vee w]$, then we must have $\lambda (u,x) \ne \lambda (u,v)$ and $\lambda (u,x) \ne \lambda (u,w)$.   We also must have $x\vee v\le v\vee w$ since $x\le v\vee w$ and $v \le v\vee w$.  By virtue of $\lambda $ meeting the index 2 formulation for $SB$-labeling, we have that every saturated chain on the interval $[u,x\vee v]$ must use the label $\lambda (u,x)$.  But then there will be saturated chains on the interval $[u,v\vee w]$ which also must use the label $\lambda (u,x)$, a contradiction.
\qed
 
 \medskip
 
 
 
 \begin{lem} \label{same}
 If  an edge labeling $\lambda $ on a finite lattice $L$ 
 meets the conditions for the index 2 formulation of $SB$-labeling, then this   guarantees for each interval $[a,b]$ in $L$  that any two saturated chains $M_1$ and $N_1$  on $[a,b]$  must   use the same set of labels  each a positive number of times, though not necessarily  with the same multiplicities. 
\end{lem}

\proof 
 Lemma \ref{2a} implies that   any two saturated chains $M_1$ and $N_1$  on an interval $[a,b]$  in a finite lattice  that are connected by a series of basic moves  use the same set of labels (though not necessarily with the same multiplicities).  Lemma \ref{sat} checks that any two saturated chains $M_1$ and $N_1$  between $a$ and $b$ in a finite lattice  are connected by a series of basic moves, so  the result follows. \qed

\section{Applications}\label{application-section}


Now we turn to applications, beginning with finite distributive lattices.  In this first example, the $SB$-labeling  we give is  also a well-known  $EL$-labeling, implying the posets are shellable.  The homotopy type of the intervals in finite distributive lattices was determined in \cite{Bjorner}  indirectly by virtue of finite distributive lattices also  being finite  supersolvable lattices, relying on an earlier $R$-labeling given by Stanley in \cite{Stanley}  for finite supersolvable lattices.

\begin{thm}\label{finite-distributive-lattice}
Any finite distributive lattice  is an $SB$-lattice.   
\end{thm}

\begin{proof}
We  will use the fact that any finite distribute lattice  $L$ is the poset $J(P)$ of order ideals of a finite poset $P$ ordered by inclusion (cf. \cite{ec1}, Theorem 3.4.1).  This allows us to regard each cover relation $u\prec v$ as adding to the order ideal associated to $u$ 
a single element $p\in P$  We use this element $p$  as the label for $u\prec v$.  Whenever we have $u\prec v$ and $u\prec w$, then this implies that there are two different elements of $P$, either of which  may individually  be added to the order ideal given by $u$ to obtain a new order ideal.  Therefore, $v\vee w$ covers both $v$ and $w$ with the further property that there cannot be any other elements $z$ with $u < z < v\vee w$.  From this,  Conditions (1), (2) and (3)  for the index 2 formulation for  $SB$-labeling follow directly.
\end{proof}

Recall that Young's lattice is the poset of integer partitions regarded as Young diagrams, with $u\prec v$ whenever $v$ is obtained from $u$ by adding a single box.  
Since Young's lattice is a locally finite,  distributive lattice with a unique minimal element,  Theorem ~\ref{finite-distributive-lattice} together with Remark ~\ref{locally-finite-variant} allows us to  conclude:
 
\begin{cor}
Young's lattice is an  $SB$-lattice. 
\end{cor}

Next we turn to a non-shellable example, the weak Bruhat order  on the elements of a  finite Coxeter group $W$.
Let $S$ be the set of  simple reflections generating $W$.   The weak Bruhat order has as its  cover relations each  $w\prec s_iw$ for $w\in W $ and $s_i\in S$ with $l(w) < l(s_i w)$, letting  $l(w)$ denote the Coxeter-theoretic length of $w$.  See e.g. \cite{BB} or \cite{Hu} for further background on Coxeter groups and on the  weak Bruhat order.    The homotopy type of each interval was originally determined in \cite{bj} (see also \cite{Ed} and \cite{EW} 
for related results regarding posets of regions).

\begin{thm}\label{weak-theorem}
The weak Bruhat  order for any finite Coxeter group $W$ is an  $SB$-lattice.   Moreover, an open  interval $(u,w)$ in $W$  is homotopy equivalent to a sphere $S^{d-2}$ if  $u^{-1}w$ is the longest element of a parabolic subgroup $J_S$ with $|S|=d$, and $(u,w)$ is contractible otherwise.
\end{thm}

\begin{proof}
See e.g. Theorem 3.2.1 in \cite{BB} for a proof that the weak Bruhat order of a finite Coxeter group  is a lattice.
We label each cover relation
$u\prec  v$ with the unique  simple reflection $s_i$ such that $v = s_iu$.
Consider  a pair of elements $u < w = s_{i_1}\cdots s_{i_r} u $ where $l(w) - l(u) = r$ for $l(u)$ denoting the Coxeter-theoretic length of $u$. 

Known results about finite Coxeter groups to be used later in our proof are:  
(1)  the isomorphism of Bruhat intervals $[u,w] \simeq [e,u^{-1}w]$ given in Proposition 3.1.6 in \cite{BB},  (2)  the characterization of the joins of finite sets of atoms in Lemma 3.2.3 in \cite{BB} as exactly those Coxeter group elements which may be regarded as the longest element of the parabolic subgroup generated by exactly  the simple reflections corresponding to the given finite set of atoms,  and (3) the fact that the longest element $w_0(S)$  for a parabolic subgroup $J_S$ has a reduced expression beginning with any letter of $S$.  
 This third assertion can be seen  by noting that  multiplying $w_0(S)$  on the right by any simple reflection in  $S$ must decrease the  length of $w_0(S)$.   



The requirements for  the index 2 formulation for $SB$-labeling  will now  follow from the following  observation that we justify next: for any two cover relations $u\prec v$ and $u\prec w$, there are unique saturated chains $u\prec v\prec \cdots \prec v\vee w$ and $u\prec w\prec\cdots \prec v\vee w$ on the interval $[u,v\vee w]$ and no other saturated chains on this interval; moreover,  these two saturated chains  have label sequences $s_i s_j s_i \cdots $ and $s_j s_i s_j \cdots $  each consisting of an alternation of only  the letters $s_i$ and $s_j$, with each label sequence having the same length $m(i,j)$ where $m(i,j)$ is the order of the Coxeter group element $s_is_j$.  In the case of $u=e$, this observation holds  by definition.  Otherwise,  it follows from the isomorphism in Proposition 3.1.6 of \cite{BB} already mentioned above, completing the proof that the weak Bruhat order of a finite Coxeter group is an $SB$-lattice.  

Finally, facts (2) and (3) above combine to imply that $w$ will be a join of atoms of the interval $[u,w]$  if and only if $u^{-1}w$ is the longest element of a parabolic subgroup of $W$.  Thus,  Theorem 
~\ref{thm:sb} implies  that  $[u,w]$ has the homotopy type of a sphere if and only if $u^{-1}w$ is the longest element of a parabolic subgroup of $W$.
\end{proof}

\begin{rk}
We note that facts (2) and (3) in the proof of Theorem ~\ref{weak-theorem} also imply that the only labels that may occur on an interval $[u,w]$ in which $w$ is a join of atoms of the interval are labels that occur on cover relations $u\prec x$ upward from $u$ to atoms of the interval.  Thus, we could have directly proved that  the weak Bruhat  order of a finite Coxeter group  was an $SB$-lattice without invoking the index 2 formulation of $SB$-lattice.    
\end{rk}



The Tamari lattice, our next example,  is a partial order on the binary bracketings of a word with $n$ letters.   Its significance comes in part from the fact that its Hasse diagram is the 1-skeleton of the associahedron, a polytope which goes back to work on homotopy associative $H$-spaces by Stasheff (cf.\cite{Stasheff}).  The number of elements in the Tamari lattice is a Catalan number.  It was proven to be non-pure shellable with each interval having the homotopy type of a ball or a sphere by Bj\"orner and Wachs in \cite{BW}.  Earlier results regarding its M\"obius function and implicitly regarding its topological structure also appear in \cite{Pallo}.

A  cover relation $u\prec v$ in the Tamari lattice results from 
replacing $((x, y),z))$   by $(x,(y , z))$  somewhere in the parenthesized expression for $u$ to obtain $v$, letting   the entities $x,y,z$ either be individual letters or themselves   larger bracketed expressions.     See e.g.  \cite{BW}, \cite{HT}, \cite{Lo}  for further background.  


\begin{thm}
The Tamari lattice is an SB-lattice.
\end{thm}

\begin{proof} 
 We regard each element as a binary bracketing of the word $1\cdots n$, so this consists of a sequence of $n-1$ left parentheses, $n-1$ right parentheses and $n$ letters being bracketed.  The minimal element of the Tamari lattice $L$ is the ``leftmost'' bracketing $((\cdots ( 1, 2) 3 ) \cdots ) n$ while the maximal element is the ``rightmost'' bracketing $1 (2 (\cdots (n-1 , n))\cdots )$.  We proceed up a  cover relation by changing some triple of  consecutive objects  (not necessarily single letters) of the form  $(a,b)c$ into a new triple $a (b,c)$.  This has the impact of moving  a single  right parenthesis (as well as a single left parenthesis)  farther to the right. 
  For our proposed $SB$-labeling,  we record at each step the letter to the immediate left of the unique 
 right parenthesis which  is moved to the right.  Thus, we label the cover relation changing $(a,b)c$ to $a(b,c)$ with the rightmost letter appearing in the expression $b$. 

 
Let us now confirm that this edge  labeling satisfies conditions (1), (2) and (3)  required for the index 2 formulation for  an  $SB$-labeling.  
By construction,  there will be at most one allowable way to move a particular right parenthesis to the right via a cover relation, yielding condition (1).
 To help us confirm (2) and (3), we first introduce a family of   operators $u_i$ for  $i \in \{ 2,3,\dots ,n-1 \} $.  Applying  to a binary bracketing with  $n$ letters the operator $u_i$ has the impact of  moving  the rightmost   
right parenthesis which is in between the  $i$-th and $(i+1)$-st letters  to the right and acts as needed on its left partner parenthesis; if 
there is no such right parenthesis in this $i$-th  position  in $v$ that may be moved to the right by a cover relation,  then $u_i(v)$  is formally set to $0$.   Thus, $v\prec w$ in the Tamari lattice if and only if there exists an operator $u_i$ with $u_i(v) = w$.

In the proof below, we will  confirm  the following things: 
\begin{enumerate}
\item
 for every element $v$ in the Tamari lattice and every $i<j$ we have  either $u_iu_j(v)=u_ju_i(v)$ or $u_iu_j(v)=u_ju_ju_i(v)$, 
 \item
 there are no other elements in the interval $[v,u_iu_j(v)]$ than the 4 or 5 elements involved in the aforementioned relation, and 
 \item
  that  $u_iu_i(v) = 0$ for each $v\in L$ and each  $2\le i < n$.  
  \end{enumerate}
      More specifically for (1), we will show that we  have the relation $u_iu_j(v) = u_ju_ju_i(v)$ for intervals which convert an expression $((a,b)c)d$ to $a(b(c,d))$ and instead we have the relation $u_iu_j(v) = u_ju_i(v)$ for all  other pairs of operators  $u_i,u_j$. 
Checking these things will yield  conditions (2) and (3) in the index 2 formulation for $SB$-labeling, hence will imply that our labeling is an $SB$-labeling.



Now we turn to  justifying the first claim enumerated above. 
First suppose that we are converting a bracketing containing the expression $((a,b)c)d$ to one instead containing $a(b(c,d))$.  When $a,b,c,d$ are single letters, one may check  directly  that we obtain the relation $u_iu_j(v) = u_ju_ju_i(v)$.  Next observe that the labeling was not sensitive to whether $a,b,c,d$ were single letters are more complex expressions themselves.
 Otherwise, the operators $u_i,u_j$ must commute since neither right parenthesis to be moved to the right has any impact on how the other is moved.  This includes the possibility of $u_i(v)=0$ or $u_j(v)=0$, since again the point is that the two operations do not impact each other. 
 Thus, we get $u_iu_j(v) = u_ju_i(v)$ in this case.
 
From the standpoint of  trees, each of our operations $u_i$,  will involve a pair of non-leaf nodes, one of which is the left child of the other; the operation will shift the right child of the lower non-leaf node to instead being a left child of a non-leaf node which is now a right child of the higher non-leaf node.  
The two operations given by $u_i$ and $u_j$ will commute unless the associated pairs of non-leaf nodes involved in the operations have at least one of these non-leaf nodes in common.  They cannot have both of these non-leaf nodes associated to them in common with each other or else the two operations  would by definition be the same operation.  The case where the two operations have one of these two non-leaf nodes in common is exactly the case which already yielded  the relation $u_iu_j(v) = u_ju_ju_i(v)$.  

  
    Now to the proof of the second claim above.  It follows from the definition of the Tamari lattice that there are no elements in the closed  interval 
$[v, u_i(v) \vee u_j(v)]$ other than the  4 or 5 elements directly   involved in this relation. 
The third claim above  also has a simple explanation: the relation  $u_iu_i(v)= 0 $ is immediate from the fact that  there is at most one allowable way to move a  right parenthesis which is  to the immediate right of the $i$-th letter farther to the  right in a binary expression to obtain a new binary expression.
\end{proof}

\begin{ex}
Neither the dominance order on the partitions of an integer $n$ nor its dual poset admits an $SB$-labeling in general.  This can be seen by considering the interval downward from the partition $(5,4,3,2,1)$ to the meet of the 4 elements its covers.  This example also rules out  the  more general class of $I$-lattices studied by Greene in \cite{Gr}.  

 Recall that the dominance order was proven to be non-pure shellable with  each open interval homotopy equivalent to a  ball or a sphere  in \cite{BW}.  The M\"obius function was  determined prior to that in \cite{Bogart}, \cite{Brylawski} and \cite{Gr}.  
\end{ex}



It would be interesting to know of additional examples of finite (or locally finite)  lattices with $SB$-labelings.  We have not made a comprehensive search for such examples, but rather have chosen to focus in this paper on some well-known  families of lattices with the appropriate M\"obius function  that seemed  to us to be especially interesting classes of posets.


\section*{Acknowledgments}

The authors  are  grateful to Georgia Benkart, Stephanie van Willigenburg,  Monica Vazirani, and  the Banff International Research Station (BIRS) for conducting an inspiring  workshop entitled
Algebraic Combinatorixx  in May 2011 for female researchers in algebraic combinatorics with the goal of helping  establish new and fruitful collaborations.   This project grew out of discussions that began at that workshop.
 The authors also thank  Louis Billera, Anders Bj\"orner, Curtis Greene,  Thomas McConville,
  Peter McNamara,  and  Vic Reiner
 for helpful discussions and references.




2014-07-22T02:08:53.000
1407
1407.5311
en
https://arxiv.org/abs/1407.5311
We introduce a new class of poset edge labelings for locally finite lattices which we call $SB$-labelings. We prove for finite lattices which admit an $SB$-labeling that each open interval has the homotopy type of a ball or of a sphere of some dimension. Natural examples include the weak order, the Tamari lattice, and the finite distributive lattices.
Combinatorics (math.CO); Algebraic Topology (math.AT)
SB-labelings and posets with each interval homotopy equivalent to a sphere or a ball
Qwen/Qwen-72B
1. YES
2. YES