%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{77}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{definition}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{corollary}[thm]{Corollary}
\newtheorem{remark}[thm]{Remark}

% \usepackage{lipsum}

\usepackage{tikz, 
mathtools % to use \coloneqq
}
\usetikzlibrary{positioning,shapes,shadows,arrows}



\newcommand{\rw}[1]{\left[{#1}\right]} % notation for reduced words
% \newcommand{\mf}[1]{\mbox{$\mathfrak #1$}} % mathfrak, used for font of symmetric group

\newcommand{\supp}{\textnormal{\textsf{supp}}} % support of an element of a Coxeter group

% \newcommand{\len}{\sf len}

\DeclareMathOperator{\sort}{{\sf sort}_c}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}

\newcommand\LatticeC{{\mathcal L}({\text{c-singletons})}}
\newcommand{\Cambrian}{\mathcal L}
\newcommand{\pidown}{\pi_\downarrow}
\definecolor{forGreen}{RGB}{0,120,0}

\newcommand{\bir}{{\sf Birk}}
\newcommand{\ord}{\mathcal{O}}
\newcommand{\heap}{{\sf Heap}}

\newcommand{\X}{\color{red}\mathsf{X}}
\usepackage{circledsteps}

\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
\node[blue,shape=circle,draw,inner sep=0.7pt] (char) {#1};}}

\usetikzlibrary{shapes.geometric}

\newcommand*\starred[1]{\tikz[baseline=(char.base)]{
\node[violet,shape=diamond,draw,inner sep=0.7pt] (char) {#1};}}

\newcommand*\rectangled[1]{\tikz[baseline=(char.base)]{
\node[red,shape=rectangle,draw,inner sep=1.1pt] (char) {#1};}}

%% define your title in the usual way
\title{
Pattern-avoiding polytopes and Cambrian lattices
}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{
Esther Banaian\thanks{\href{banaian@math.au.dk}{banaian@math.au.dk}
% {Esther Banaian was partially supported by Grant 2017.11.14.$\partial$\;supp.}
}\addressmark{1}, Sunita Chepuri\thanks{\href{schepuri@pugetsound.edu}{schepuri@pugetsound.edu}}\addressmark{2}, Emily Gunawan\thanks{\href{emily\_gunawan@uml.edu}{emily\_gunawan@uml.edu}}\addressmark{3},
\and Jianping Pan\thanks{\href{jpan9@ncsu.edu}{jpan9@ncsu.edu}}\addressmark{4}
}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Aarhus University, Aarhus, Denmark \\ 
\addressmark{2}Department of Mathematics and Computer Science, University of Puget Sound, Tacoma, WA, USA \\ 
\addressmark{3}Department of Mathematics and Statistics, University of Massachusetts Lowell, Lowell, USA\\ 
\addressmark{4}Department of Mathematics, North Carolina State University, Raleigh, USA }

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
% We define a family of pattern-avoiding Birkhoff subpolytopes whose vertices are c-singletons of the symmetric group. 
For each Coxeter element c in the symmetric group, we define a pattern-avoiding Birkhoff subpolytope whose vertices are the c-singletons. 
We show that the normalized volume of our polytope is equal to the number of longest chains in a corresponding type A Cambrian lattice.
% \esther{do we ever say this in the document?}\jianping{It is implied. I just added a new sentence at the end of the last section.}
% The normalized volume of each of these polytopes is equal to the number of longest chains in a corresponding type A Cambrian lattice. 
% Our work recovers a result of Davis and Sagan which states that the normalized volume of the convex full of the 132 and 312 avoiding permutation matrices is the number of longest chains in the Tamari lattice. 
Our work extends a result of Davis and Sagan which states that the normalized volume of the convex hull of the 132 and 312 avoiding permutation matrices is the number of longest chains in the Tamari lattice, a special case of a type A Cambrian lattice. 
Furthermore, we prove that 
each of our polytopes is unimodularly equivalent to the order polytope of the heap of the c-sorting word of the longest permutation.  
This gives an affirmative answer to a generalization of a question posed by Davis and Sagan. 
% This gives an affirmative answer to a question posed by Davis and Sagan on whether their 132 and 312 avoiding Birkhoff subpolytope is unimodularly equivalent to an order polytope.
}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{order polytopes, heap, Birkhoff polytopes, Cambrian lattices, permutations}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

%\tableofcontents 

\section{Introduction}
% \esther{going to bed, I sign off on the submission once you all finish your edits!}

The sequence \cite[A003121]{oeis} 
% https://oeis.org/A003121
% See the most recent comments (2015-2022) in https://oeis.org/A003121 by Heinz, Davis, and Gunawan.
counts 
shifted standard tableaux of staircase shape and  
longest chains in the Tamari lattice; 
it also counts the number of reduced words in a certain commutation class of the longest permutation. 
More recently, it was shown by Davis and Sagan in \cite{DS18} that this sequence gives the normalized volume of a certain "pattern-avoiding polytope," a subpolytope of the Birkhoff polytope whose vertices are 132 and 312 avoiding permutations. 
Since these permutations form a distributive sublattice of the right weak order, Davis and Sagan asked whether their polytope might be unimodularly equivalent to the order polytope of the poset of join irreducibles of the 
132 and 312 avoiding permutations.


In the same paper, Davis and Sagan pointed out that the 132 and 312 avoiding permutations
are known to be the $c$-singletons for the symmetric group for a specific "Tamari" Coxeter element $c$ and proposed that
it would be interesting to define 
similar pattern-avoiding polytopes for other Coxeter groups 
and study them 
from the perspective of c-singletons. 
The $c$-singletons are the spine of an important lattice called the $c$-Cambrian lattice~\cite{Rea06}, and they form a distributive sublattice of the right weak order~\cite{HLT11}. 
% Since the vertices of $\bir$ forms a distributive sublattice of the right weak order, 
% In light of this, Davis and Sagan asked whether their polytope 
% % $\bir$ 
% might be unimodularly equivalent to the order polytope of the poset of join irreducibles of the 
% 132 and 312 avoiding permutations. 
%$c$-singletons. 


In this article, we associate a pattern-avoiding polytope to each Coxeter element $c$ in the symmetric group. We define this polytope to be the convex hull of the permutation matrices of the $c$-singletons (see Sections~\ref{sec: def of c-singletons} and \ref{sec:definition of c-birkhoff polytope}). 
We prove that our polytope is indeed unimodularly equivalent to the order polytope of the poset of join irreducibles of the $c$-singletons (see Section~\ref{sec.unimodular}). In particular, for the Tamari Coxeter element, our result answers Davis and Sagan's question in the affirmative.

% Proposal Title: Volumes of pattern-avoiding polytopes and Cambrian lattices

% === begin proposal ==
% The sequence https://oeis.org/A003121 counts longest chains in the Tamari lattice; it also counts the number of reduced words in a certain commutation class of the longest permutation. Recently, it was shown by Davis and Sagan that this sequence gives the normalized volume of a certain "pattern-avoiding polytope", a subpolytope of the Birkhoff polytope whose vertices are 132 and 312 avoiding permutations. Such permutations are known to be c-singletons for the symmetric group for a specific Coxeter element c. See the most recent comments (2015-2022) in https://oeis.org/A003121 by Heinz, Davis, and Gunawan.

% For each Coxeter element of the symmetric group, we can define a semidistributive lattice called a type A Cambrian lattice. The Tamari lattice is a special case of a type A Cambrian lattice. With the exception of the volume of the polytope, all facts above have been generalized to all type A Cambrian lattices. 

% We propose to generalize Davis' and Sagan's pattern-avoiding polytope results to all type A Cambrian lattices. In particular, we conjecture that the number of longest chains in a type A Cambrian lattice is in fact the volume of a pattern-avoiding polytope. A Polymake computation (thanks to Davis) confirms this conjecture for a so-called bipartite type A Cambrian lattices up to n=7.

% === end proposal ==



\section{Background and notation}
Denote the symmetric group on $n+1$ elements by $A_n$.
We can represent a permutation $w\in A_n$ in \emph{one-line notation} as $w = w(1)w(2)\cdots w(n+1)$. 
For each $i \in \{1, \ldots, n\}$, we write $s_i \in A_n$ to denote the \emph{simple reflection} (or \emph{adjacent transposition})
that swaps $i$ and $i+1$ and fixes all other letters. 
Every permutation can be expressed as a product of simple reflections. Given $w\in A_n$, the minimum number of simple reflections among all such expressions for $w$ is called the \emph{(Coxeter) length} of $w$, and is denoted by $\ell(w)$. 
A \emph{reduced decomposition} of $w$ is an expression $w=s_{i_1} \cdots s_{i_{\ell(w)}}$ realizing the Coxeter length of $w$. To simplify notation, we refer to such a  decomposition via its \emph{reduced word} $\rw{i_1 \cdots i_{\ell(w)}}$. 
For example, consider  $w = 51342 \in A_4$. 
One of its reduced decompositions is 
$s_{4}s_{2}s_{3}s_{2}s_{4}s_{1} $ 
with $\rw{423241}$ as the corresponding reduced word, and  $\ell(w)=6$. 

A \emph{Coxeter element} $c$ in 
$A_n$ is a product of all $n$ simple reflections in any order, where each reflection appears exactly once.  
The longest permutation of $A_n$ is the permutation $w_0= (n+1)n \dots 321$ and  
% One of its reduced words is $\rw{12\dots n
% \ \  
% 12 \dots(n-1) 
% \dots 
% 123 \ \ 
% 12 \ \ 
% 1}$ and 
$\ell(w_0)=\binom{n+1}{2}$.


Simple reflections satisfy \emph{commutation relations} of the form $s_i s_j=s_j s_i$ for $|i-j| > 1$. 
An application of a commutation relation to a product of simple reflections is called a \emph{commutation move}. 
% and \emph{(long) braid relations} of the form $s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}$. 
% An application of a commutation relation (respectively, braid relation) to a product of simple reflections is called a \emph{commutation move} (respectively, a \emph{braid move}). 
% The set of reduced decompositions of a permutation is related by a sequence of commutation moves and  braid moves.  
When referring to reduced words, 
we will say adjacent letters $i$ and $j$ in a reduced word \emph{commute} when $|i - j| > 1$. 
Given a reduced word $\rw{u}$ of a permutation, the equivalence class consisting of all words that can be obtained from $\rw{u}$ by a sequence of commutation moves is the \emph{commutation class} of $\rw{u}$.





\subsection{Heaps}
We review the classical theory of heaps, which was used in~\cite{Ste96} to study fully commutative elements of a Coxeter group. 
Heaps also appeared as "the natural partial orders" in \cite[Definition 6]{GR08} and \cite[Definition 1]{LL20} and they were used to study certain acyclic domains. 
For a detailed list of attributions on the theory of heaps, see~\cite[Solutions to Exercise 3.123(ab)]{Sta12}.

% Given a reduced word $\rw{u}$ of a permutation, we can associate to $\rw{u}$ a \emph{heap}, a poset whose elements are labeled by the simple reflections in $\rw{u}$. 
% A \emph{heap diagram} is the Hasse diagram for a heap in which poset elements are replaced by their labels. \esther{it feels like this and the formal definition are repetitive}


\begin{definition}
\label{defn:heap of a reduced word}
Given a %an arbitrary 
reduced word $\rw{u}=\rw{u_1 \cdots u_\ell}$ of a permutation, 
consider the
partial order $\preccurlyeq$ on the set $\{ 1, \dots, \ell\}$ obtained via the transitive closure of the relations 
\[x
\prec
y\]
for $x < y$ such that
$|u_x-u_y| \leq 1$ (that is, $u_x$ and $u_y$ do not commute). 
For each $1 \leq x \leq \ell$, the \emph{label} of the poset element $x$ is  $u_x$. This labeled poset is called the \emph{heap} for $\rw{u}$, denoted $\heap(\rw{u})$. The Hasse diagram for this poset with elements $\{1,\ldots, \ell\}$ replaced by their labels is called the \emph{heap diagram} for $\rw{u}$. 
The labels in the heap diagram are drawn in increasing order
from left to right.  
\end{definition}



\newcommand{\posetelt}[1]{{#1}}
\newcommand{\posetLABEL}[1]{{#1}}
\begin{figure}[htb!]
\begin{center}
\begin{tikzpicture}[scale=0.7]
% First, locate each of the nodes and name them
\node (s1a) at (0,0) {$\posetelt{1}$}; %{$s_1$};
\node (s2a) at (1,1) {$\posetelt{2}$}; %{$s_2$};
\node (s3a) at (2,2) {$\posetelt{5}$}; %{$s_3$};
\node (s4a) at (3,1) {$\posetelt{4}$}; %{$s_4$};
\node (s1b) at (0,2) {$\posetelt{3}$}; %{$s_1$};
\node (s2b) at (1,3) {$\posetelt{6}$}; %{$s_2$};
\node (s3b) at (2,4) {$\posetelt{9}$}; %{$s_3$};
\node (s4b) at (3,3) {$\posetelt{8}$}; %{$s_4$};
\node (s1c) at (0,4) {$\posetelt{7}$}; %{$s_1$};
\node (s2c) at (1,5) {$\posetelt{10}$}; %{$s_2$};

% Now draw the lines:
\draw [
black, % red, 
thick, shorten <=-2pt, shorten >=-2pt] (s1a) -- (s2a);
\draw [
black, % red, 
thick, shorten <=-2pt, shorten >=-2pt] (s2a) -- (s3a);
\draw [
black, % red, 
thick, shorten <=-2pt, shorten >=-2pt] (s3a) -- (s4a);

\draw [
black, %orange, 
thick, shorten <=-2pt, shorten >=-2pt] (s1b) -- (s2b);
\draw [
black, %orange, 
thick, shorten <=-2pt, shorten >=-2pt] (s2b) -- (s3b);
\draw [
black, %orange, 
thick, shorten <=-2pt, shorten >=-2pt] (s3b) -- (s4b);

\draw [
black, %violet, 
thick, shorten <=-2pt, shorten >=-2pt] (s1c) -- (s2c);

\draw [thick, shorten <=-2pt, shorten >=-2pt] (s2a) -- (s1b); 
\draw [thick, shorten <=-2pt, shorten >=-2pt] (s3a) -- (s4b);
\draw [thick, shorten <=-2pt, shorten >=-2pt]  (s3a) -- (s2b) -- (s1c);
\draw [thick, shorten <=-2pt, shorten >=-2pt] (s3b) -- (s2c);
\end{tikzpicture}
\qquad
\qquad
\begin{tikzpicture}[scale=0.7]
% First, locate each of the nodes and name them
\node (s1a) at (0,0) {$\posetLABEL{1}$};
\node (s2a) at (1,1) {$\posetLABEL{2}$};
\node (s3a) at (2,2) {$\posetLABEL{3}$};
\node (s4a) at (3,1) {$\posetLABEL{4}$};
\node (s1b) at (0,2) {$\posetLABEL{1}$};
\node (s2b) at (1,3) {$\posetLABEL{2}$};
\node (s3b) at (2,4) {$\posetLABEL{3}$};
\node (s4b) at (3,3) {$\posetLABEL{4}$};
\node (s1c) at (0,4) {$\posetLABEL{1}$};
\node (s2c) at (1,5) {$\posetLABEL{2}$};

% Now draw the lines:
\draw [
black, %red, 
thick, shorten <=-2pt, shorten >=-2pt] (s1a) -- (s2a);
\draw [
black, %red, 
thick, shorten <=-2pt, shorten >=-2pt] (s2a) -- (s3a);
\draw [
black, %red, 
thick, shorten <=-2pt, shorten >=-2pt] (s3a) -- (s4a);

\draw [
black, %orange, 
thick, shorten <=-2pt, shorten >=-2pt] (s1b) -- (s2b) node[pos=0.5, left=5mm]{};
\draw [
black, %orange, 
thick, shorten <=-2pt, shorten >=-2pt] (s2b) -- (s3b);
\draw [
black, %orange, 
thick, shorten <=-2pt, shorten >=-2pt] (s3b) -- (s4b);

\draw [
black, %violet, 
thick, shorten <=-2pt, shorten >=-2pt] (s1c) -- (s2c);

\draw [
black, thick, 
shorten <=-2pt, shorten >=-2pt] (s2a) -- (s1b); 
\draw [thick, shorten <=-2pt, shorten >=-2pt] (s3a) -- (s4b);
\draw [thick, shorten <=-2pt, shorten >=-2pt]  (s3a) -- (s2b) -- (s1c);
\draw [thick, shorten <=-2pt, shorten >=-2pt] (s3b) -- (s2c);
\end{tikzpicture}
\caption{Hasse diagram of the underlying poset (left) and the heap diagram (right) of a commutation class of $w_0$ given in Example \ref{ex:fig:longest element heap A4 for c 1243}.}
\label{fig:longest element heap A4 for c 1243}
\end{center}
\end{figure}

\begin{example}\label{ex:fig:longest element heap A4 for c 1243}
Consider 
a reduced word $\rw{u}=\rw{u_1 \dots u_{10}}=\rw{1 21 4321 432}$ %$s_1 s_2s_1 s_4s_3s_2s_1 s_4s_3s_2$ 
of the longest element $w_0$ in $A_4$. 
\begin{enumerate}
\item 
Figure~\ref{fig:longest element heap A4 for c 1243} (left) shows a Hasse diagram of the underlying unlabeled poset $\heap(\rw{u})$. 
Here $\ell=10$ and so the
the elements of the heap poset $\heap(\rw{u})$ are $\{1,2,\dots, 10 \}$. 
\item 
Figure~\ref{fig:longest element heap A4 for c 1243} (right) shows the heap diagram for $\heap(\rw{u})$. The possible labels of the poset elements are $\{1,2,3,4\}$.
\end{enumerate}
\end{example}





Linear extensions of $\heap(\rw{u})$ relate to the commutation class of $\rw{u}$.



\begin{definition}\label{def:Labeled linear extensions}
A \emph{linear extension} 
$\pi = \pi(1) \cdots \pi(\ell)$ 
of a partial order $\preccurlyeq$ on $\{1,\ldots, \ell\}$
 is a total order
 on the poset elements that is consistent with the structure of the poset. 
That is, $x \prec y$ implies $\pi(x) < \pi(y)$.
A \emph{labeled linear extension} of the heap of a reduced word $\rw{u}=\rw{u_1 \cdots u_\ell}$
is a word $\rw{u_{\pi(1)} \cdots u_{\pi(\ell)}}$, 
where 
 $\pi = \pi(1) \cdots \pi(\ell)$ 
 is a linear extension of the heap. 
\end{definition}

%As the next proposition illustrates, labeled linear extensions are related to reduced words and commutation classes.

\begin{proposition}
[{\cite[Proof of Proposition~2.2]{Ste96} and~\cite[Solutions to Exercise 3.123(ab)]{Sta12}}]
\label{prop:set of labeled linear extensions is commutativity class Stembridge}
Given a reduced word $\rw{u}$,  the set of labeled linear extensions of the heap for $\rw{u}$ is the commutation class of $\rw{u}$.
\end{proposition}

\begin{example}\label{ex:linear ext A4 for c 1243}
% The heap diagram of the reduced word $\rw{1 21 4321 432}$ of the longest permutation $w=54321 \in A_4$ is depicted in Figure~\ref{fig:longest element heap A4 for c 1243}. 
%Figure~\ref{fig:longest element heap A4 for c 1243} shows three different diagrams illustrating (from left to right) a Hasse diagram of an unlabeled heap poset, its heap diagram, and a linear extension.  
Three of labeled linear extensions of $\heap(\rw{u})$ from Example~\ref{ex:fig:longest element heap A4 for c 1243} are 
$\rw{u}$ itself,
$\rw{1243 1243 12}$, 
and 
$\rw{4123  4123  12}$.  Notice that these reduced words all belong to the same commutation class, due to Proposition~\ref{prop:set of labeled linear extensions is commutativity class Stembridge}. 
\end{example}




\subsection{Order polytopes}
\label{sec:order polytope}

In this section, we review \emph{order polytopes}, following Stanley's paper~\cite{Sta86}. 
Given a finite poset $P$, the order polytope of $P$ is given by
\[
\mathcal{O}(P) \coloneqq \{x\in \R^P: 0\leqslant x_t \leqslant 1 \text{ for all }  t\in P \text{ and } x_t \leqslant x_s \text{ when } t\leqslant_P s\}\,.
\]

Many basic properties of an order polytope are answered by the combinatorial structure of the poset. 
Below are some properties that are relevant to us.
% We list some of them from~\cite{Sta86} below which we will need.



\begin{enumerate}
\item The dimension of $\mathcal{O}(P)$ is given by the number of elements in $P$.
\item The volume of $\mathcal{O}(P)$ can be computed from the number of linear extensions of $P$.
\item The vertices of $\mathcal{O}(P)$ are exactly the indicator vectors of order ideals of $P$.
\end{enumerate}

In this paper, we will be focusing on order polytopes for certain heap posets.


\section{$c$-singletons}
\label{sec.cbirkhoff}


% In this section, we review $c$-sorting words and $c$-sortable elements, which were introduced in~\cite{reading07-clusters-paper4}, and $c$-singletons, which were introduced in \cite{HLT11}. 

\subsection{$c$-sorting words and $c$-sortable permutations}

In this section, we review $c$-sorting words and $c$-sortable elements, which were introduced in~\cite{reading07-clusters-paper4}. 
Given a Coxeter element $c$ and reduced word $\rw{a_1 a_2 \dots a_n}$, define an infinite word
\[
c^{\infty} \coloneqq a_1 a_2 \dots a_n \mid a_1 a_2 \dots a_n\mid \cdots
\]
consisting of repeated copies of the given reduced word for $c$. 
The symbols "$\mid$" are "dividers" which facilitate the definition of sortable elements. 
The $c$-sorting word of $w\in A_n$ is 
the lexicographically first (as a sequence of positions in $c^\infty$) subword of $c^\infty$ that is a reduced word for $w$. 
We denote this word by $\sort(w)$. 

% Given a Coxeter element $c$ and reduced expression $s_{i_1}\cdots s_{i_n}$, define an infinite word
% \[
% c^{\infty} := s_{i_1}\cdots s_{i_n} \mid s_{i_1}\cdots s_{i_n}\mid \cdots
% \]
% consisting of repeated copies of the given reduced expression for $c$.
% The $c$-sorting word of $w\in A_n$ is the lexicographically left-most reduced expression for $w$ which appears as a subword of $c^{\infty}$.


% Section 5 of the survey chapter \cite{ReadingBeyond} describes the following useful algorithm to find the $c$-sorting word of a permutation.


% \begin{algorithm}[Finding the $c$-sorting word] 
% Fix a Coxeter element $c \in A_n$ with reduced word $\rw{a_1 a_2 \dots a_n}$. 
% Let $w \in A_n$ with length $\ell \coloneqq \ell(w)$.
% \emily{This algorithm doesn't need to be in FPSAC paper. But put in big paper.}

% \begin{enumerate}
% \item If $w$ is the identity, then the only reduced word for $w$ is the empty word. Otherwise, we write down a reduced word $\rw{u_1 \dots u_\ell}$ as follows.  

% \item First, try each $a_1, a_2, \dots, a_n$ (in this order) until we find one $a_i$ such that $\ell(\rw{a_i} w) < \ell(w)$. Set $u_1 \coloneqq a_i$, and write $w'=\rw{a_i} w$. \esther{the usage of brackets is confusing to me}

% \item If $w'$ is the identity, then $\ell=1$ and $\rw{u_1}$ is the desired $c$-sorting word. 
% Otherwise, try each of $a_{i+1}, \dots, a_n, a_1,\dots, a_i$ (in this order) until we find one $a_i'$ such that 
% $\ell(\rw{a_i'} w') < \ell(w')$. Set $u_2 \coloneqq a_i'$, and define $w"=\rw{u_2}w'$. 

% \item If $w"$ is the identity, then $\ell=2$ and $\rw{u_1 u_2}$ is the desired $c$-sorting word. 
% Otherwise, continuing in this manner, we eventually find a reduced word $\rw{u_1 \dots u_\ell}$ for $w$.  
% This reduced word is the $c$-sorting word 
% $\sort(w)$ 
% for $w$.
% \end{enumerate}
% \end{algorithm}

% \begin{example}
% Let $W = A_4$ and $c = s_1 s_2 s_3 s_4$ our Coxeter element.
% Then 
% \[
% c^{\infty} = s_1 s_2 s_3 s_4 \mid s_1 s_2 s_3 s_4 \mid \cdots
% \]
% The $c$-sorting word of the permutation $42351$ is $s_1 s_2 s_3 s_4 s_2 s_1$.
% Note that $s_1 s_2 s_3 s_2 s_1 s_4$ is a lexicographically-smaller reduced expression for $w$ (with respect to the order $s_1<s_2<s_3<s_4$), but it is not the $c$-sorting word, since it is not leftmost in $c^{\infty}$.
% There is a sense in which the $c$-sorting word is lexicographically minimal: as positions in $c^{\infty}$.
% \end{example}

We say that the identity permutation is \emph{$c$-sortable}. 
If $w$ is not the identity permutation, 
we can think of $\sort(w)$ as a sequence of nonempty subsets of $\{a_1, \ldots, a_n\}$. The subsets $K_1, K_2, \dots,K_p$ in this sequence are the sets of letters of $c$ that occur between two adjacent dividers, so we have $x \in K_j$ if $x$ is in the $j$th copy of $c$ inside $c^\infty$. 
We say that a permutation $w$ is \emph{$c$-sortable} if $K_1 \supseteq K_2 \supseteq \cdots \supseteq K_p$. 
The set of $c$-sortable permutations does not depend on the choice of reduced word for $c$.  
% We say that $w$ is \emph{$c$-sortable} if  $\sort(w)$ yields a nested sequence of sets, i.e. $K_1 \supseteq K_2 \supseteq \cdots \supseteq K_p$. 


\begin{example}
Consider the Coxeter element $c = s_1 s_2 s_3 s_4=\rw{1234}$  of $A_4$. 
Then the $c$-sorting word of the permutation $42351$ is 
$\rw{1 2 3 4 \mid  2 \mid 1}$. 
%$s_1 s_2 s_3 s_4 | s_2 | s_1$, 
Our subsets are $K_1 = \{1,2,3,4\}$, $K_2 = \{2\}$, and $K_3 = \{1\}$.  Since $K_2\not\supseteq  K_3$, these sets do not form a nested sequence and therefore $42351$ is not $c$-sortable.
On the other hand, the permutation $43215$ has $c$-sorting word $\rw{123 \mid 12 \mid 1}$ and is $c$-sortable. 
% the permutation $3214$ has $c$-sorting word $\rw{1 2 \mid 1}$ 
%$s_1 s_2 | s_1$ and is $c$-sortable.
\end{example}



Reading showed in~\cite{Reading07-paper5} that 
the restriction of the right weak order to $c$-sortable elements is a lattice which is isomorphic to an important quotient of the right weak order called the $c$-Cambrian lattice~\cite{Rea06}.  
For the Coxeter element $c=s_1 s_2 \dots s_n$, the $c$-sortable elements form the Tamari lattice. For this reason, we refer to this Coxeter element as the "Tamari" Coxeter element of $A_n$. 
Cambrian lattices and $c$-sortable elements  have strong connections
to cluster algebras, representation theory, and many areas of combinatorics, and they are widely studied.  % both to noncrossing partitions 
We will be interested in a subclass of $c$-sortable elements, called $c$-singletons, which we describe next. 

\subsection{$c$-singleton permutations}
% \subsection{Heap for $c$-sorting word of $w_0$} 
% \subsection{$c$-singletons and their heaps} 


% In \cite{HLT11}, Hohlweg, Lange, and Thomas introduced an important subclass of $c$-sortable elements called $c$-singletons. 

There is an order-preserving projection $\pidown^c: A_n\to A_n$ which sends an element $w$ to the largest $c$-sortable element that is weakly below $w$ in the right weak order~\cite[Proposition 3.2]{Reading07-paper5}. 
% Let $\pidown^c:W\to W$ be the map which sends an element $x$ to the largest $c$-sortable element that is below it (possibly itself) in the right weak order. 
% See Figure~\ref{fig:CambrianlatticeA2}.
% Observe that an element $x$ is $c$-sortable if and only if $\pidown^c(x)=x$.
% In~\cite{Rea06}, Reading defines the map $\pidown^c: A_n\to A_n$ which sends an element $w$ to the largest $c$-sortable element that is below $w$ in the right weak order. 
In \cite{HLT11}, Hohlweg, Lange, and Thomas used this map to introduce an important subclass of $c$-sortable elements:  
A $c$-sortable $w$ is called a 
\emph{$c$-singleton} if the preimage of $\{ w\}$ under $\pidown^c$
is the singleton $\{ w\}$ itself. 
We will use the following characterization of $c$-singletons. %given by Hohlweg--Lange--Thomas.
\label{sec: def of c-singletons}
\begin{thm}[{{\cite[Theorem 2.2]{HLT11}}}]\label{thm:c-sing-prefix}
A permutation $w$ is a $c$-singleton 
if and only if some reduced word of $w$ is a prefix of a word in the commutation class of $\sort(w_0)$, the $c$-sorting word of the longest permutation $w_0$.
\end{thm}

% \subsection{Heap for $c$-sorting word of $w_0$} \label{sec:heap for w0}
% Order polytope of Heap for $c$-sorting word of $w_0$

% In light of this fact, we will be primarily interested in $\heap(q)$ where $q$ is the $c$-sorting word of the longest permutation $w_0\in W$, which we denote by $\heap(\sort(w_0))$. 

%Since the commutation class of $\sort(w_0)$ can be obtained from the heap of $\sort(w_0)$, we will be very interested in this heap and give a description of it in Section \ref{sec:heap}. 
% In light of this fact, we will be very interested in the heap $\heap(\sort(w_0))$ of the $c$-sorting word of the longest permutation $w_0$. We will describe this heap in 
%Let $J(\heap(\sort(w_0)))$ denote the %(distributive) lattice of order ideals of %the poset 
%$\heap(\sort(w_0))$. 
% Let $J(P)$ denote the lattice of order ideals of a poset $P$, so, in particular, $J(\heap(\sort(w_0)))$ denotes the lattice of order ideals of the poset $\heap(\sort(w_0))$. 
The set of $c$-singletons form a distributive sublattice of the right weak order due to \cite[Proposition 2.5]{HLT11}. We denote this lattice by $\LatticeC$. 
By \cite[Proposition 3]{LL20}, $\LatticeC$ is isomorphic to the lattice of order ideals of $\heap(\sort(w_0))$, which we denote by $J(\heap(\sort(w_0)))$. 
% \emily{Maybe say: In this section, let $H\coloneqq \heap(\sort(w_0))$ denote the heap of ....}\sunita{I think it's fine as is without the extra notation}

% Furthermore, \cite[Proposition 2.7]{HLT11} tells us that, if $w$ is a $c$-singleton, then any prefix of $\sort{w}$ up to commutations is also a $c$-singleton.

% \begin{lem}
% Let $\rw{u}$ be a prefix of a reduced word in the commutation class of $\sort(w_0)$ and set $w=\rw{u}$.  
% Then $\heap(\rw{u})$ is an order ideal of $\heap(\sort(w_0))$.  
% Furthermore, 
% the $c$-sorting word of $w$ is in the same commutation class as $\rw{u}$. 
% In particular, $\heap(\sort(w))$ is equal to $\heap(\rw{u})$, and so $\heap(\sort(w))$ is an order ideal of $\heap(\sort(w_0))$. 
% \emily{Maybe this should be a remark because it's long}
% \end{lem}


% In other words, let $I$ be an order ideal of $\heap(\sort(w_0))$, 
% \emily{I think \cite[Prop 3]{LL20} proves this, but I think they didn't prove the part about c-sorting word of w} 


\begin{proposition}\label{prop:vertex-bijection}
The following map is a poset isomorphism
\begin{align*}
    f: 
    \LatticeC 
    %\{c-\text{singletons}\} 
    & \to J(\heap(\sort(w_0)))\\
    w & \mapsto \heap(\sort(w))
\end{align*}
% where we obtain the partial order on $c$-singletons by restricting the weak order on $A_n$ to the set of $c$-singletons.
between the $c$-singletons and the order ideals of the heap poset $\heap(\sort(w_0))$.  
\end{proposition}


As we noted in Section \ref{sec:order polytope}, the vertices of the order polytope $\ord(P)$ of a poset $P$ correspond to the order ideals of $P$.
As a consequence, the $c$-singletons are in bijection with the vertices of $\ord(\heap(\sort(w_0)))$. 




\section{
$c$-Birkhoff polytopes
}


The \emph{Birkhoff polytope} 
is the convex hull of all permutation matrices.
Davis and Sagan~\cite{DS18} studied a 
"pattern-avoiding" subpolytope 
of the Birkhoff polytope
whose vertices correspond to the permutations avoiding the pattern $132$ and $312$.
As noted in \cite[Remark 3.6]{DS18}, 
for the "Tamari" Coxeter element $c=s_1 s_2 \dots s_n$, 
the $c$-singletons are precisely the permutations which avoid these same patterns 
$132$ and $312$. 


% \jianping{Point out that corresponds to the Tamari case}

\subsection{A pattern-avoidance criterion for $c$-singletons}\label{sec:definition of c-birkhoff polytope}

There is a similar classification of $c$-singletons for other $c$ (see Proposition~\ref{prop:pattern avoidance characterization type A}). 
In this section, we generalize Davis and Sagan's pattern-avoiding  polytope coming from the "Tamari" Coxeter element $c$ 
to all Coxeter elements $c$ in $A_n$.



Let $c$ be a Coxeter element in $A_n$. 
There is exactly one commutation class for $c$, so every reduced word for $c$ has the same heap.  By abuse of notation we write $\heap(c)$ to denote this heap.  Then
$\heap(c)$ is the partial order 
on $\{1,\dots,n\}$ obtained via the transitive closure of the cover relations 
% \[
% \text{
% $i \prec i+1$ if $i$ appears to the left of $i+1$ in every reduced word of $w$}\]
% \[
% \text{new 
% $j-1=i \prec j=i+1$ if $j-1=i$ appears to the left of $j=i+1$ in every reduced word of $w$}
% \]
% \begin{center}
$i-1 \prec i$ %~~
if $i-1$ appears to the left of $i$ in every reduced word of $c$, and
 % \] 
% \[
% \text{
% $i \succ i+1$ otherwise.}
% \]
 % \[
% \text{  
$i-1 \succ i$ otherwise. %}
% \end{center}




\begin{figure}[htb!]
\centering
\begin{tikzpicture}[xscale=1,yscale=0.9,>=latex]
\def\posetedgecolor{blue}
\def\posetedgenegativeslope{red}
\node(1) at (1,0) {$1$}; 
\node(2) at (2,1) {$2$}; 
\node(3) at (3,0) {$3$}; 
\node(4) at (4,-1) {$4$};  
\node(5) at (5,0) {$5$};  
\node(6) at (6,-1) {$6$}; 
\node(7) at (7,0) {$7$}; 
% \node(8) at (8,2) {$8$}; 


\draw[-] (1) -- (2) node[pos=0.3,right=3pt]{\color{blue}{$\underline{2}$}};  
\draw[-] (2) -- (3) node[pos=0.3,right=3pt]{\color{red}{$\overline{3}$}}; 
\draw[-] (3) -- (4) node[pos=0.3,right=3pt]{\color{red}{$\overline{4}$}}; 
\draw[-] (4) -- (5) node[pos=0.3,right=3pt]{\color{blue}{$\underline{5}$}};  
\draw[-] (5) -- (6)node[pos=0.3,right=3pt]{\color{red}{$\overline{6}$}}; 
\draw[-] (6) -- (7) node[pos=0.3,right=3pt]{\color{blue}{$\underline{7}$}}; 
% \draw[-] (7) -- (8) node[pos=0.3,right=3pt]{\color{red}{$\overline{8}$}}; 

\end{tikzpicture}
\caption{The heap diagram for the Coxeter element $c = s_1s_4s_3s_2s_6s_5s_7$ which corresponds to lower-barred numbers %$\underline{p_1}, \underline{p_2}, \underline{p_3} = 
{\color{blue}$\underline{2}$}, 
{\color{blue}$\underline{5}$}, 
{\color{blue}$\underline{7}$} and
upper-barred numbers 
% $\overline{q_1} , \overline{q_2}, \overline{q_3}$ = 
{\color{red}$\overline{3}$}, 
{\color{red}$\overline{4}$},
{\color{red}$\overline{6}$}. 
}
\label{fig:heap for reduced word 1432657}
\end{figure}
% \emily{If need to reduce page, change example to the A7 or A4 that is the same as another example}

% \jianping{Do we need the heap for $c$ specifically? Would it be enough to have the upper and lower barred numbers?}\emily{For the big paper we should, to be used to explain shape of big heap later. For FPSAC paper it's not necessary.}

As described in \cite[Chapter 6]{Rea06}, we partition the integers in $[2,n]$ into lower-barred and upper-barred numbers $\underline{[2,n]}$ and $\overline{[2,n]}$, respectively. 
If $i-1 \prec i$, define $i$ to be a lower-barred number $\underline{i}\in \underline{[2,n]}$;
If $i-1 \succ i$, define $i$ to be a upper-barred number $\overline{i}\in \overline{[2,n]}$. For example, see Figure \ref{fig:heap for reduced word 1432657}.
%\esther{should we be consistent w before, where we use $i$ and $i+1$?} \emily{Previous description was changed}


We say that a permutation $w$
avoids the pattern $31\underline{2}$ if $w$ contains no $312$-pattern such that the last entry "2" in the pattern is a lower-barred number. 
Similarly, a permutation $w$
avoids the pattern $\overline{2}31$ if the one-line notation $w$ contains no $231$-pattern such that the first entry "2" in the pattern is an upper-barred number.



The following result of \cite[Proposition 5.7]{Rea06} characterizes 
$c$-sortable and $c$-singleton permutations using pattern-avoidance.

\begin{proposition}\label{prop:pattern avoidance characterization type A}
% Let $c$ be a Coxeter element in $A_n$. 
A permutation $w \in A_n$ is $c$-sortable if and only if the one-line notation of $w$ avoids the patterns $31\underline{2}$
and 
$\overline{2}31$. 
Furthermore, 
a $c$-sortable permutation $w$ is a $c$-singleton if and only if $w$ avoids the patterns $13\underline{2}$
and 
$\overline{2}13$. 
\end{proposition}

\begin{definition}
For a Coxeter element $c$ in $A_n$, we define the \emph{$c$-singleton Birkhoff polytope}, or \emph{$c$-Birkhoff polytope} for short, to be the convex hull of the permutation matrices corresponding to the $c$-singletons, that is, the permutations avoiding the four patterns listed in Proposition~\ref{prop:pattern avoidance characterization type A}.   We denote the $c$-Birkhoff polytope as $\bir(c)$.
\end{definition}

Note that our convention is that 
the permutation matrix of the 
permutation $w=w(1)\dots w(n+1)$ has 1's in entries $(i,w(i))$.

% Remark 3.6. We would like to note a connection between permutations avoiding {132, 312} and the world of polytopes. The permutations of Avn(132,312) can be considered as elements of a type-A Coxeter group. Thought of in this way, the elements of Avn(132,312) are an example of c -singletons (where c = s1 s2 s3 ), that is, their inverses form vertices of both the permutohedron and Loday’s realization of the associahedron; see [23,20]. It would be interesting to define pattern- avoiding polytopes for other Coxeter groups and see if there is any relationship with the corresponding c -singletons.

\begin{remark}\label{rem:remark of Davis and Sagan}
Davis and Sagan suggested in~\cite[Remark 3.6]{DS18} that it would be interesting to define pattern-avoiding polytopes for other Coxeter groups. 
Theorem 4.12 of \cite{reading07-clusters-paper4}
characterizes type $B$ and $D$ $c$-sortable elements as signed permutations satisfying certain pattern avoidance conditions. 
This can be used to give us an analog of Proposition~\ref{prop:pattern avoidance characterization type A} for type $B$ and $D$ $c$-singletons. 
\end{remark}

\subsection{Relations for $c$-Birkhoff polytopes}


The classical Birkhoff polytope of $A_n$ lives in a $(n+1)^2$-dimensional ambient space. Since each of its row and column sum up to one, it is a $n^2$-dimensional polytope.
The row and column relations for the classical Birkhoff polytope also hold in the $c$-Birkhoff polytope, 
since the vertices still come from permutation matrices. Our goal in this section is to exhibit ${n \choose 2}$ additional relations which any point in $\bir(c)$ satisfies, 
so that it is in fact an ${n+1 \choose 2}$-dimensional polytope. 

From the pattern avoidance criteria in Proposition \ref{prop:pattern avoidance characterization type A}, we see that if $w$ is a $c$-singleton and $i \in \underline{[2,n]}$, all numbers less than $i$ or all numbers greater than $i$ must appear after $i$ in the one-line notation $w$ and similarly for upper-barred numbers. 
In particular, if $m = \max(i+1,n-i+2)$, then $i$ cannot appear in any of the last $m$ spots of $w$.



We will consider points in $\bir(c)$ as matrices $(x_{i,j})$ for $1 \leq i,j \leq n+1$.
\begin{proposition}\label{prop:zeroes}
Let $c$ %$c = a_1 \cdots a_{n}$ 
be a Coxeter element in $A_{n}$, and let $(x_{i,j})$ be a point in the $c$-Birkhoff polytope. For $2 \leq i \leq n$, if $i \in \underline{[2,n]}$ and $m = \max(i+1,n+2-i)$, we have 
\[x_{m,i} = x_{m+1,i} = \cdots = x_{n+1,i} = 0.\]
Otherwise, $i \in \overline{[2,n]}$ and if $r = \min(i-1,n+2-i)$, then 
\[x_{1,i} = x_{2,i} = \cdots = x_{r,i} = 0.\]
\end{proposition}

 Using the pattern avoidance repeatedly puts restrictions on which numbers can appear together in the first $u$ spots of a $c$-singleton for some values of $u$.

\begin{thm}\label{thm:SummingRelations}
Let $c$ be a Coxeter element in $A_n$. 
For each
$1 \leq i \leq \frac{n-1}{2}$ and  $i+1 \leq u \leq n-i$, 
there exists a sequence $i = v_0 < v_1 < \cdots < v_d$, where $d \geq 1$, such that 
\[
\sum_{j=0}^d \sum_{i=1}^u x_{i,v_j}
\]
is equal to either $1$ or $d$ (depending on $i$ and $u$) 
for all points 
in the $c$-Birkhoff polytope. 
\end{thm}
\begin{example}
Let $c = s_1s_2s_4s_3$.  
Then the $c$-Birkhoff polytope 
has $\binom{4}{2}=6$ additional relations. 
Proposition \ref{prop:zeroes} gives us four relations 
\[x_{5,2} = x_{4,3} = x_{5,3} = x_{1,4} = 0.\]
% From Proposition \ref{prop:zeroes}, we have that $x_{5,2} = x_{4,3} = x_{5,3} = x_{1,4} = 0$. 
Theorem \ref{thm:SummingRelations} gives us two more relations.
For $i = 1$, $u = 2$, the sequence is $v_0 = 1, v_1 = 3, v_2 = 4$, and we have the relation  %$\displaystyle \sum_{j=0}^2 \sum_{i=1}^2 x_{i,v_j} = 1$. 
\[ \sum_{j=0}^2 \sum_{i=1}^2 x_{i,v_j}= \sum_{j \in \{1,3,4\}} \sum_{i=1}^2 x_{i,j} 
= x_{1,1} + x_{2,1} + x_{1,3} + x_{2,3} + x_{1,4} + x_{2,4} =1.\]
% For $i = 1$, $u = 3$, the sequence is $(1,5)$ and the corresponding sum will again be 1:
For $i = 1$, $u = 3$, the sequence is $v_0=1$, $v_1=5$ and we have the relation 
\[
\sum_{j=0}^1 \sum_{i=1}^3 x_{i,v_j}= \sum_{j \in \{1,5\}} \sum_{i=1}^3  x_{i,j} 
= 
x_{1,1} + x_{2,1} + x_{3,1} + x_{1,5} + x_{2,5} + x_{3,5} = 1.\]
% Thm 4.4, $i = 1, u = 2$, 
% $i=1$ and $u=3$
% % Thm 4.4, $i = 1, u = 3$, 
% \[x_{1,1} + x_{2,1} + x_{3,1} + x_{1,5} + x_{2,5} + x_{3,5} = 1\]

% From Theorem \ref{thm:SummingRelations}, for $i = 1$ and $u = 2$, the sequence is $v_0 = 1, v_1 = 3, v_2 = 4$, and we have $\displaystyle \sum_{j=0}^2 \sum_{i=1}^2 x_{i,v_j} = 1$. 
% For $i = 1$ and $u = 3$, the sequence is $(1,5)$ and the corresponding sum will again be 1. 
% In general, these sums will be 1 or $d$ where the sequence has length $d+1$.

% \begin{itemize}
% \item Proposition \ref{prop:zeroes} gives us four relations $x_{5,2} = x_{4,3} = x_{5,3} = x_{1,4} = 0$
% \item Thm 4.4, $i = 1, u = 2$, $\sum_{j \in \{1,3,4\}} \sum_{i=1}^2 x_{i,j} = x_{1,1} + x_{2,1} + x_{1,3} + x_{2,3} + x_{1,4} + x_{2,4} =1$.
%     \item Thm 4.4, $i = 1, u = 3$, $x_{1,1} + x_{2,1} + x_{3,1} + x_{1,5} + x_{2,5} + x_{3,5} = 1$
% \end{itemize}
\end{example}

%\esther{note just for us} Lets consider how many relations we would want to find. The ordinary Birkhoff polytope, which only satisfies the row and column relations, lives in $n^2 - (2n-1) = (n-1)^2$ dimensional space. We hope that the $c$-birkhoff polytope lives in ${n\choose 2}$-dimensional space. Therefore, we hope to find $(n-1)^2 - {n \choose 2} = {n-1 \choose 2}$ linearly-independent relations which any point of the $c$-Birkhoff polytope satisfies. The zero-relations provide $(n-2) + (n-4) + \cdots$ such relations, so we hope to find $(n-3) + (n-5) + \cdots$ linearly-independent admissible sequences. (These numbers are \cite[A002620]{oeis}). 

% \section{A unimodular equivalence}
\section{$\bir(c)$ and $\mathcal{O}(\heap(\sort(w_0)))$}

\label{sec.unimodular}

In this section, we will prove $\bir(c)$ is unimodularly equivalent to the order polytope $\mathcal{O}(\heap(\sort(w_0)))$. We will achieve this by first explicitly constructing a lattice-preserving projection $\Pi_c$ on $\bir(c)$, and then show the existence of a unimodular transformation $\mathcal{U}_c$.

\subsection{A lattice-preserving projection}

Let $c$ be a Coxeter element of $A_n$. % Note: Pi_c is projection from height-($(n+1)(n+1)$)-vectors to height-$\binom{n+1}{2}$ vectors. Pi_c is a projection map from a point (not necessarily a vertex) in c-Birk and sends it to a point in the order polytope. Pi_c is lattice-preserving for the vertices of c-Birk. Neither polytopes have interior lattice points, so Pi_c is lattice-preserving (that is, "good projection")
We define a projection $\Pi_c$ on $(n+1)\times (n+1)$-matrices which reads $\binom{n+1}{2}$ of the entries in a specific order.
We describe the reverse order by reading entries in the matrix.
% , which we will denote by $\Pi'_c$.

Let $1< \underline{p_1}< \dots < \underline{p_r} <n+1$ be the set of lower-barred numbers  
and $\overline{q_1} < \dots \overline{q_s} < n+1$ be the set of upper-barred numbers for $c$. 
% Let $P=\{p_1,\dots,p_r\}$.
Let $\sigma$ be the permutation 
$(n+1) \, {p_r} \, {p_{r-1}} \dots \, {p_1} \, 1 \, {q_1} {q_2} \,\dots \, {q_s}$ written in one-line notation. 
% $n+1,p_r,p_{r-1},\dots,p_1,1,q_1,q_2,\dots,q_s$. 
%(We will now read entries in ... of $\sigma$) 
The first entries  we will read are 
% all elements in columns indexed by $P\cup\{n+1\}$ that lie strictly above the main diagonal, column-by-column, left-to-right, and from bottom to top. That is,
\begin{align*}
&({p_1}-1 , {p_1}), ({p_1} - 2 , {p_1}), \dots, (1, {p_1}),\\
    % &(p_2-1,p_2), (p_2-2,p_2), \dots, (1,p_2),\\
& \dots \\
    &({p_r}-1,{p_r}), ({p_r} - 2 , {p_r}), \dots, (1, {p_r}), \\
    & (n,n+1), (n-1,n+1), \dots, (1,n+1).
\end{align*}
% We read all the elements in column $p_1$ from bottom to top, the elements in column $p_2$ from bottom to top, and so on through column $p_r$ and finally column $n+1$.  
The remaining entries come from ${q_s}, \dots, {q_1}$. For each ${q_i}$,  take ${q_i}-1$ entries as follows:
\begin{itemize}
\item Let $m=\min({q_i} - 1, n+1- {q_i})$.   Let $\sigma^i_1,\sigma^i_2, \dots, \sigma^i_m $ be the $m$ numbers of $\sigma$ (in one-line notation) immediately before ${q_i}$, from right to left.
\item First take the $m$ entries $(n+1,\sigma_1^i), (n,\sigma_2^i), \dots, (n+2-m, \sigma^m_i)$.
% The first element of $\Pi'(x)$ that we get from $q_i$ is the $n+1$\textsuperscript{st} element of column $\sigma^i_1$.  The next element is the $n$\textsuperscript{th} element of column $\sigma^i_2$.  Then we have the $n-1$\textsuperscript{st} element of column $\sigma^i_3$ and we repeat this until we have taken the $n+2-m$\textsuperscript{th} element of column $\sigma^i_m$.
\item  Then take the
additional ${q_i} - 1 - m$ entries 
% from column $q_i$
 $({q_i} -1 , {q_i}), ({q_i} - 2, {q_i}), \dots, (m+1, {q_i})$. 
% Note that when $m = q_i-1$, this sequence is empty.

% get from $q_i$ are the entries in column $q_i$ in rows $n-q_i+1$ through $q_i-1$, reading bottom to top.
\end{itemize}

\begin{example}\label{eg.proj}
Let $c = s_1s_4s_3s_2s_6s_5s_7$ be the Coxeter element whose Heap diagram and corresponding upper- and lower-barred numbers are illustrated in 
Figure \ref{fig:heap for reduced word 1432657}. Then $\underline{p_1}, \underline{p_2}, \underline{p_3} = \underline{2}, \underline{5}, \underline{7}$ and $\overline{q_1} , \overline{q_2}, \overline{q_3} = \overline{3}, \overline{4}, \overline{6}$. 
We have $\sigma = 87521346$. We compute the projection $\Pi_c$ in Figure~\ref{fig.proj} (left).

\smallskip

\begin{figure}[h]
\begin{minipage}{0.45\textwidth}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
  & $28$ & $\X$  & $\X$ & $24$ & $\X$ & $18$ & $11$ \\ \hline
  &    & $\X$  & $\X$ & $25$ & $\X$ & $19$ & $12$ \\ \hline
  &    &    & $\X$ & $26$ & $6$ & $20$ & $13$ \\ \hline
  &    &    &   & $27$ & $7$ & $21$ & $14$ \\ \hline
  &    &    &   &    & $8$ & $22$ & $15$ \\ \hline
  & $3$  &    &   &  $\X$  &   & $23$ & $16$ \\ \hline
$4$ & $1$  & $9$ &   &  $\X$  &   &    & $17$ \\ \hline
$2$ & $\X$  & $5$  & $10$ &  $\X$  &   & $\X$   &    \\ \hline
\end{tabular}
\end{minipage}\hfill
\begin{minipage}{0.45\textwidth}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$0$ & $\Circled{1}$ & $0$ & $0$ & $\Circled{0}$ & $0$ & $\Circled{0}$ & $\Circled{0}$\\ \hline
$0$ & $0$ & $0$ & $0$ & $\Circled{1}$ & $0$ & $\Circled{0}$ & $\Circled{0}$ \\ \hline
$1$ & $0$ & $0$ & $0$ & $\Circled{0}$ & $\Circled{0}$ & $\Circled{0}$ & $\Circled{0}$ \\ \hline
$0$ & $0$ & $1$ & $0$ & $\Circled{0}$ & $\Circled{0}$& $\Circled{0}$ & $\Circled{0}$ \\ \hline
$0$ & $0$ & $0$ & $1$ & $0$ & $\Circled{0}$ & $\Circled{0}$ & $\Circled{0}$ \\ \hline
$0$ & $\Circled{0}$ & $0$ & $0$ & $0$ & $1$ & $\Circled{0}$ & $\Circled{0}$\\ \hline
$\Circled{0}$ & $\Circled{0}$ & $\Circled{0}$& $0$ & $0$ & $0$ & $1$ & $\Circled{0}$\\ \hline
$\Circled{0}$ & $0$ & $\Circled{0}$ & $\Circled{0}$ & $0$ & $0$ & $0$ & $1$ \\ \hline
\end{tabular}
\end{minipage}
\caption{Left: The projection $\Pi_c$ of Example \ref{eg.proj}. Right: permutation matrix for $b_4$ of Example~\ref{eg.basis}.}\label{fig.proj}
\end{figure}

\end{example}

\begin{thm}\label{thm.lattice}
$\Pi_c$ is a lattice-preserving projection on the $c$-Birkhoff polytope.
\end{thm} 




% \subsection{A basis for the $c$-Birkhoff Polytope}
% \subsection{A linear extension and a basis}
% \subsection{A lexicographically first linear extension and a basis} 
\subsection{A diagonal reading word} \label{sec:heap}
% \sunita{This now contains more than what the title says  - could we call this subsection Main Result or something along those  lines?}\emily{we made changes}

% \emily{I think it's easier to describe version 1, so I describe version 1}
 % - shape of the heap [Emily will write a description, version 2] \emily{I should write this in Section \ref{sec:heap for w0}?}\jianping{It makes sense to put it there.}


Let $c$ be a Coxeter element of $A_n$
%A line segment of slope $-1$ is called a \emph{diagonal}, and a line segment of slope $1$ is called an \emph{antidiagonal}.  
% \sunita{We'll need this description in the full paper, but I don't think we need it here?  Also  if we do want it, then shouldn't it really  be a theorem/lemma since we've already  given a definition of $H$?}
% square grid with diagonal lines of slope $1$ and $-1$
% Diagonal reading word like row reading word and column reading word of a tableau
and let $\mathcal{R}_c$ denote the
labeled linear extension of $\heap(\sort(w_0))$ which is lexicographically first, in the sense of lexicographic order on heap labels.  Observe that $\mathcal{R}_c$ is the 
% "diagonal reading word" 
word formed by concatenating the diagonals of $\heap(\sort(w_0))$ from left to right; within each diagonal, read from southeast to northwest. 
For this reason, we refer to the reduced word $\mathcal{R}_c$ as the \emph{diagonal reading word} of $\heap(\sort(w_0))$.


\def\myscale{.61}
\begin{figure}[htb]
\centering
\begin{tikzpicture}[scale=\myscale]
\filldraw [yellow!20]
(6+.4,14+.4) -- (3,11+.4) -- (2,12+.4) -- (1,11+.4) --
(0-.4,12+.4) --(0-.4,8-.4) -- 
(3,5-.4) -- (4,6-.4) -- 
(5,5-.4) -- (6+.2,6-.4) -- 
(6+.4,14+.4) ; 

\draw [black!40, 
%very 
thin, 
] (0,0) -- (6,6)
(0,2) -- (6, 6+2)
(0,4) -- (6-2, 6+4-2)
(0,6) -- (6-2, 6+6-2)
(0,8) -- (6-2, 8+6-2)
;

\draw [black!40, 
%very 
thin, 
] (0,2) -- (1,1)
(0,2+2) -- (2,2)
(0,2+4) -- (3,3)
(0,2+6) -- (4,4)
(0,4) -- (6, 6+4)
(0,6) -- (6, 6+6)
(0,8) -- (6, 8+6)
(0,10) -- (4, 8+6)
(0,12) -- (2, 14)
;

\draw [black!40, 
%very 
thin, 
] 
(0,10) -- (5,5)
(0,12) -- (6,6)
(0,14) -- (6,8)
(2,14) -- (6,10)
(4,14) -- (6,12)
;

% First, locate each of the nodes and name them
\node[gray] (s1r1) at (0,0) {11}; %{$s_1 l 1$};
% \node (s3r1) at (2,0) {none}; %{$s_3 l 1$};
% \node (s5r1) at (4,0) {none}; %{$s_5 l 1$};
% \node (s7r1) at (6,0) {none}; %{$s_7 l 1$};
\node[gray] (s2r2) at (1,1) {21}; %{$s_2 l 2$};
% \node (s4r2) at (3,1) {none}; %{$s_4 l 2$};
% \node (s6r2) at (5,1) {none}; %{$s_6 l 2$};

\node[gray] (s1r3) at (0,2) {12}; %{$s_1 l 3$};
\node[gray] (s3r3) at (2,2) {31}; %{$s_3 l 3$};
% \node (s5r3) at (4,2) {none}; %{$s_5 l 3$};
% \node (s7r3) at (6,2) {none}; %{$s_7 l 3$};
\node[gray] (22) %(s2r4) 
at (1,3) {22}; %{$s_2 l 4$};
\node[gray] (41) %(s4r4) 
at (3,3) {41}; %{$s_4 l 4$};
% \node (s6r4) at (5,3) {none}; %{$s_6 l 4$};

\node[gray] (13) %(s1r5) 
at (0,2+2) {13}; %{$s_1 l 5$};
\node[gray] (32) %(s3r5) 
at (2,2+2) {32}; %{$s_3 l 5$};
\node[gray] (51) %(s5r5) 
at (4,2+2) {51}; %{$s_5 l 5$};
% \node (s7r5) at (6,2+2) {non}; %{$s_7 l 5$};
\node[gray] (23) %(s2r6) 
at (1,3+2) {23}; %{$s_2 l 6$};
\node (42) %(s4r6) 
at (3,3+2) {\circled{42}}; %{$s_4 l 6$};
\node (61) %(s6r6) 
at (5,3+2) {\circled{61}}; %{$s_6 l 6$};

\node[gray] (14) %(s1r7) 
at (0,2+4) {14}; %{$s_1 l 7$};
\node (33) %(s3r7) 
at (2,2+4) {\circled{33}}; %{$s_3 l 7$};
\node (52) %(s5r7) 
at (4,2+4) {\circled{52}}; %{$s_5 l 7$};
\node (71) %(s7r7) 
at (6,2+4) {\circled{71}}; %{\starred{\circled{71}}};%{$\circled{71}$}; %{$s_7 l 7$};
\node (24) %(s2r8) 
at (1,3+2+2) {\circled{24}}; %{$s_2 l 8$};
\node (43) %(s4r8) 
at (3,3+2+2) {43}; %{$s_4 l 8$};
\node (62) %(s6r8) 
at (5,3+2+2) {\starred{62}}; %{68}; %{$s_6 l 8$};

\node (15) %(s1r9) 
at (0,2+4+2) {\circled{15}}; %{$s_1 l 7$};
\node (34) %(s3r9) 
at (2,2+4+2) {34}; %{$s_3 l 7$};
\node (53) %(s5r9) 
at (4,2+4+2) {\starred{53}}; %{$s_5 l 7$};
\node (72) %(s7r9) 
at (6,2+4+2) {\rectangled{72}}; %{$s_7 l 7$};
\node (25) %(s2r10) 
at (1,3+2+2+2) {25}; %{$s_2 l 8$};
\node (44) %(s4r10) 
at (3,3+2+2+2) {\starred{44}}; %{$s_4 l 8$};
\node (63) %(s6r10) 
at (5,3+2+2+2) {\rectangled{63}}; %{68}; %{$s_6 l 8$};

\node (16) %(s1r11) 
at (0,2+4+2+2) {16}; 
\node (35) %(s3r11) 
at (2,2+4+2+2) {\starred{35}}; 
\node (54) %(s5r11) 
at (4,2+4+2+2) {\rectangled{54}}; 
\node (73) %(s7r11) 
at (6,2+4+2+2) {\rectangled{73}}; 
\node (26) %(s2r12) 
at (1,3+2+2+2+2) {\starred{26}}; 
\node (45) %(s4r12) 
at (3,3+2+2+2+2) {\rectangled{45}}; 
\node (s6r12) at (5,3+2+2+2+2) {\rectangled{64}}; 


\node (17) %(s1r13) 
at (0,2+4+2+2+2) {\starred{17}}; 
\node (36) %(s3r13) 
at (2,2+4+2+2+2) {\rectangled{36}}; 
\node (55) %(s5r13) 
at (4,2+4+2+2+2) {\rectangled{55}}; 
\node (74) %(s7r13) 
at (6,2+4+2+2+2) {\rectangled{74}}; 
\node[gray] (27) %(s2r14) 
at (1,3+2+2+2+2+2) {27}; 
\node[gray] (46) %(s4r14) 
at (3,3+2+2+2+2+2) {46}; 
\node (65) %(s6r14) 
at (5,3+2+2+2+2+2) {\rectangled{65}}; 

\node[gray] (18) %(s1r15)
at (0,2+4+2+2+2+2) {18}; 
\node[gray] (37) %(s3r15) 
at (2,2+4+2+2+2+2) {37}; 
\node[gray] (56) %(s5r15) 
at (4,2+4+2+2+2+2) {56}; 
\node (75) %(s7r15) 
at (6,2+4+2+2+2+2) {\rectangled{75}}; 
% \node (s2r16) at (1,3+2+2+2+2+2+2) {28}; 
% \node (s4r16) at (3,3+2+2+2+2+2+2) {47}; 
% \node (s6r16) at (5,3+2+2+2+2+2+2) {66}; 


% % Now draw the lines:
% \draw [black, thick, 
% shorten <=-5pt, shorten >=-5pt] (42) -- (33); 
% \draw [black, thick, 
% shorten <=-5pt, shorten >=-5pt] (33) -- (24); 
% \draw [black, thick, 
% shorten <=-5pt, shorten >=-5pt] (24) -- (15); 
% \draw [black, thick, 
% shorten <=-5pt, shorten >=-5pt] (61) -- (52); 
% \draw [black, thick, 
% shorten <=-5pt, shorten >=-5pt] (42) -- (52); 
% \draw [black, thick, 
% shorten <=-5pt, shorten >=-5pt] (71) -- (61); 


% \draw [black, thick, 
% shorten <=-6pt, shorten >=-3pt] (52) -- (43); 
% \draw [black, thick, 
% shorten <=-3pt, shorten >=-3pt] (43)-- (34);  
% \draw [black, thick, 
% shorten <=-3pt, shorten >=-3pt] (34) -- (25);  
% \draw [black, thick, 
% shorten <=-3pt, shorten >=-3pt] (25) -- (16); 

% \draw [black, thick, 
% shorten <=-1pt, shorten >=-5pt] (71) -- (62); 
% \draw [black, thick, 
% shorten <=-3pt, shorten >=-3pt] (62) -- (53); 
% \draw [black, thick, 
% shorten <=-3pt, shorten >=-3pt] (53) -- (44); 
% \draw [black, thick, 
% shorten <=-3pt, shorten >=-3pt] (44) -- (35); 
% \draw [black, thick, 
% shorten <=-5pt, shorten >=-5pt] (35) -- (25); 
% \draw [black, thick, 
% shorten <=-3pt, shorten >=-3pt] (26) -- (17); 

% Now draw the lines:
% \draw [red, thick, 
% shorten <=-5pt, shorten >=-2pt] (s1r1) -- (s2r2) -- (s3r1) -- (s4r2) -- (s5r1) -- (s6r2) -- (s7r1) node[pos=0.5, left=5mm]{};
% \draw [violet, thick, shorten <=-2pt, shorten >=-2pt] (s1r3) -- (s2r2) -- (s3r3) -- (s4r2) -- (s5r3) -- (s6r2) -- (s7r3) node[pos=0.5, left=5mm]{};

% \draw [blue, thick, 
% % shorten <=-7pt, shorten >=-7pt
% ] (s1r3) -- (s2r4) -- (s3r3) -- (s4r4) -- (s5r3) -- (s6r4) -- (s7r3) node[pos=0.5, left=5mm]{};
% \draw [violet, thick, shorten <=-2pt, shorten >=-2pt] (s1r5) -- (s2r4) -- (s3r5) -- (s4r4) -- (s5r5) -- (s6r4) -- (s7r5) node[pos=0.5, left=5mm]{};

% \draw [red, thick, shorten <=-2pt, shorten >=-2pt] (s1r5) -- (s2r6) -- (s3r5) -- (s4r6) -- (s5r5) -- (s6r6) -- (s7r5) node[pos=0.5, left=5mm]{};
% \draw [violet, thick, shorten <=-2pt, shorten >=-2pt] (s1r7) -- (s2r6) -- (s3r7) -- (s4r6) -- (s5r7) -- (s6r6) -- (s7r7)  node[pos=0.5, left=5mm]{};

% \draw [red, thick, shorten <=-2pt, shorten >=-2pt] (s1r7) -- (s2r8) -- (s3r7) -- (s4r8) -- (s5r7) -- (s6r8) -- (s7r7) node[pos=0.5, left=5mm]{};
% \draw [violet, thick, shorten <=-2pt, shorten >=-2pt] (s1r9) -- (s2r8) -- (s3r9) -- (s4r8) -- (s5r9) -- (s6r8) -- (s7r9)  node[pos=0.5, left=5mm]{};

% \draw [red, thick, shorten <=-2pt, shorten >=-2pt] (s1r9) -- (s2r10) -- (s3r9) -- (s4r10) -- (s5r9) -- (s6r10) -- (s7r9) node[pos=0.5, left=5mm]{};
\end{tikzpicture}
\begin{tikzpicture}[scale=\myscale]
% \filldraw [yellow!20] 
% (6+.4,14+.4) -- (3,11+.4) -- (2,12+.4) -- (1,11+.4) --
% (0-.4,12+.4) --(0-.4,8-.4) -- 
% (3,5-.4) -- (4,6-.4) -- 
% (5,5-.4) -- (6+.2,6-.4) -- 
% (6+.4,14+.4) ; 

% \draw [black!40, 
% %very 
% thin, 
% ] (0,0) -- (6,6)
% (0,2) -- (6, 6+2)
% (0,4) -- (6-2, 6+4-2)
% (0,6) -- (6-2, 6+6-2)
% (0,8) -- (6-2, 8+6-2)
% ;


% \draw [black!40, 
% %very 
% thin, 
% ] (0,2) -- (1,1)
% (0,2+2) -- (2,2)
% (0,2+4) -- (3,3)
% (0,2+6) -- (4,4)
% (0,4) -- (6, 6+4)
% (0,6) -- (6, 6+6)
% (0,8) -- (6, 8+6)
% (0,10) -- (4, 8+6)
% (0,12) -- (2, 14)
% ;


% \draw [black!40, 
% %very 
% thin, 
% ] 
% (0,10) -- (5,5)
% (0,12) -- (6,6)
% (0,14) -- (6,8)
% (2,14) -- (6,10)
% (4,14) -- (6,12)
% ;

% First, locate each of the nodes and name them
 \node[white] (s1r1) at (0,0) {11}; %{$s_1 l 1$};
% % \node (s3r1) at (2,0) {none}; %{$s_3 l 1$};
% % \node (s5r1) at (4,0) {none}; %{$s_5 l 1$};
% % \node (s7r1) at (6,0) {none}; %{$s_7 l 1$};
% \node[gray] (s2r2) at (1,1) {21}; %{$s_2 l 2$};
% \node (s4r2) at (3,1) {none}; %{$s_4 l 2$};
% \node (s6r2) at (5,1) {none}; %{$s_6 l 2$};

% \node[gray] (s1r3) at (0,2) {12}; %{$s_1 l 3$};
% \node[gray] (s3r3) at (2,2) {31}; %{$s_3 l 3$};
% % \node (s5r3) at (4,2) {none}; %{$s_5 l 3$};
% % \node (s7r3) at (6,2) {none}; %{$s_7 l 3$};
% \node[gray] (22) %(s2r4) 
% at (1,3) {22}; %{$s_2 l 4$};
% \node[gray] (41) %(s4r4) 
% at (3,3) {41}; %{$s_4 l 4$};
% \node (s6r4) at (5,3) {none}; %{$s_6 l 4$};

 % \node[white] (13) %(s1r5) 
 % at (0,2+2) {0};%{13}; %{$s_1 l 5$};
% \node[gray] (32) %(s3r5) 
% at (2,2+2) {32}; %{$s_3 l 5$};
% \node[gray] (51) %(s5r5) 
% at (4,2+2) {51}; %{$s_5 l 5$};
% \node (s7r5) at (6,2+2) {non}; %{$s_7 l 5$};
% \node[gray] (23) %(s2r6) 
 % at (1,3+2) {0}; %{23}; %{$s_2 l 6$};
\node (42) %(s4r6) 
at (3,3+2) {4}; %{\circled{42}}; %{$s_4 l 6$};
\node (61) %(s6r6) 
at (5,3+2) {6}; %{\circled{61}}; %{$s_6 l 6$};

% \node[gray] (14) %(s1r7) 
 % at (0,2+4) {}; %{14}; %{$s_1 l 7$};
\node (33) %(s3r7) 
at (2,2+4) {3}; %{\circled{33}}; %{$s_3 l 7$};
\node (52) %(s5r7) 
at (4,2+4) {5}; %{\circled{52}}; %{$s_5 l 7$};
\node (71) %(s7r7) 
at (6,2+4) {7}; %{\circled{71}}; %{\starred{\circled{71}}};%{$\circled{71}$}; %{$s_7 l 7$};
\node (24) %(s2r8) 
at (1,3+2+2) {2}; %{\circled{24}}; %{$s_2 l 8$};
\node (43) %(s4r8) 
at (3,3+2+2) {4}; %{43}; %{$s_4 l 8$};
\node (62) %(s6r8) 
at (5,3+2+2) {6}; %{\starred{62}}; %{68}; %{$s_6 l 8$};

\node (15) %(s1r9) 
at (0,2+4+2) {1}; %{\circled{15}}; %{$s_1 l 7$};
\node (34) %(s3r9) 
at (2,2+4+2) {3}; %{34}; %{$s_3 l 7$};
\node (53) %(s5r9) 
at (4,2+4+2) {5}; %{\starred{53}}; %{$s_5 l 7$};
\node (72) %(s7r9) 
at (6,2+4+2) {7}; %{\rectangled{72}}; %{$s_7 l 7$};
\node (25) %(s2r10) 
at (1,3+2+2+2) {2}; %{25}; %{$s_2 l 8$};
\node (44) %(s4r10) 
at (3,3+2+2+2) {4}; %{\starred{44}}; %{$s_4 l 8$};
\node (63) %(s6r10) 
at (5,3+2+2+2) {6}; %{\rectangled{63}}; %{68}; %{$s_6 l 8$};

\node (16) %(s1r11) 
at (0,2+4+2+2) {1}; %{16}; 
\node (35) %(s3r11) 
at (2,2+4+2+2) {3}; %{\starred{35}}; 
\node (54) %(s5r11) 
at (4,2+4+2+2) {5}; %{\rectangled{54}}; 
\node (73) %(s7r11) 
at (6,2+4+2+2) {7}; %{\rectangled{73}}; 
\node (26) %(s2r12) 
at (1,3+2+2+2+2) {2}; %{\starred{26}}; 
\node (45) %(s4r12) 
at (3,3+2+2+2+2) {4}; %{\rectangled{45}}; 
\node (64) %(s6r12) 
at (5,3+2+2+2+2) {6}; % {\rectangled{64}}; 


\node (17) %(s1r13) 
at (0,2+4+2+2+2) {1}; %{\starred{17}}; 
\node (36) %(s3r13) 
at (2,2+4+2+2+2) {3}; %{\rectangled{36}}; 
\node (55) %(s5r13) 
at (4,2+4+2+2+2) {5}; % {\rectangled{55}}; 
\node (74) %(s7r13) 
at (6,2+4+2+2+2) {7}; %{\rectangled{74}}; 
% \node[gray] (27) %(s2r14) 
% at (1,3+2+2+2+2+2) {27}; 
% \node[gray] (46) %(s4r14) 
% at (3,3+2+2+2+2+2) {46}; 
\node (65) %(s6r14) 
at (5,3+2+2+2+2+2) {6}; %{\rectangled{65}}; 

% \node[gray] (18) %(s1r15)
% at (0,2+4+2+2+2+2) {18}; 
% \node[gray] (37) %(s3r15) 
% at (2,2+4+2+2+2+2) {37}; 
% \node[gray] (56) %(s5r15) 
% at (4,2+4+2+2+2+2) {56}; 
\node (75) %(s7r15) 
at (6,2+4+2+2+2+2) {7}; %{\rectangled{75}}; 
% \node (s2r16) at (1,3+2+2+2+2+2+2) {28}; 
% \node (s4r16) at (3,3+2+2+2+2+2+2) {47}; 
% \node (s6r16) at (5,3+2+2+2+2+2+2) {66}; 

% Now draw the lines:
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (42) -- (33); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (33) -- (24); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (24) -- (15); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (61) -- (52); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (71) -- (61); 

\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (52) -- (43); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (43)-- (34);  
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (34) -- (25);  
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (25) -- (16); 

\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (71) -- (62); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (62) -- (53); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (53) -- (44); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (44) -- (35); 

\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (26) -- (17); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (35) -- (26); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (26) -- (17); 

\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (72) -- (63);
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (63) -- (54);
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (54) -- (45);
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (45) -- (36); 

\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (73) -- (64); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (64) -- (55); 

\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (74) -- (65); 


\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (16) -- (26); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (26) -- (36); 


\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (15) -- (25); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (25) -- (35); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (35) -- (45); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (45) -- (55); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (55) -- (65);
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (65) -- (75); 

\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (24) -- (34); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (34) -- (44); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (44) -- (54); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (54) -- (64); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (64) -- (74); 

\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (33) -- (43); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (43) -- (53); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (53) -- (63); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (63) -- (73); 


\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (42) -- (52); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (52) -- (62); 
\draw [black, thick, 
shorten <=-2pt, shorten >=-2pt] (62) -- (72); 

% Now draw the lines:
% \draw [red, thick, 
% shorten <=-5pt, shorten >=-2pt] (s1r1) -- (s2r2) -- (s3r1) -- (s4r2) -- (s5r1) -- (s6r2) -- (s7r1) node[pos=0.5, left=5mm]{};
% \draw [violet, thick, shorten <=-2pt, shorten >=-2pt] (s1r3) -- (s2r2) -- (s3r3) -- (s4r2) -- (s5r3) -- (s6r2) -- (s7r3) node[pos=0.5, left=5mm]{};

% \draw [blue, thick, 
% % shorten <=-7pt, shorten >=-7pt
% ] (s1r3) -- (s2r4) -- (s3r3) -- (s4r4) -- (s5r3) -- (s6r4) -- (s7r3) node[pos=0.5, left=5mm]{};
% \draw [violet, thick, shorten <=-2pt, shorten >=-2pt] (s1r5) -- (s2r4) -- (s3r5) -- (s4r4) -- (s5r5) -- (s6r4) -- (s7r5) node[pos=0.5, left=5mm]{};

% \draw [red, thick, shorten <=-2pt, shorten >=-2pt] (s1r5) -- (s2r6) -- (s3r5) -- (s4r6) -- (s5r5) -- (s6r6) -- (s7r5) node[pos=0.5, left=5mm]{};
% \draw [violet, thick, shorten <=-2pt, shorten >=-2pt] (s1r7) -- (s2r6) -- (s3r7) -- (s4r6) -- (s5r7) -- (s6r6) -- (s7r7)  node[pos=0.5, left=5mm]{};

% \draw [red, thick, shorten <=-2pt, shorten >=-2pt] (s1r7) -- (s2r8) -- (s3r7) -- (s4r8) -- (s5r7) -- (s6r8) -- (s7r7) node[pos=0.5, left=5mm]{};
% \draw [violet, thick, shorten <=-2pt, shorten >=-2pt] (s1r9) -- (s2r8) -- (s3r9) -- (s4r8) -- (s5r9) -- (s6r8) -- (s7r9)  node[pos=0.5, left=5mm]{};

% \draw [red, thick, shorten <=-2pt, shorten >=-2pt] (s1r9) -- (s2r10) -- (s3r9) -- (s4r10) -- (s5r9) -- (s6r10) -- (s7r9) node[pos=0.5, left=5mm]{};
\end{tikzpicture}
\caption{Left: Algorithm for constructing the heap $\heap(\sort(w_0))$ for $\rw{4321657}$-sorting word of the longest element $w_0$ in $A_7$. Right: The heap diagram for $\heap(\sort(w_0))$.}%, of length 8 choose 2, which is 28} % 8 choose 2 is 28
\label{fig:longest element heap A7 4321657}
\end{figure}

Thanks to \cite{Bed99, LL20}, we can give a nice algorithmic construction of $\heap(\sort(w_0))$ using the upper- and lower-barred numbers corresponding to $c$. For example, Figure \ref{fig:longest element heap A7 4321657} shows this construction for $\heap(\sort(w_0))$ where $c=\rw{4321 65 7}$ with lower-barred numbers $\underline{5}, \underline{7}$  
and upper-barred numbers $\overline{2}, \overline{3}, \overline{4}, \overline{6}$.  This algorithm gives us the following lemma.


\begin{lem}
Let $c$ be any Coxeter element in $A_n$ with $s$ upper-barred numbers $1< \overline{q_1} < \dots < \overline{q_s} < n+1$ and $r$ lower-barred numbers $1<\underline{p_1}< \dots < \underline{p_r} < n+1$. 
Then 
% Then the reduced word for $w_0$ that is obtained by the linear extension $\mathcal{L}_c$ on $\heap(\sort(w_0))$ is 
% \[
% (s_{p_1-1}\dots s_1)\cdot(s_{p_2-1}\dots s_1) \dots (s_{p_\ell-1}\dots s_1) \cdot (s_{n-1} \dots s_1) \cdot (s_{n-1} \dots s_{n-q_k+1}) \cdots (s_{n-1} \dots s_{n-q_1+1})
% \]
% \[
% \mathcal{R}_c = \rw{\underline{p_1} -1,\dots,1} \dots \rw{\underline{p_\ell} -1,\dots,1} \rw{n,\dots,1} \rw{n, \dots n-\overline{q_k} +2}\dots \rw{n-1,\dots n- \overline{q_1} +2}
% \]
\[
\mathcal{R}_c = \rw{(\underline{p_1} -1) ... 1} \dots  
\rw{(\underline{p_r} -1) ... 1} 
\rw{n ... 1} 
\rw{n ... (n-\overline{q_s} +2)} \dots  
\rw{n ... (n- \overline{q_1} +2)}
\] is a concatenation of $n$ factors, 
where each factor is a decreasing sequence of consecutive integers.
\end{lem}

\begin{example}
For example, the reduced word $\rw{u}=\rw{1}\rw{21}\rw{4321}\rw{432}$ 
given in Example \ref{ex:fig:longest element heap A4 for c 1243} is the diagonal reading word $\mathcal{R}_{\rw{1243}}$ of the heap diagram in Figure \ref{fig:longest element heap A4 for c 1243}. 
The diagonal reading word 
of the heap diagram given in Figure \ref{fig:longest element heap A7 4321657}
is 
\[\mathcal{R}_{\rw{4321 65 7}}=\rw{4321}\rw{654321}\rw{7654321}\rw{76543}\rw{765}\rw{76}\rw{7}.\]
%If $c=\rw{n\dots 1}=s_n \dots s_1$, the diagonal reading word $\mathcal{R}_c$ is equal to the $c$-sorting word of $w_0$. 
\end{example}


% Since $\mathcal{R}_c$ is of length $\binom{n+1}{2}$, we can define elements $b_i$ for $1\leqslant i \leqslant \binom{n+1}{2}$ to be the permutation whose reduced word is formed by the first $i$ simple reflections in $\mathcal{R}_c$. We can see that the $b_i$'s are $c$-singletons. \emily{will rephrase}

\subsection{Unimodular equivalence}


Note that $\mathcal{R}_c$ is of length $\binom{n+1}{2}=\ell(w_0)$, and write $\mathcal{R}_c = \rw{r_1 \dots r_{\ell(w_0)}}$. 
For each $1\leqslant i \leqslant \ell(w_0)$,  
define $b_i$ to be the length-$i$ prefix of  $\mathcal{R}_c$, that is, $b_i = \rw{r_1 \dots r_i}$. 
Since $\mathcal{R}_c$ is a labeled linear extension of $\heap(\sort(w_0))$, 
Proposition \ref{prop:set of labeled linear extensions is commutativity class Stembridge} tells us that
it is in the commutation class of $\sort(w_0)$, 
and thus Theorem~\ref{thm:c-sing-prefix} tells us that  
 each $b_i$ is a $c$-singleton.

%$\mathcal{O}(\heap(\sort(w_0)))$. 
Given a c-singleton $w$, let $f(w)$ be the corresponding order ideal of $\heap(\sort(w_0))$, where $f$ is as defined in Proposition~\ref{prop:vertex-bijection}. 
Consider the vector in $\mathbb{R}^{\ell(w_0)}$ defined by the indicator function of $f(w)$, following the linear extension given by $\mathcal{R}_c$. 
Let $o(w)$ denote this vector in reverse order.
In particular, note that  $o(b_i)$ is the vector whose last $i$ entries are $1$s and whose all other entries are $0$s.

% We will use $o(w)$ to denote the coordinate of the vertex corresponds to $w$ in the order polytope $\mathcal{O}(\heap(\sort(w_0)))$. 
% In fact, $o(b_i)$ is the vector with the last $i$ entries being $1$ and $0$ anywhere else.

\begin{example}\label{eg.basis}
Let $c$ be as in Example~\ref{eg.proj}
% Continuing from Example~\ref{eg.proj} for the Coxeter element $c = s_1s_4s_3s_2s_6s_5s_7$ 
with $\underline{p_1}, \underline{p_2}, \underline{p_3} = \underline{2}, \underline{5}, \underline{7}$ and $\overline{q_1} , \overline{q_2}, \overline{q_3} = \overline{3}, \overline{4}, \overline{6}$.
We have $\mathcal{R}_c = \rw{1\,\, 4321\,\, 654321\,\, 7654321\,\, 76543\,\, 765\,\, 76}$. Therefore $b_4 = s_1s_4s_3s_2=25134678$ and  its permutation matrix is in Figure~\ref{fig.proj} (right).
We can then compute 
\begin{align*}
\Pi_c(b_4) &= (0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0, 1,0,0,1)\,, \text{ and} \\
o(b_4) &= (0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0, 1,1,1,1)\,.
\end{align*}
\end{example}

% \sunita{If there's  space, I think this would be much better as  two examples  -  the first paragraph and picture in the previous section and the second paragraph and picture here.  Or maybe we could  make the two matrices a figure so they can still be side-by-side and then we  can have two examples referencing the figure?}\jianping{I can try to make it two examples that the second one continues from the first one.}\sunita{yes, I think that would be good.}\jianping{I just made a draft of two examples sharing one figure. Please take a look, particular the caption of the Figure~\ref{fig.proj}.}

\begin{lem}
Let $c$ be a Coxeter element of $A_n$. 
Then the $\left(\binom{n+1}{2}-i+1\right)$\textsuperscript{th} entry of the vector $\Pi_c(b_i)$  is $1$,  
and all earlier entries of $\Pi_c(b_i)$ are zero.
That is, the matrix whose columns are $\Pi_c(b_i)$ 
%for $1\leqslant i \leqslant \binom{n+1}{2}$ 
is a lower antidiagonal triangular matrix with $1$'s along the antidiagonal.
\end{lem}

% \begin{lem}
% $\Pi_c$ does not take any entry from the main diagonal.
% \end{lem}

% \subsection{Unimodular transformation}

\begin{thm}\label{thm:main}
Fix a Coxeter element $c$ in $A_n$. There exists a $\binom{n+1}{2}\times \binom{n+1}{2}$ lower-triangular matrix $\mathcal{U}_c$ with $1$'s on the main diagonal such that $\mathcal{U}_c\circ\Pi_c(b_i) = o(b_i)$ for all $1\leqslant i \leqslant \binom{n+1}{2}$.
Furthermore,  we have $\mathcal{U}_c \circ \Pi_c(w) = o(w)$ for any $c$-singleton $w$.
\end{thm}

%Since the projection $\Pi_c$ preserves lattice points and the linear transformation $\mathcal{U}_c$ has determinant $1$, we have shown the $c$-Birkhoff polytope is unimodularly equivalent to the order polytope $\mathcal{O}(\heap(\sort(w_0)))$. In particular, the normalized volume of the $c$-Birkhoff polyope is equal to the number of longest chains in the corresponding Cambrian lattice.

\begin{corollary}
The $c$-Birkhoff polytope $\bir(c)$ is unimodularly equivalent to the order polytope $\mathcal{O}(\heap(\sort(w_0)))$.
\end{corollary}

\begin{proof}
This follows from the facts that the projection $\Pi_c$ preserves lattice points (Theorem~\ref{thm.lattice}) and that the linear transformation $\mathcal{U}_c$ has determinant $1$ (Theorem~\ref{thm:main}).
\end{proof}

\begin{corollary}\label{cor:vol}
The normalized volume of the $c$-Birkhoff polyope is equal to the number of longest chains in the corresponding Cambrian lattice.
\end{corollary}

Corollary~\ref{cor:vol} recovers, and generalizes, a result of Davis and Sagan in~\cite{DS18}.

\begin{remark}
One might ask whether our result generalizes as follows:
If $w\in A_n$ and $\rw{u}$ is a reduced word for $w$ then the order polytope of $\heap{\rw{u}}$ is unimodularly equivalent to the convex hull of the permutations corresponding to order ideals of $\heap{\rw{u}}$.  This is not true in general; for $A_4$ the reduced words $\rw{2123243212}$ and $\rw{3432312343}$ are counterexamples.  It would be interesting to determine when the above statement holds.
\end{remark}


\acknowledgements{We thank the Minnesota Research Workshop in Algebraic Combinatorics 2022 (MRWAC 2022) organizers for bringing us together. 
This project benefited from the input and feedback of many people including  
Emily Barnard,
Rob Davis,
Jesus De Loera,
Galen Dorpalen-Barry, 
Elizabeth Kelley, 
Jean-Philippe Labb\'{e}, 
Fu Liu, 
Emily Meehan,
Alejandro Morales,
Sasha Pevzner, 
Nathan Reading,
Bruce Sagan, 
Frank Sottile, 
Jessica Striker, 
and Sylvester Zhang. 
We would also like to thank the anonymous reviewers for their feedback and suggestions.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
