% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.16}{25(4)}{2018}

\usepackage{algorithmic}
\usepackage{pgf,tikz}
\usepackage{mathrsfs}
\usetikzlibrary{arrows}


\newcommand{\Flip}{\textsc{Flip}}
\newcommand{\cpsi}{\widetilde{\psi}}

\newcommand{\dd}{\textbf{d}}
\newcommand{\cc}{\textbf{c}}
\newcommand{\cd}{\textbf{cd}}
\newcommand{\aaa}{\textbf{a}}
\newcommand{\bbb}{\textbf{b}}
\newcommand{\Nil}{\mbox{Nil}}
\newcommand{\id}{\mbox{Id}}
\newcommand{\flip}{\textsc{Flip}}

  
\usepackage{tikz}
\usetikzlibrary{automata,positioning}

\usepackage[linesnumbered,ruled]{algorithm2e}
\makeatletter
\newcommand{\RemoveAlgoNumber}{\renewcommand{\fnum@algocf}{\AlCapSty{\AlCapFnt\algorithmcfname}}}
\newcommand{\RevertAlgoNumber}{\algocf@resetfnum}
\makeatother

% Please remove all commands that change parameters such as
%    margins or page sizes.

% Packages amssymb and amsthm are already loaded. 
% We recommend these AMS packages:
\usepackage{amsmath,amssymb}
% We recommend the graphicx package for importing figures:
\usepackage{graphicx}
% Use this command to create hyperlinks (optional and recommended):
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% Theorem-like environments that are declared in the style file are:
% theorem, lemma, corollary, proposition, fact, observation, claim,
% definition, example, conjecture, open, problem, question, remark, note

%%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Give the submission and acceptance dates in the format shown.
% The editors will insert the publication date in the third argument.
\dateline{Jun 5, 2018}{Sep 13, 2018}{Oct 19, 2018}

% Give one or more subject codes separated by commas.
% Codes are available from http://www.ams.org/mathscinet/freeTools.html
\MSC{20F55, 05E99 , 05E15}

% Uncomment exactly one of the following copyright statements.  Alternatively,
% you can write your own copyright statement subject to the approval of the journal.
% See https://creativecommons.org/licenses/ for a full explanation of the 
% Creative Commons licenses.
%
% We strongly recommend CC BY-ND or CC BY. Both these licenses allow others
% to freely distribute your work while giving credit to you. The difference between
% them is that CC BY-ND only allows distribution unchanged and in whole, while
% CC BY also allows remixing, tweaking and building upon your work.  
%
%    One author:
%\Copyright{The author.}
%\Copyright{The author. Released under the CC BY license (International 4.0).}
%\Copyright{The author. Released under the CC BY-ND license (International 4.0).}
%    More than one author:
%\Copyright{The authors.}
%\Copyright{The authors. Released under the CC BY license (International 4.0).}
\Copyright{  The author. Released under the CC BY-ND license (International 4.0).}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% If needed, include a line break (\\) at an appropriate place in the title.
\title{Flip posets of Bruhat intervals}

% Input author, affiliation, address and support information as follows;
% The address should include the country, but does not have to include
%    the street address. Give at least one email address.

\author{Sa\'ul A. Blanco\thanks{Supported by NSF grant DMS-0555268.}\\
\small Department of Computer Science\\[-0.8ex]
\small Indiana University\\[-0.8ex] 
\small Bloomington, IN 47408, U.S.A.\\
\small\tt sblancor@indiana.edu
}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract may be distributed without the rest of the
% paper so it must be entirely self-contained.  Try to include all words
% and phrases that someone might search for when looking for your paper.

\begin{abstract}
  In this paper we introduce a way of partitioning the paths of shortest lengths in the Bruhat graph $B(u,v)$ of a Bruhat interval $[u,v]$ into rank posets $P_{i}$ in a way that each $P_{i}$ has a unique maximal chain that is rising under a reflection order. In the case where each $P_{i}$ has rank three, the construction yields a combinatorial description of some terms of the complete $\textbf{cd}$-index as a sum of ordinary $\textbf{cd}$-indices of Eulerian posets obtained from each of the $P_{i}$.
\end{abstract}

\section{Introduction} 

Given a Coxeter group $W$ with $u,v\in W$, the Bruhat graph associated with a Bruhat interval $[u,v]$ has $u$-$v$ paths of several lengths (see~\cite{D91}). The $u$-$v$ paths of maximum length correspond to maximal chains of $[u,v]$. Dyer~\cite{D93} defined and proved the existence of a set of total orders on the set of reflections of $W$, called reflection orders, which were used to prove algebraic and topological properties of $[u,v]$. For instance, $[u,v]$ is Eulerian and Cohen-Macaulay, which was also proved by Bj\"orner and Wachs~\cite{BW82} by using a different labeling. One of the advantages of Dyer's reflection orders is that they can be used to label all the paths in the Bruhat graph of $[u,v]$, and not just those of longest length. However, whenever Bj\"orner and Wachs's labeling is defined on \emph{all} paths of a certain length (maximal or not), it has the same descent-set distribution as the any reflection order (see~\cite[Theorem 2.11]{B11}). Utilizing reflection orders, Billera and Brenti~\cite{BiBr11} defined a polynomial in the noncommutative variables $\cc$ and $\dd$, called the complete $\cd$-index, that encodes the descent-set distribution of any reflection order on the $u$-$v$ paths. The complete $\cd$-index can be used to express the Kazhdan-Lusztig polynomials and it extends the notion of the $\cd$-index of $[u,v]$ seen as an Eulerian poset. The coefficients of the complete $\cd$-index have been conjectured to be nonnegative, and this has been proven in some cases (see~\cite{B11, B13, FH15,K13}). In this paper we propose an algorithm that separates the $u$-$v$ paths in the Bruhat graph of $[u,v]$. In the special case of the shortest-length $u$-$v$ paths, this algorithm yields posets in which every subinterval has at most one rising chain (under any reflection order). Furthermore, when applied to the $u$-$v$ paths of length two and three, the corresponding terms of the complete $\cd$-index can be obtained as the sum of the $\cd$-index of certain Eulerian posets determined by the algorithm. So not only do we have an alternative proof of the nonnegativity of these terms, but we prove that they arise from a natural decomposition of posets. 

The basic definitions are presented in Section~\ref{sec:basicdefns}. The remaining of the paper is organized as follows. The \flip\;algorithm and some of its properties are presented in Section~\ref{sec:flipalgorithm}. In Section~\ref{sec:flipSP}, we apply the \flip\;algorithm to the maximal chains of the shortest path poset $SP(u,v)$ of $[u,v]$ to obtain certain subposets, which we call flip posets, and show that they satisfy properties similar to $SP(u,v)$.  In Section~\ref{sec:B3} we study the special case of applying the \flip\;algorithm to $B_{2}(u,v)$ and $B_3(u,v)$, the paths of length two and three, respectively, in the Bruhat graph of $[u,v]$. We furthermore show that certain terms of the complete $\cd$-index, those corresponding to $u$-$v$ paths of length two or three,  can be expressed as a sum of the $\cd$-index of certain Eulerian posets that are obtained from the \flip\;algorithm, enabling us to conclude nonnegativity in these cases, as well as a connection between the two indices. 

\section{Basic definitions}\label{sec:basicdefns}
We follow~\cite[Section 5.1]{H90} and let $(W,S)$ denote an arbitrary Coxeter system. Namely, 
\[
W=\langle S\mid (s,s')^{m(s,s')=e}\rangle,
\] where $e$ is the identity element of $W$, and for all $s,s'\in S$, $m(s,s)=1$, and $m(s,s')=m(s',s)\in\mathbb{Z}^+\cup\{\infty\}$ if $s\neq s'$. We let $T:=\{wsw^{-1}\mid s\in S,w\in W\}$ be the corresponding set of \emph{reflections}. Dyer~\cite{D91} defined the \emph{Bruhat graph} of $(W,S)$ as the directed graph with vertex set $W$, and given $u,v\in W$, there is a directed edge between $u$ and $v$ if and only if $v=ut$ for some $t\in T$. If $w=s_1s_2\ldots s_k$ with $s_i\in S$ for $1\leq i\leq k$ and $k$ is minimal, then we say that the \textit{length} of $w$ is $k$ and write $\ell(w)=k$. Given two elements $u,v\in W$, we say that $u\leq v$ if and only if there exists a $u$-$v$ path from $u$ to $v$ in the Bruhat graph of $(W,S)$. The order $\leq$ is called the \emph{Bruhat order}. Given $T'\subseteq T$, we denote by $W'$ be the subgroup of $W$ generated by $T'$. $W'$ is called a \textit{reflection subgroup} of $W$. Following~\cite[Section 8.2]{H90}, we let $N(w):=\{t\in T\mid \ell(wt)<\ell(w)\}$ and $S':=\{t \in T : N(t) \cap W = \{t\}\}$. In this case, $(W',S')$ is a Coxeter system, and if $|S'|=2$ we say that $(W',S')$ is a \emph{dihedral reflection subgroup}. Dyer~\cite{D93} proved the existence of linear orders on the set $T$, called \textit{reflection orders}. The total order $<_T$ is a reflection order if for any dihedral reflection subgroup $(W',\{t_1,t_2\})$, either $t_1 <_T t_1t_2t_1 <_T t_1t_2t_1t_2t_1 <_T \cdots <_T t_2t_1t_2t_1t_2 <_T t_2t_1t_2 <_T t_2$ or $t_2 <_T t_2t_1t_2 <_T t_2t_1t_2t_1t_2 <_T \cdots <_T t_1t_2t_1t_2t_1 <_T t_1t_2t_1 <_T t_1$.  In the case $W=A_{n-1}$, the symmetric group generated by the $n-1$ adjacent transpositions $(1\;\;2),(2\;\;3),\ldots,(n-1\;\;n)$, it is well-known that the lexicographic order on \emph{all} transpositions form a reflection order, and we use this order in our examples. To be more specific, $(1\;\;2)<_{T}(1\;\;3)<_{T}(1\;\;4)<_{T}\cdots<_{T}(n-1\;\;n)$ is a reflection order, and it is customary to refer to these reflections in the order in which they appear. So $(1\;\;2)$ is labeled with a ``1,'' $(1\;\;3)$ is labeled with a ``2,'' and so forth. Any reflection order produces an \emph{EL-labeling} of a Bruhat interval $[u,v]$ (see~\cite[Section 4]{D93}) and this EL-labeling was used to prove topological properties such as $[u,v]$ being \emph{Cohen-Macaulay}, which was also proved by Bj\"orner and Wachs~\cite{BW82}.

The maximal-length $u$-$v$ paths form the maximal chains in the Bruhat interval $[u,v]$. Furthermore, the set of $u$-$v$ paths $(u_{0}=u<u_{1}<u_{2}<\cdots< u_{k}=v)$ of length $k$  is denoted by $B_{k}(u,v)$. Sometimes we will denote a path $(u_{0}=u<u_{1}<u_{2}<\cdots< u_{k}=v)\in B_{k}(u,v)$ by the $k$-tuple $(\lambda(u_{0},u_{1}),\lambda(u_{1},u_{2}),\ldots,\lambda(u_{k-1},u_{k}))$ where $\lambda(u_{i-1},u_{i})\in T$ is the unique reflection such that $u_{i}=u_{i-1}\lambda(u_{i-1},u_{i})$. So sometimes we refer to a $u$-$v$ path in terms of the vertices that are in the path, and sometimes we refer to it in terms of the edges, which are labeled by reflections. Furthermore, we denote by $B(u,v)$ the set of all $u$-$v$ paths; that is, $B(u,v)=\cup_{k}B_{k}(u,v).$

To every path $\Delta=(\lambda(u_{0},u_{1}),\lambda(u_{1},u_{2}),\ldots,\lambda(u_{k-1},u_{k}))\in B_k(u,v)$ we can associate a monomial $w(\Delta):=x_{1}x_{2}\ldots x_{k-1}$ on the variables $\aaa$ and $\bbb$ as follows:
\[
x_{i}:=\begin{cases}
\aaa&\text{ if $\lambda(u_{i-1},u_{i})<_{T}\lambda(u_{i},u_{i+1})$}\\
\bbb&\text{ if $\lambda(u_{i},u_{i+1})<_{T}\lambda(u_{i-1},u_{i})$}
\end{cases}
\]


The \emph{complete \textbf{ab}-index} is the polynomial $\sum_{\Delta\in B(u,v)}w(\Delta)$ in the noncommutative variables $\aaa$ and $\bbb$. Billera and Brenti~\cite{BiBr11} showed that the complete $\aaa\bbb$-index can be expressed as a polynomial $\widetilde{\psi}_{u,v}(\cc,\dd)$ in the noncommutative variables $\cc$ and $\dd$, where $\cc=\aaa+\bbb$ and $\dd=\aaa\bbb+\bbb\aaa$. The polynomial $\widetilde{\psi}_{u,v}(\cc,\dd)$ is called the \emph{complete $\cc\dd$-index} of $[u,v]$, where $[u,v]$ denotes the Bruhat interval $\{x\in W\mid u\leq x\leq v\}$. Furthermore, it was shown in~\cite[Proposition 2.5]{BiBr11} that the highest-degree terms of $\widetilde{\psi}_{u,v}(\cc,\dd)$ correspond to the $\cc\dd$-index of $[u,v]$ seen as an Eulerian poset, which was studied by Reading in~\cite{R04}. The $\cd$-index was first defined in~\cite{BK91} as a way of encoding the linear relations on flag vectors of polytopes. Let $P$ be a finite graded poset of rank $d+1$ with partial order $\preceq$, rank function $r$ and smallest and largest elements $\hat{0}$ and $\hat{1}$, respectively. For any $S=\{s_{1},\ldots,s_{k}\}\subseteq[d]$, with $s_{1}<\cdots<s_{k}$, define
\[
f_{S}(P):=|\{\hat0\prec x_{0}\prec x_{1}\prec\cdots \prec x_{k+1}=\hat1:r(x_{i})=s_{i}\}|,
\]

where $\hat0\prec x_{0}\prec x_{1}\prec\cdots \prec x_{k+1}=\hat1$ denotes a maximal chain of $P$.

The vector $(f_{S}(P))_{S\subseteq[d]}$ is called the \emph{flag $f$-vector} of $P$.  A closely related object, and sometimes more useful, is the \emph{flag h-vector}. Each of the components of the flag $h$-vector is defined from the flag $f$-vector as follows. 
\begin{equation*}
h_{S}=\sum_{T\subseteq S}(-1)^{|S\setminus T|}f_{T}.
\end{equation*}

Furthermore, let $\aaa$ and $\bbb$ be non-commutative variables. For $S\subseteq[d]$, let $w(S)=x_{1}x_{2}\cdots x_{d}$, where
\[
x_{i}=
\begin{cases}
\aaa &\text{ if $i\not\in S$}\\
\bbb &\text{ if $i\in S$}.
\end{cases}
\]

The polynomial $\sum_{S\subseteq[d]}h_{S}w(S)$
is called the $\aaa\bbb$-index of $P$. Bayer and Klapper~\cite{BK91} proved that, when $P$ is Eulerian,  the $\aaa\bbb$-index can be rewritten as a homogeneous polynomial in the noncommutative variables $\cc$ and $\dd$, where $\cc=\aaa+\bbb$ and $\dd=\aaa\bbb+\bbb\aaa$. This polynomial is called the \emph{\textbf{cd}-index} of $P$, and we denote it by $\psi(P)$.

Given $\Delta=(t_{1},t_{2},\ldots,t_{k})\in B_{k}(u,v)$, we define the \emph{descent set} $D(\Delta)$ of $\Delta$ as 
\[
D(\Delta):=\{i\in[k-1]: t_{i+1}<_{T}t_{i}\}.
\]

Notice that the complete $\cc\dd$-index provides a way of encoding the distribution of the descent sets of all paths in $B(u,v)$. If a given path $\Gamma\in B(u,v)$ has empty descent set, that is,  $D(\Gamma)=\varnothing$, then $\Gamma$ is said to be a \emph{rising path}. Similarly, if a path $\Gamma\in B_k(u,v)$ has descent set $D(\Gamma)=[k-1]$, then $\Gamma$ is called a \emph{falling path}. It is known that the coefficient of $\cc^{m}$ in $\widetilde{\psi}_{u,v}(\cc,\dd)$ gives the number of rising (and falling) paths in $B_{m+1}(u,v)$ for $0\leq m\leq \ell(v)-\ell(u)-1$ (see~\cite[Corollary 2.10]{BiBr11}). We denote the coefficient of $\cc^{m}$ in $\widetilde{\psi}_{u,v}(\cc,\dd)$ by $[\cc^{m}]_{u,v}$.

The \emph{shortest path poset} of $[u,v]$ was defined in~\cite{B13}. To construct it, one takes the subgraph of $B(u,v)$ formed by the minimal-length $u$-$v$ paths, and considers this to be the Hasse diagram of a poset, denoted by $SP(u,v)$. The lowest-degree terms of  $\widetilde{\psi}_{u,v}(\cc,\dd)$ correspond to the shortest $u$-$v$ paths of $B(u,v)$. When $SP(u,v)$ has only one rising chain, $SP(u,v)$ is a \emph{Gorenstein* poset}; that is, $SP(u,v)$ is Eulerian and Cohen Macaulay (see~\cite[Theorem 5]{B13}). Moreover, under the assumption that $SP(u,v)$ has only one rising chain, $SP(u,v)$ is an EL-labelable poset (the reflection order is an EL-labeling) and therefore the coefficients of the $\widetilde{\psi}_{u,v}(\cc,\dd)$ corresponding to the maximal chains in $SP(u,v)$ coincide with $\psi(SP(u,v))$ (see~\cite[Theorem 2.2]{BGS82}) and are  nonnegative (see~\cite{K06}).

\section{Flip algorithm}\label{sec:flipalgorithm}
In this section we propose an algorithm to divide the elements of $B_k(u,v)$ into a graph with $[\cc^{k-1}]_{u,v}$ components so that each component has exactly one $u$-$v$ path that is rising under $<_T$.

Following~\cite[Section 6]{BiBr11} we now define the \emph{flip} of $\Gamma\in B_2(u,v)$ and we use $\leq_{lex}$ to denote the lexicographic order. Let $(t_1,t_2)$ and $(r_1,r_2)$ be in $B_2(u,v)$. We say that $(t_1,t_2)\leq_{lex}(r_1,r_2)$ if and only if $t_1<_Tr_1$, or if $t_1=r_1$ and $t_2\leq_Tr_2$. The existence of the complete $\cd$-index implies that there are as many paths with empty descent set in $B_2(u,v)$ as those with descent set $\{1\}$. Order all the paths in $B_2(u,v)$ lexicographically and let 
\[r(\Gamma):=|\{\Delta\in B_2(u,v)\mid D(\Delta)=D(\Gamma), \Delta\leq_{lex}\Gamma\}|.\] 
The \emph{flip} of $\Gamma$ is the $r(\Gamma)$-th Bruhat path in $\{\Delta\in B_2(u,v)\mid D(\Delta)\neq D(\Gamma)\}$ ordered by $\leq_{lex}$, and we denote the \emph{flip} of a path $\Gamma$ by $\textit{flip}(\Gamma)$.

The following proposition was proved in~\cite[Proposition 6.2]{BiBr11} for affine and finite Coxeter groups, and then proved to hold for general Coxeter groups in~\cite[Proposition 3.8]{B11}. The proof of the general case also follows as a consequence of Dyer's proof of Cellini's conjecture~\cite{D12}.

\begin{proposition}\label{prop:6_2}
Let $W$ be a Coxeter group, and let $u,v\in W$, $u<v$, $(u<y<v)\in B_2(u,v)$ be such that $D((u<y<v))=\varnothing$ and $(u<x<v):=\textit{flip}((u<y<v))$. Then $u^{-1}y<_Tu^{-1}x$ and $x^{-1}v<_Ty^{-1}v$ for any reflection order $<_T$.
\end{proposition}

In fact, it turns out that the lexicographically first element in $B_k(u,v)$ is rising. 

\begin{proposition}[Proposition 3.9,~\cite{B11}]\label{prop:lexfirstrises} Let $\Delta$ be the lexicographically-first path in $B_k(u, v)$. Then $D(\Delta) = \varnothing$, i.e., $\Delta$ is rising.
\end{proposition}

We now define the operation $\Flip_{i}$. In a few words, given a path 
\[\Delta=(u=x_{0}<x_{1}<\cdots<x_{k}=v)\in B_{k}(u,v), \] we construct a path $\Delta'$ by taking $(x_{i-1}<x_{i}<x_{i+1})\in B_2(x_i,x_{i+1})$ and replacing this part of $\Delta$ by its flip, $flip((x_{i-1}<x_{i}<x_{i+1}))$. If $i\in D(\Delta)$ then $i\not\in D(\Delta')$ and vice-versa. The pseudocode is given in Algorithm~\ref{alg:Flipi} below.

\begin{algorithm}

	\caption{$\textsc{Flip}_{i}(\Delta)$ flips a path $\Delta\in B_{k}(u,v)$ at position $i$.} 
	 \label{alg:Flipi}
\SetKwInOut{Input}{Input}
    \Input{$\Delta=(u=x_{0}<x_{1}<\cdots<x_{k}=v)\in B_{k}(u,v)$ and $i\in[k-1]$}

\begin{algorithmic}[1]
     \STATE $(x_{i-1}<x'_{i}<x_{i+1}):=flip((x_{i-1}<x_{i}<x_{i+1}))$ 
     
     \STATE $\Delta':=(x_{0}<x_{1}<\cdots<x_{i-1}<x'_{i}<x_{i+1}<\cdots<x_{k})$
     
    \RETURN $\Delta'$
     \end{algorithmic}
\end{algorithm}
    
For the remainder of the paper, it will be convenient for us to refer to the elements in $B_k(u,v)$ by utilizing the labels of their edges instead of listing the vertices in the path. 

We use $\flip_{i}$ to define $\flip$. \textsc{Flip}$(\Delta)$ transforms $\Delta$, with $D(\Delta)\neq\varnothing$, to a path such that $D(\Flip(\Delta))=D(\Delta)\setminus \{\min(D(\Delta))\}$, where $\min(D(\Delta))$ denotes the smallest element in $D(\Delta)$. In other words, $\flip$ transforms a path $\Delta$ to one that removes the first descent, from bottom to top, of $\Delta$. The pseudocode is written in Algorithm~\ref{alg:FlipDelta}.

\begin{algorithm}[h]
\caption{$\Flip(\Delta)$, where $\Delta\in B_{k}(u,v)$}
\SetKwInOut{Input}{Input}
\Input{A path $\Delta\in B_{k}(u,v)$}
\begin{algorithmic}[1]
\STATE $\Flip(\Delta):=\Delta$
	\IF{$D(\Delta)\neq\varnothing$} 
		\STATE $i:=\min(D(\Delta))$ 
		\STATE $\Flip(\Delta):=\textsc{Flip}_{i}(\Delta)$ 				
	\ENDIF
\RETURN $\Flip(\Delta)$
\end{algorithmic}
\label{alg:FlipDelta}
\end{algorithm}

We write  $\Flip^j(\Delta)$, with $j\geq 1$, to denote the path obtained after applying $\flip$ $j$ times; that is, $\flip^{j}(\Delta):=\underbrace{\Flip\circ\cdots\circ\Flip}_j(\Delta)$.

The  $\Flip$ algorithm constructs a directed graph $FG(u,v;k)$ with vertex set, $B_k(u,v)$ and the $\flip$ operator is used to determine the edges. To each path $\Delta\in B_{k}(u,v)$ with nonempty descent, we shall assign a unique path $\flip(\Delta)\in B_{k}(u,v)$ obtained by flipping $\Delta$ at its first descent, from bottom to top, and then we add a directed edge from $\Delta$ to $\flip(\Delta)$. The pseudocode is given in Algorithm~\ref{alg:flipgraph}. 
\\
%\RemoveAlgoNumber
\begin{algorithm}[h!]
\SetKwInOut{Input}{Input}
	\caption{\textbf{$\Flip$ algorithm }$\textsc{Flip}(B_{k}(u,v))$: Determine the \textsc{Flip}-graph of $B_{k}(u,v)$} 
		\Input{$B_{k}(u,v)$, each element labeled by reflections}
	\begin{algorithmic}[1]
	\STATE $E:=\varnothing$
	\STATE $FG(u,v;k):=(B_{k}(u,v),E)$
		\FOR{$\Delta\in B_{k}(u,v)$} 
			\IF{$D(\Delta)\neq\varnothing$}
	%		\STATE $i:=\min D(\Delta)$ 
			 \STATE Add (the directed) edge $(\Delta,\Flip(\Delta))$ to $E$. 
			 \ENDIF
		\ENDFOR 
		\RETURN{$FG(u,v;k)$}. 
	\end{algorithmic}
	\label{alg:flipgraph}
\end{algorithm}

There are two straightforward properties that the \flip\;algorithm satisfies: it terminates and it creates a graph with $[\cc^{k-1}]_{u,v}$ components. We prove these properties in the following lemma.

\begin{lemma} The $\Flip$ algorithm satisfies the following properties. 
\begin{enumerate} 
    \item[(i)] The \textsc{Flip} algorithm terminates.
	\item[(ii)] $FG(u,v;k)$ has $[\cc^{k-1}]_{u,v}$ connected components, each one of which is an anti-arborescence. That is, every connected component has a unique vertex $v$ with zero out-degree and every vertex in the component has a unique path to $v$.
\end{enumerate}
\end{lemma}

\begin{proof}
\begin{enumerate}
\item[(i)] Notice that if $i\in D(\Delta)$, $\textsc{Flip}_{i}(\Delta)$ is earlier in the lexicographic order than $\Delta$ by Proposition~\ref{prop:6_2}, and since the lexicographically-first path in $B_k(u,v)$ is rising by Proposition~\ref{prop:lexfirstrises}, the \textsc{Flip} algorithm must terminate.
\item[(ii)] Every path, seen as a vertex in the flip graph $FG(u,v;k)$ is associated with a unique rising path obtained by iterating $\Flip$ until a rising path is reached. Moreover, a vertex representing a rising path has in-degree zero, and is therefore a sink. Hence every rising path must be in a different component, and there are $[\cc^{k-1}]_{u,v}$ of them since there are $[\cc^{k-1}]_{u,v}$ rising paths. Now, if there were two paths between a path $\Delta$ and the rising path associated with it through repeatedly applying \flip, then that would imply that the out-degree of $\Delta$ is at least two, but this is not possible since the only edge having $\Delta$ as a tail is $(\Delta,\flip(\Delta))$. Therefore, there is a unique path between any vertex in the component and the corresponding rising path. \qedhere
\end{enumerate}
 \end{proof}

The following corollary is an easy consequence of the \flip\;algorithm terminating. 

\begin{corollary}
	For every $\Delta\in B_k(u,v)$, there is nonnegative integer $i_{k,\Delta}$ so that 
	\begin{enumerate}
	    \item[(i)] $\Flip^{i_{k,\Delta}}(\Delta)=\Flip^{i_{k,\Delta}+1}(\Delta)$,
	    \item[(ii)] $\Flip^{i_{k,\Delta}}(\Delta)$ is rising, and
	    \item[(iii)] The time and space complexity of the \flip\;algorithm is $\Omega(|B_{k}(u,v)|)$.
	\end{enumerate}
\end{corollary}

\begin{definition}Let $x\in [u,v]$, and let 
$c=(u=w_{0}<w_{1}<\cdots<w_{p}=x)\in B_{p}(u,x)$ and $d=(x=y_{0}<y_{1}<\cdots<y_{q}=v)\in B_{q}(x,v)$ with $0\leq p,q<k$. Then consider the following definitions.
\begin{enumerate}
\item[(i)] Define $FG_{c}(u,v;k)$ to be the induced subgraph of $FG(u,v;k)$ with vertex set
\begin{align*}
V_{c}(u,v;k):=\{(u=x_{0}<x_{1}<\cdots<x_{k}=v): (x_{0}=x<\cdots<x_{p}=x)=c \}.%B_{k-p}(x,v)\}.
\end{align*} 
\item[(ii)] Similarly, define $FG^{d}(u,v;k)$ to be the induced subgraph of $FG(u,v;k)$ with vertex set 
\begin{align*}
V^{d}(u,v;k):=\{(u=x_{0}<x_{1}<\cdots<x_{k}=v):
 (x_{k-q}=x<\cdots<x_{k}=v)=d\}.
\end{align*}
\end{enumerate}
\end{definition}

In other words, $V_{c}(u,v;k)$ denotes the set of all elements in $V(FG(u,v;k))$, the vertex set of $FG(u,v;k)$, that ``start'' with $c$ and $V^{d}(u,v;k)$ denotes the set of all elements in $V(FG(u,v;k))$ that ``end'' with $d$. 

With this definition, we have the following proposition, which we call the \textbf{Subgraph Property}.

\begin{proposition}[Subgraph Property]\label{prop:subgraph}
Let $x\in[u,v]$, and let $c=(u=w_{0}<\cdots<w_{p}=x)\in B_{p}(u,x)$ and $d=(x=y_{0}<\cdots<y_{q}=v)\in B_{q}(x,v)$ with $0\leq p,q<k$. Then
\begin{enumerate}
    \item[(i)] $FG^{d}(u,v;k)\cong FG(u,x;k-q)$ as graphs, and
    \item[(ii)] $FG_{c}(u,v;k)$ is isomorphic to a subgraph of $FG(x,v;k-p)$.  
\end{enumerate}
\end{proposition}

In the proof of the Subgraph Property, if $\Delta\in B_{k}(u,x)$ and $\Gamma\in B_{\ell}(x,v)$, where $x\in [u,v]$,  we denote the \emph{concatenation} of $\Delta$ and $\Gamma$ by $\Delta\Gamma\in B_{k+\ell}(u,v)$.
 	
\begin{proof}
\begin{enumerate}
    \item[(i)] Let $(D_{1},D_{2})$ be an edge of $FG^{d}(u,v;k)$. We show that there exists an edge $(d_{1},d_{2})$ in $FG(u,x;k-q)$, where $d_{1},d_{2}\in B_{k-q}(u,x)$ are so that $d_{1}d=D_{1}$ and $d_{2}d=D_{2}$. By definition of the flip graph, we have that $D_{2}=\Flip(D_{1})$, so $D_{1}$ has a nonempty descent set. If $\min (D(D_{1}))\geq k-q$, then $D_{2}$ would not end with $d$ and therefore $D_{2}\not\in V(FG^{d}(u,v;k))$, which contradicts the choice of $D_{2}$. Hence $\min (D(D_{1}))<k-p$, and so $\min (D(D_{1}))=\min (D(d_{1}))$, and therefore there exists $d_{2}$ with $\flip(D_{1})=d_{2}d$ and $\flip(d_{1})=d_{2}$.

Conversely, suppose that $(d_{1},d_{2})$ is an edge of $FG(u,x;k-q)$ then $(d_{1}d,d_{2}d)$ must be an edge of $FG^{d}(u,v;k)$, as the first descent from bottom to top of $d_1d$ occurs in $d_{1}$.
\item[(ii)] It is enough to show that if $(cc_{1},cc_{2})$ is and edge in $FG_{c}(u,v;k)$, then $(c_{1},c_{2})$ is also an edge of $FG(x,v;k-p)$. By definition of the flip graph,  $cc_{2}=\Flip(cc_{1})$. Then the first descent from bottom to top of $cc_{1}$ occurs after $c$, as otherwise  $cc_{2}\not\in V_{c}(u,v;k)$. Thus, $c_{2}=\Flip(c_{1})$, and the result follows.\qedhere
\end{enumerate}
\end{proof}

\begin{remark}\label{rem:noiso}
We point out that it is not true that $FG(x,v;k-p)$ is isomorphic to a subgraph of $FG_{c}(x,v;k)$. For example, in $A_{4}$, if $c=(12345<32145<35142)$, or $c=(2,7)$ if labeled by reflections, then $FG(35142,54312;3)$ is not isomorphic to $FG_{c}(12345,54312;5)$. In fact,  the vertex set $$V(FG(35142,54312;3))=\{(1, 6, 8), (1, 8, 5), (3, 1, 8), (3, 8, 1), (8, 1, 5), (8, 2, 1)\},$$ where the elements have been denoted using reflections. Meanwhile, 
$$V(FG_{c}(12345,54312;5))=\{(2, 7, 3, 1, 8), (2, 7, 3, 8, 1), (2, 7, 8, 2, 1)\}.$$ 
\end{remark}


We now focus our attention on the case $B_{\ell_{s(u,v)}}(u,v)$, where $\ell_s(u,v)$ denotes the length of the shortest $u$-$v$ path in $B(u,v)$. In this case the \flip\;algorithm gives a way of partitioning the shortest path poset $SP(u,v)$ into subposets $P_{1},\ldots,P_{k}$ so that every subinterval of each $P_{i}$ has at most one rising chain. 

\section{$\Flip(SP(u,v))$}\label{sec:flipSP}

In this section we study the \flip\;algorithm when applied to the shortest $u$-$v$ paths of $B(u,v)$. Let us denote the number of rising maximal chains in $SP(u,v)$ by $r(u,v)$; that is, $r(u,v):=[\cc^{\ell_{s}(u,v)-1}]_{u,v}$. 

\begin{definition}[Flip posets] Let $FG(u,v):=FG(u,v;\ell_{s}(u,v))$, and $G_1,\ldots,G_{r(u,v)}$ be the connected components of the flip graph $FG(u,v)$. For each $G_i$ one can form a poset $P_i$ whose maximal chains are the vertices of $G_i$. That is, the maximal chains of $P_{i}$ are the elements in the set $\{C\mid C\in V(G_{i})\}$.  We call the posets $P_{1},\ldots,$ and $P_{r(u,v)}$ the \emph{flip posets} of $[u,v]$.
\end{definition}

To illustrate the $\Flip$ algorithm, consider the following example.

\begin{example}\label{ex:one}
Consider the 10 elements of $B_{3}(1234,4312)$. Then the output of the $\Flip$ algorithm is shown in Figure~\ref{fig:flipoutput}. In the first column we have the two components $G_{1}$ and $G_{2}$ of the flip graph $FG(1234,4312)$, and in the right column the corresponding flip posets $P_{1}$ and $P_{2}$. The paths of $B_{3}(1234,4312)$ are labeled by reflections, and the same is done to label the edges of the posets. 
\end{example}

\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=.8,line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(-6.5,-3) rectangle (18.,14.);
\draw [line width=1.2pt] (8.,-2.)-- (6.,0.);
\draw [line width=1.2pt] (8.,-2.)-- (8.,0.);
\draw [line width=1.2pt] (8.,-2.)-- (10.,0.);
\draw [line width=1.2pt] (6.,0.)-- (7.,2.);
\draw [line width=1.2pt] (6.,0.)-- (9.,2.);
\draw [line width=1.2pt] (10.,0.)-- (7.,2.);
\draw [line width=1.2pt] (8.,0.)-- (9.,2.);
\draw [line width=1.2pt] (7.,2.)-- (8.,4.);
\draw [line width=1.2pt] (8.,4.)-- (9.,2.);
\draw [line width=1.2pt] (8.,6.)-- (5.,8.);
\draw [line width=1.2pt] (8.,6.)-- (6.5,8.);
\draw [line width=1.2pt] (8.,6.)-- (9.5,8.);
\draw [line width=1.2pt] (8.,6.)-- (11.,8.);
\draw [line width=1.2pt] (5.,8.)-- (6.,10.);
\draw [line width=1.2pt] (5.,8.)-- (8.,10.);
\draw [line width=1.2pt] (8.,10.)-- (6.5,8.);
\draw [line width=1.2pt] (10.,10.)-- (6.5,8.);
\draw [line width=1.2pt] (6.,10.)-- (9.5,8.);
\draw [line width=1.2pt] (10.,10.)-- (11.,8.);
\draw [line width=1.2pt] (6.,10.)-- (8.,12.);
\draw [line width=1.2pt] (8.,10.)-- (8.,12.);
\draw [line width=1.2pt] (8.,12.)-- (10.,10.);
\draw [->,line width=1.2pt] (2.,10.) -- (0.,10.);
\draw [->,line width=1.2pt] (0.,10.) -- (-2.,10.);
\draw [->,line width=1.2pt] (-2.,10.) -- (-4.,10.);
\draw [->,line width=1.2pt] (-4.,10.) -- (-6.,10.);
\draw [->,line width=1.2pt] (-6.,8.) -- (-6.,10.);
\draw [->,line width=1.2pt] (-4.,0.) -- (-4.,2.);
\draw [->,line width=1.2pt] (0.,2.) -- (-2.,2.);
\draw [->,line width=1.2pt] (-2.,2.) -- (-4.,2.);
\begin{scriptsize}
\draw [fill=black] (8.,-2.) circle (2.5pt);
\draw[color=black] (11.5,10) node {$P_{1}$};
\draw[color=black] (-3,7) node {$G_{1}$};
\draw[color=black] (11.5,2) node {$P_{2}$};
\draw[color=black] (-3,-1) node {$G_{2}$};
\draw[color=black] (8,-2.25) node {1234};
\draw [fill=black] (6.,0.) circle (2.5pt);
\draw[color=black] (6.7,0) node {3214};
\draw [fill=black] (8,0) circle (2.5pt);
\draw[color=black] (8.5,0) node {1432};
\draw [fill=black] (10.,0.) circle (2.5pt);
\draw[color=black] (10.5,0) node {1243};
\draw [fill=black] (7.,2.) circle (2.5pt);
\draw[color=black] (7.6,2) node {4213};
\draw [fill=black] (9.,2.) circle (2.5pt);
\draw[color=black] (9.5,2) node {3412};
\draw [fill=black] (8.,4.) circle (2.5pt);
\draw[color=black] (8,4.3) node {4312};
\draw[color=black] (6.6,-1) node {2};
\draw[color=black] (8.2,-1) node {5};
\draw[color=black] (9.3,-1) node {6};
\draw[color=black] (6.1,.7) node {3};
\draw[color=black] (6.7,.7) node {5};
\draw[color=black] (8.1,.7) node {2};
\draw[color=black] (9.4,.7) node {2};
\draw[color=black] (7.3,3) node {5};
\draw[color=black] (8.7,3) node {1};
\draw [fill=black] (8.,6.) circle (2.5pt);
\draw[color=black] (8,5.7) node {1234};
\draw [fill=black] (6.5,8.) circle (2.5pt);
\draw[color=black] (7.2,8) node {1324};
\draw [fill=black] (5.,8.) circle (2.5pt);
\draw[color=black] (4.5,8) node {2134};
\draw [fill=black] (11.,8.) circle (2.5pt);
\draw[color=black] (11.5,8) node {1243};
\draw [fill=black] (6.,10.) circle (2.5pt);
\draw[color=black] (5.5,10) node {4132};
\draw [fill=black] (9.5,8.) circle (2.5pt);
\draw[color=black] (8.8,8) node {1432};
\draw [fill=black] (8.,10.) circle (2.5pt);
\draw[color=black] (8.5,10) node {2314};
\draw [fill=black] (10.,10.) circle (2.5pt);
\draw[color=black] (10.5,10) node {1342};
\draw [fill=black] (8.,12.) circle (2.5pt);
\draw[color=black] (8,12.3) node {4312};
\draw[color=black] (6,7) node {1};
\draw[color=black] (7,7) node {4};
\draw[color=black] (8.5,7) node {5};
\draw[color=black] (9.8,7) node {6};
\draw[color=black] (5.1,8.7) node {3};
\draw[color=black] (6.8,8.7) node {2};
\draw[color=black] (5.7,8.7) node {4};
\draw[color=black] (7.4,8.7) node {6};
\draw[color=black] (8.8,8.7) node {1};
\draw[color=black] (10.9,8.7) node {5};
\draw[color=black] (6.5,11) node {4};
\draw[color=black] (8.2,11) node {3};
\draw[color=black] (9.3,11) node {2};
\draw [fill=black] (2.,10.) circle (2.5pt);
\draw[color=black] (2,9.6) node {(6,5,2)};
\draw [fill=black] (0.,10.) circle (2.5pt);
\draw[color=black] (0,9.6) node {(4,6,2)};
\draw [fill=black] (-2.,10.) circle (2.5pt);
\draw[color=black] (-2,9.6) node {(4,2,3)};
\draw [fill=black] (-4.,10.) circle (2.5pt);
\draw[color=black] (-4,9.6) node {(1,4,3)};
\draw [fill=black] (-6.,10.) circle (2.5pt);
\draw[color=black] (-6,10.5) node {(1,3,4)};
\draw [fill=black] (-6.,8.) circle (2.5pt);
\draw[color=black] (-6,7.6) node {(5,1,4)};
\draw [fill=black] (-4.,2.) circle (2.5pt);
\draw[color=black] (-4,2.5) node {(2,3,5)};
\draw [fill=black] (-4.,0.) circle (2.5pt);
\draw[color=black] (-4,-0.4) node {(6,2,5)};
\draw [fill=black] (0.,2.) circle (2.5pt);
\draw[color=black] (0,1.6) node {(5,2,1)};
\draw [fill=black] (-2.,2.) circle (2.5pt);
\draw[color=black] (-2,1.6) node {(2,5,1)};
\end{scriptsize}
\end{tikzpicture}
\caption{On the left, the two connected components $G_{1}$ and $G_{2}$ of the flip graph $FG(1234,4312)$, and on the right, the corresponding flip posets $P_{1}$ and $P_{2}$. If 1243 and 1432 are identified, one would obtain the face poset of a triangle and a 2-gon, respectively. We discuss this identification in Section~\ref{sec:B3}. } 
\label{fig:flipoutput}
\end{figure}


Each $P_{i}$ has properties that resemble those of Bruhat intervals; for instance, consider the following lemma. 


\begin{lemma}\label{lem:rank}
Let $G_{i}$, $1\leq i\leq r(u,v)$, be a connected component of $FG(u,v)$ and $P_{i}$, with $1\leq i\leq r(u,v)$, be the corresponding flip poset. Then $P_{i}$ is graded.
\end{lemma}
\begin{proof}
We recall that $SP(u,v)$ is graded (see~\cite[Proposition 3]{B13}.) We now prove that the $\flip$ algorithm preserves the rank in $SP(u,v)$.

Let $C$ be a maximal chain of $SP(u,v)$ and $w\in W$ be an element in $C$. Let $r_C(w)$ be the length of the $u$-$w$ path in $C$. Furthermore, let $u_1$ and $v_1$ be elements in $C$ with $r_C(u_1)=r_C(w)-1$ and $r_C(v_1)=r_C(w)+1$. We show that the \textsc{Flip} algorithm does not change the value $r_{C}(w)$, that is, $r_{\Flip^{j}(C)}(w)=r_{C}(w)$ for all $j>1$. Suppose otherwise, and let $r_{C'}(w)$ be the length of the $u$-$w$ path $C'$, with $\Flip^{j}(C)=C'$ for some $j>1$. Let $u_2$ and $v_2$ be elements in $C'$ with $r_{C'}(u_2)=r_{C'}(w)-1$ and $r_{C'}(v_2)=r_{C'}(w)+1$. Notice that
	\[r_C(w)=\frac{r_C(u_1)+r_C(v_1)}{2}\quad \text{ and }\quad r_{C'}(w)=\frac{r_{C'}(u_2)+r_{C'}(v_2)}{2}.\]
	
	If $ r_C(w)\neq r_{C'}(w)$ then either $r_C(u_1)<r_{C'}(u_2)$ or $r_C(u_1)>r_{C'}(u_2)$, but in either case there is a contradiction to $C$ and $C'$ being maximal chains of $SP(u,v)$. Indeed, if it were the case, there would exist $D$ of the form $C_{w}(C')^{w}$ or $C'_{w}C^{w}$, where $C_{w}$ (or $C'_{w}$) and $C^{w}$ (or $(C')^{w}$) denotes the chain $C$ (or $C'$) of elements that are at most $w$ and the chain $C$ (or $C'$) of elements that are at least $w$, respectively. This chain $D$ would be shorter than $C$ and $C'$, which is not possible since $C$ and $C'$ are maximal chains in $SP(u,v)$. So $r_C(w)=r_{C'}(w)$. Thus the rank function of every flip poset $P_{i}$ of $SP(u,v)$ is the same as the rank function of $SP(u,v)$.\end{proof}

\begin{remark}
The proof of Lemma~\ref{lem:rank} holds in more generality. If one selects a maximal chain in a graded poset and there is a suitable definition of the $flip$ operation, the rank would be preserved after repeated applications of the $flip$ operation.
\end{remark}

\textbf{Useful notation:} We define the following notation. 

\begin{enumerate}
\item We write $x\leq_{s}y$ to denote that $x$ is smaller than $y$ in $SP(u,v)$. 
\item If $x\leq_s y$ is a \emph{cover relation}, that is, if there does not exist $z$ with $x\leq_s z\leq_s y$, then we use the notation $x\lessdot_s y$.
\item If $P_{1},\ldots,P_{r(u,v)}$ are the flip posets of the Bruhat interval $[u,v]$, we define $[x,y]_{P_{i}}:=\{z\in P_{i}:x\leq_{s} z\leq_{s} y \}$, for $x,y\in P_{i}$ and $1\leq i\leq r(u,v)$.
\end{enumerate}

As a consequence of the Subgraph Property (Proposition~\ref{prop:subgraph}), we have the following corollary.

\begin{corollary}\label{cor:atmostonerising1} If $x\in [u,v]$ and $P_{1},\ldots,P_{r(u,v)}$ are the flip posets of $[u,v]$ then
\begin{enumerate}
    \item[(i)] $[u,x]_{P_{i}}\subset[u,v]_{P_{i}}$ has one rising chain for $1\leq i\leq r(u,v)$.
    \item[(ii)] $[x,v]_{P_{i}}\subset[u,v]_{P_{i}}$ has at most one rising chain for $1\leq i\leq r(u,v)$.
\end{enumerate}
\end{corollary}

\begin{proof} 
\begin{enumerate}
\item[(i)] Let $d=(x=x_{0}<\cdots<x_{k}=v)$. The Subgraph Property, Proposition~\ref{prop:subgraph}(i), yields that $FG^{d}(u,v)\cong FG(u,x)$. Since each connected component of $FG(u,x)$ gives rise to a flip poset, which has a unique rising chain, $[u,x]_{P_{i}}$ must have a unique rising chain.
\item[(ii)] Let $c=(u=y_{0}<\cdots<y_{t}=x)$. Then the Subgraph Property, Proposition~\ref{prop:subgraph}(ii), gives the existence of an injection $\varphi:V(FG_{c}(u,v))\to V(FG(x,v))$ so that if $(C_{1},C_{2})\in E(FG_{c}(u,v))$ then $(c_{1},c_{2})\in E(FG(x,v))$, with $cc_{1}=C_{1}$ and $cc_{2}=C_{2}$. Since $\varphi$ is not necessarily a bijection since $FG(x,v)$ need not be a subgraph of $FG_{c}(u,v)$ (cf. Remark~\ref{rem:noiso}), there could be an edge $(c_{1},c_{2})$ of $FG(x,v)$ so that $(cc_{1},cc_{2})$ is not an edge of $FG_{c}(u,v)$. Hence a connected component of $FG_{c}(u,v)$ might not have a rising chain.\qedhere
\end{enumerate}
\end{proof}

Putting (i) and (ii) together we obtain the following proposition.

\begin{proposition}\label{cor:atmostonerising2}
If $P_1,\ldots,P_{r(u,v)}$ are the flip posets of $[u,v]$ then $[x,y]_{P_{i}}\subset[u,v]_{P_{i}}$ has at most one rising chain for $1\leq i\leq r(u,v)$.
\end{proposition}

\begin{proof}
It is enough to show that the proposition holds for $u\lessdot_{s} x\leq_{s} y$ or $u\leq_{s} y\lessdot_{s} v$, as $P_{i}$ is graded. These cases follow from Corollary~\ref{cor:atmostonerising1}(i) and~\ref{cor:atmostonerising1}(ii).
\end{proof}


Moreover, 

\begin{proposition}\label{prop:coatoms}
If $P_1,\ldots,P_{r(u,v)}$ are the flip posets of $[u,v]$ and $[x,y]_{P_{i}}\subset[u,v]_{P_{i}}$ is an interval of rank 2, then $[x,y]_{P_{i}}$ has at most two atoms for $1\leq i\leq r(u,v)$.
\end{proposition}

\begin{proof}
If there were more than two atoms, then either (i) $[x,y]_{P_{i}}$ would have at least two rising chains, or (ii) $[x,y]_{P_{i}}$ would have at least two falling chains. Proposition~\ref{cor:atmostonerising2} gives that Case (i) is impossible. On the other hand, if Case (ii) were true, then since the Bruhat interval $[x,y]$ has the same number of rising chains as falling chains, the pigeonhole principle gives that there would exist $j$ with $1\leq j\leq r(u,v)$ so that $[x,y]_{P_{j}}$ would have more than one rising chain. Again, this contradicts Proposition~\ref{cor:atmostonerising2}, and the result follows.
\end{proof}



We remark that Corollary~\ref{cor:atmostonerising1}, Proposition~\ref{cor:atmostonerising2}, and Proposition~\ref{prop:coatoms} hold in the case of Bruhat intervals, for which one can substitute the phrase ``at most'' with the word ``exactly.'' Indeed, since the Bruhat order is an Eulerian poset, every interval of length two has exactly two atoms (see~\cite[Lemma 2.7.3]{BB}).

\begin{lemma}\label{lem:even}
	Let $P_1,\ldots,P_{r(u,v)}$ be the flip posets of $[u,v]$ and $G_1,\ldots,G_{r(u,v)}$ be the corresponding connected components in the flip graph. Then each $G_{i}$, $1\leq i\leq r(u,v)$, has an even number of vertices. 
\end{lemma}
\begin{proof}
	Let $C=(t_1,t_2,t_3,\ldots,t_{\ell_{s}})$ be a vertex of $G_{i}$ (so $(t_1,t_2,t_3,\ldots,t_{\ell_{s}})$ is a maximal chain of $SP(u,v)$). Notice that $(t_1,t_2,t_3,\ldots,t_{\ell_{s}})$ is connected to $C'=(t_1',t_2',t_3,\ldots,t_{\ell_{s}})$, where $flip(t_1,t_2)=(t'_1,t'_2)$, as either $(t_{1},t_{2})$ or $(t'_{1},t'_{2})$ has a descent. Hence,  $C'$ is also a vertex of $G_{i}$, and thus one can establish a bijection 
	\[
	\varphi:\{C\in G_{i}:D(C)\cap\{1\}=\{1\}\}\longleftrightarrow\{C\in G_{i}:D(C)\cap\{1\}=\varnothing\}
	\]
	given by $(r_{1},r_{2},r_{3}\ldots,r_{\ell_{s}})\stackrel{\varphi}{\leftrightarrow}(r'_{1},r'_{2},r_{3},\ldots, r_{\ell_{s}})$, with $flip(r_{1},r_{2})=(r'_{1},r'_{2})$. Therefore the vertices of $G_i$ can be paired, and so there must be an even number of them.
\end{proof}


\section{$\Flip$ algorithm applied to $B_{2}(u,v)$ and $B_{3}(u,v)$}\label{sec:B3}

In this section we focus our attention on the case $k=2,3$. In these cases, we have been able to derive connections to the complete $\cd$-index. Indeed, one of the main open questions regarding the complete $\cd$-index is if its coefficients are nonnegative~\cite[Conjecture 6.1]{BiBr11}. Partial results exist for some coefficients~\cite{B11,B13,FH15,K13}. One approach that has not been explored much is to find a way of partitioning the elements of $B_{k}(u,v)$ of the same length in such a way that each of the parts would produce $\cd$-monomials that when added together would yield the terms of $\widetilde{\psi}_{u,v}(\cc,\dd)$ of degree $k-1$. In this section, we show that the $\flip$ algorithm provides such a procedure for $k=2,3$.

\subsection{Case $B_{2}(u,v)\neq\varnothing$} If $B_{2}(u,v)\neq\varnothing$, then the maximal chains of $SP(u,v)$ correspond to the elements of $B_{2}(u,v)$. In this case, the $\flip$ algorithm will split up the elements of $B_{2}(u,v)$ into $[\cc]_{u,v}$ components, each of them will have two elements, one of which will be falling and the other one will be rising. So in this case, the $\flip$ algorithm will split up the maximal chains of $SP(u,v)$ into $[\cc]_{u,v}$ pieces, each of them contributing $\cc$ to $\widetilde{\psi}_{u,v(\cc,\dd)}$. Moreover, each of these pieces is isomorphic to a Boolean poset on two elements, which we denote by $Boolean(2)$, and therefore each has ordinary $\cd$-index (seen as an Eulerian poset) of $\cc$. In other words,
\begin{equation}\label{eq:deg1}
[1]\widetilde{\psi}_{u,v}(\cc,\dd)=\sum_{i=1}^{[\cc]_{u,v}}\psi(Boolean(2)),
\end{equation}
where $[k]\widetilde{\psi}_{u,v}(\cc,\dd)$ denotes the coefficients of degree $k$ in $\widetilde{\psi}_{u,v}(\cc,\dd)$. Notice that (\ref{eq:deg1}) relates terms in the complete $\cd$-index to terms arising from the ordinary $\cd$-index of Eulerian posets. It turns out we can establish a similar equality for the terms of degree two in the complete $\cd$-index. 

\subsection{Case $B_{3}(u,v)\neq\varnothing$}

We can think of $B_{3}(u,v)$ as a poset by considering its elements as maximal chains, even if $B_1(u,v)\neq\varnothing$. First we need some definitions.

\begin{definition}[Order complex, face poset, and face lattice]
Following~\cite[Section 1.1]{W07}, we recall that for every partially ordered set $P$, one can define an abstract simplicial complex $\Delta(P)$,  called the \emph{order complex} of $P$,  as follows. The vertices of $\Delta(P)$ are the elements of $P$ and the faces of $\Delta(P)$ are the chains of $P$. In other words, $\Delta(P)=\{F\subseteq P\mid F\text{ is totally ordered}\}$. Similarly, if $\Delta$ is a simplicial complex, then its \emph{face poset} $P(\Delta)$ is the poset of nonempty faces of $\Delta$ ordered by inclusion. That is, if $F_{1}$ and $F_{2}$ are two nonempty faces of $\Delta$, then $F_{1}\leq F_{2}$ if and only if $F_{1}\subseteq F_{2}$. Furthermore, the \emph{face lattice} $L(\Delta)$ is $P(\Delta)$ with a smallest element $\hat0$ and a largest element $\hat1$ attached to it.
\end{definition}

\begin{lemma}\label{lem:ballorsphere}
	Let $P_{1},\ldots,P_k$ be the flip poset of $B_{3}(u,v)$. Then $\Delta(P_{i}\setminus\{u,v\})$ is isomorphic to a path or a polygon for $1\leq i\leq k$. 
\end{lemma}
\begin{proof}
	The result follows if we show that each vertex in $G_{i}$ has degree at most 2. This is clear as any subinterval $[x,y]_{P_{i}}\subset[u,v]_{P_{i}}$ of rank two has at most four elements as a consequence of Proposition~\ref{cor:atmostonerising2}. 
\end{proof}

To illustrate the previous lemma, for example, the order complexes corresponding to the flip posets of Example~\ref{ex:one} are depicted in Figure~\ref{fig:orderflip}. In this case, they are both paths.

\subsubsection{Identification}  Let $\Delta$ be the order complex $\Delta(P_{i}\setminus\{u,v\})$ for some flip poset $P_{i}$ of $B_{3}(u,v)$. Then by Lemma~\ref{lem:ballorsphere}, $\Delta$ is either isomorphic to a path or a polygon. We define $I(\Delta)$ to be the following operator: If $\Delta$ is a polygon, then $I(\Delta):=\Delta$, and if $\Delta$ is a path, then $I(\Delta)$ is the unique polygon obtained by identifying the two vertices of degree 1 and preserving the other vertices and edges of $\Delta$. For instance, after identification, the order complexes of the flip posets of Example~\ref{ex:one}, shown in Figure~\ref{fig:orderflip}, become a hexagon and a square, respectively.

\begin{figure}[h!] 
\begin{center} 
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
%\clip(-4.,0) rectangle (20.,4.5);
\draw [line width=1.2pt] (2.,4.)-- (1.,3.);
\draw [line width=1.2pt] (0.98,1.66)-- (1.,3.);
\draw [line width=1.2pt] (0.98,1.66)-- (2.5,0.7);
\draw [line width=1.2pt] (2.5,0.7)-- (4.04,1.62);
\draw [line width=1.2pt] (4.04,1.62)-- (4.,3.);
\draw [line width=1.2pt] (4.,3.)-- (3.,4.);
\draw [line width=1.2pt] (9.2,3.76)-- (8.,3.);
\draw [line width=1.2pt] (8.,3.)-- (8.,1.);
\draw [line width=1.2pt] (8.,1.)-- (10.,1.);
\draw [line width=1.2pt] (10.,1.)-- (10.,3.);
\begin{scriptsize}
\draw [fill=black] (2.,4.) circle (2.5pt);
\draw [fill=black] (3.,4.) circle (2.5pt);
\draw [fill=black] (1.,3.) circle (2.5pt);
\draw [fill=black] (4.,3.) circle (2.5pt);
\draw [fill=black] (0.98,1.66) circle (2.5pt);
\draw [fill=black] (4.04,1.62) circle (2.5pt);
\draw [fill=black] (2.5,0.7) circle (2.5pt);
\draw[color=black] (1.26,3.8) node {5};
\draw[color=black] (.7,2.5) node {6};
\draw[color=black] (1.6,1.0) node {2};
\draw[color=black] (3.4,1.0) node {4};
\draw[color=black] (4.3,2.5) node {3};
\draw[color=black] (3.72,3.8) node {1};
\draw [fill=black] (9.2,3.76) circle (2.5pt);
\draw [fill=black] (8.,3.) circle (2.5pt);
\draw [fill=black] (8.,1.) circle (2.5pt);
\draw [fill=black] (10.,1.) circle (2.5pt);
\draw [fill=black] (10.,3.) circle (2.5pt);
\draw[color=black] (8.5,3.6) node {2};
\draw[color=black] (7.8,2.0) node {3};
\draw[color=black] (8.98,0.8) node {5};
\draw[color=black] (10.16,2) node {2};
\draw[color=black] (10,3.2) node {$x$};
\draw[color=black] (9.2,4) node {$y$};
\draw[color=black] (1.9,4.2) node {$x$};
\draw[color=black] (3.2,4.2) node {$y$};
\end{scriptsize}
\end{tikzpicture}
\caption{The order complexes $\Delta_{1}:=\Delta(P_{1}\setminus\{1234,4312\})$ and $\Delta_{2}:=\Delta(P_{2}\setminus\{1234,4312\})$, where $P_{1},P_{2}$ are the posets in Figure~\ref{fig:flipoutput}. After identification of vertices $x$ and $y$, $\Delta_{1}$ and $\Delta_{2}$ are the barycentric subdivision of a triangle and a 2-gon, respectively. } 
\label{fig:orderflip} 
\end{center} 
\end{figure} 

Lemma~\ref{lem:even} and Lemma~\ref{lem:ballorsphere} guarantee that, after identification if needed, $\Delta(P_{i}\setminus \{u,v\})$ will be an $n$-gon with an even number of sides. Thus, said order complex is the barycentric subdivision of an $\frac{n}{2}$-gon. The face posets of these $\frac{n}{2}$-gons shall be utilized to express the terms of degree two in the complete $\cd$-index as sums of the $\cd$-index of Eulerian posets. This is discussed in the next subsection. 


\subsection{Terms of degree two in the complete $\cd$-index}

In this sub-section we show how the $\Flip$ algorithm separates $B_{3}(u,v)$ into Eulerian pieces whose $\cd$-index adds up to the degree-two terms of $\cpsi_{u,v}(\cc,\dd)$. In particular, we establish that the terms corresponding to the paths in $B_{3}(u,v)$ are non-negative. Using a different method, the non-negativity of these terms has already been established by Karu~\cite{K13} as they contain at most one $\mathbf{d}$. Our approach, however, allows us to describe these monomials in the complete $\cd$-index in terms of the (ordinary) $\cd$-index of Eulerian posets, thus providing a nice connection between the two concepts and concluding non-negativity of certain terms in the complete $\cd$-index.


We now prove that the terms of degree two in the complete $\cd$-index are given by adding up the $\cd$-index of posets coming from the $\flip$ algorithm.

\begin{theorem}
Suppose that $B_3(u,v)\neq\varnothing$ and let $P_{i}$, for $1\leq i\leq k$, be the flip posets of $B_{3}(u,v)$. Furthermore, let  $\Delta_{i}=\Delta(P_{i}\setminus\{u,v\})$,  and $P'_i:=L(I(\Delta_{i}))$ (the face lattice of $\Delta_{i}$ after identification). Then the terms of degree two of the complete $\cd$-index are obtained by adding the $\cd$-index of all the $P'_i$. In other words,
\[
[2]\widetilde{\psi}_{u,v}(\cc,\dd)=\sum_{i=1}^{k}\psi(P'_i).
\]
\end{theorem}

\begin{proof}
Lemma~\ref{lem:even} gives that $I(\Delta_{i})$ is a polygon of even length. Thus $I(\Delta_{i})$ is the first barycentric subdivision of an $m_{i}$-cycle for some positive integer $m_i$. Therefor, $P'_i$ (and $P_{i}$) has $2m_i$ maximal chains. Notice that the flag $f$-vector of $P'_{i}$ is $f_{\varnothing}=1$, $f_{\{1\}}=m_{i}=f_{\{2\}}$, and $f_{\{1,2\}}=2m_{i}$ and therefore the flag $h$-vector of $P'_i$ is $h_\varnothing=1,h_{\{1\}}=m_i-1=h_{\{2\}}$, and $h_{\{1,2\}}=1$. It follows that the $\aaa\bbb$-index of $P'_i$ is \begin{align*}
\aaa^2+(m_i-1)\aaa\bbb+(m_i-1)\bbb\aaa+\bbb^2=(\aaa^2+\aaa\bbb+\bbb\aaa+\bbb^2)+(m_i-2)(\aaa\bbb+\bbb\aaa).
\end{align*}
Thus, $\psi(P'_i)=\cc^2+(m_i-2)\dd$, and the sum of the $\cd$-index of $P'_{1},\ldots,P'_{k}$ is
\begin{align*}
\sum_{i=1}^{k}(P'_{i}) = k\cc^{2}+\sum_{i=1}^{k}(m_{i}-2)\dd.
\end{align*}


Let us now compute the terms of degree two of $\cpsi_{u,v}(\cc,\dd)$. Since there are $k$ flip posets, there are exactly $k$ rising paths and $k$ falling paths in $B_3(u,v)$. Thus, 
\begin{equation}\label{eq:cd2}
[2]\cpsi_{u,v}(\cc,\dd)=k(\aaa^{2}+\bbb^{2})+n_{ab}\aaa\bbb+n_{ba}\bbb\aaa,
\end{equation}
where $n_{ab}$ and $n_{ba}$ are the number of $\aaa\bbb$ and $\bbb\aaa$ monomials, respectively.  Notice that $n_{ab}+n_{ba}$ is the number of paths in $B_{3}(u,v)$ that are neither rising nor falling. Thus \[n_{ab}+n_{ba}=\sum_{i=1}^{k}(2m_{i}-2),\]
since each flip poset $P_{i}$ has $2m_i$ maximal chains. The existence of $\cpsi_{u,v}(\cc,\dd)$ gives that $n_{ab}=n_{ba}$, and therefore~(\ref{eq:cd2}) becomes
\begin{align*}
[2]\cpsi_{u,v}(\cc,\dd)&=k(\aaa^{2}+\bbb^{2})+\sum_{i=1}^{k}(m_{i}-1)(\aaa\bbb+\bbb\aaa)\\
&=k(\aaa^{2}+\aaa\bbb+\bbb\aaa+\bbb^{2})+\sum_{i=1}^{k}(m_{i}-2)(\aaa\bbb+\bbb\aaa)\\
&=k\cc^2+\sum_{i=1}^{k}(m_{i}-2)\dd,
\end{align*} and the result follows.
\end{proof}

\begin{example} Let us consider the interval $[1234,4312]$ in $A_{3}$. One can compute $\cpsi_{u,v}(\cc,\dd)$ to get
\[  \widetilde{\psi}_{1234,4312}(\cc,\dd)=\cc^4 + \cc^2\dd + 2\cc\dd\cc+\dd\cc^2 + \dd^2  +2\cc^2 + \dd.\]

From Example~\ref{ex:one}, shown in Figure~\ref{fig:flipoutput}, we know that $B_3(1234,4312)$ has two flip posets $P_1$ and $P_2$. The face posets of their order complex, $\Delta_{1}$ and $\Delta_{2}$, shown in Figure~\ref{fig:orderflip}, are that of a triangle and a 2-gon, and they contribute $\cc^{2}+\dd$ and $\cc^{2}$, respectively. The sum gives the degree-two terms of $\cpsi_{1234,4312}(\cc,\dd)$, $2\cc^2+\dd$.
\end{example}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}

The author thanks Louis J. Billera and Matthew Dyer for many helpful discussions throughout the years. The author was partially supported by NSF grant DMS-0555268. We also thank the referee for valuable suggestions that helped improved this paper.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% You do not have to use the same format for your references, but 
%    include everything in this file.  Don't use natbib please.
% If you use BibTeX to create a bibliography, copy the .bbl file into here.

\begin{thebibliography}{99}

\bibitem{BK91}
Margaret~M. Bayer and Andrew Klapper.
\newblock A new index for polytopes.
\newblock {\em Discrete Comput. Geom.}, 6(1):33--47, 1991.

\bibitem{BiBr11}
Louis~J. Billera and Francesco Brenti.
\newblock Quasisymmetric functions and {K}azhdan-{L}usztig polynomials.
\newblock {\em Israel J. Math.}, 184:317--348, 2011.

\bibitem{BGS82}
Anders~Bj\"orner, Adriano~M. Garsia, and Richard~P. Stanley.
\newblock An introduction to {C}ohen-{M}acaulay partially ordered sets.
\newblock In {\em Ordered sets ({B}anff, {A}lta., 1981)}, volume~83 of {\em
  NATO Adv. Study Inst. Ser. C: Math. Phys. Sci.}, pages 583--615. Reidel,
  Dordrecht-Boston, Mass., 1982.

\bibitem{BB}
Anders Bj{\"o}rner and Francesco Brenti.
\newblock {\em Combinatorics of {C}oxeter {G}roups}, volume 231 of {\em
  Graduate Texts in Mathematics}.
\newblock Springer, New York, 2005.

\bibitem{BW82}
Anders Bj{\"o}rner and Michelle Wachs.
\newblock Bruhat order of {C}oxeter groups and shellability.
\newblock {\em Adv. in Math.}, 43(1):87--100, 1982.

\bibitem{B11}
Sa{\'u}l~A. Blanco.
\newblock The complete {\bf cd}-index of dihedral and universal {C}oxeter
  groups.
\newblock {\em Electron. J. Combin.}, 18(1):\#P174, 2011.

\bibitem{B13}
Sa{\'u}l~A. Blanco.
\newblock Shortest path poset of {B}ruhat intervals.
\newblock {\em J. Algebraic Combin.}, 38(3):585--596, 2013.

\bibitem{D12}
Matthew Dyer.
\newblock Proof of {C}ellini's conjecture on self-avoiding paths in {C}oxeter
  groups.
\newblock {\em Compos. Math.}, 148(2):548--554, 2012.

\bibitem{D91}
Matthew~J. Dyer.
\newblock On the ``{B}ruhat graph'' of a {C}oxeter system.
\newblock {\em Compositio Math.}, 78(2):185--191, 1991.


\bibitem{D93}
Matthew~J. Dyer.
\newblock Hecke algebras and shellings of {B}ruhat intervals.
\newblock {\em Compositio Math.}, 89(1):91--115, 1993.

\bibitem{FH15}
Neil~J.Y. Fan and Liao He.
\newblock On the non-negativity of the complete cd-index.
\newblock {\em Discrete Mathematics}, 338(11):2037 -- 2041, 2015.

\bibitem{H90}
James~E. Humphreys.
\newblock {\em Reflection {G}roups and {C}oxeter {G}roups}, volume~29 of {\em
  Cambridge Studies in Advanced Mathematics}.
\newblock Cambridge University Press, Cambridge, 1990.

\bibitem{K06}
Kalle Karu.
\newblock The \textbf{cd}-index of fans and posets.
\newblock {\em Compos. Math.}, 142(3):701--718, 2006.

\bibitem{K13}
Kalle Karu.
\newblock On the complete {\bf cd}-index of a {B}ruhat interval.
\newblock {\em J. Algebraic Combin.}, 38(3):527--541, 2013.

\bibitem{R04}
Nathan Reading.
\newblock The \textbf{cd}-index of {B}ruhat intervals.
\newblock {\em Electron. J. Combin.}, 11(1):\#R74, 2004.

\bibitem{W07}
Michelle~L. Wachs.
\newblock Poset topology: tools and applications.
\newblock In {\em Geometric combinatorics}, volume~13 of {\em IAS/Park City Math. Ser.}, pages 497--615. Amer. Math. Soc., Providence, RI, 2007.


\end{thebibliography}

\end{document}