%% 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]{FPSAC2023}
\articlenumber{1}
%% 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}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{hyperref}

\DeclareMathOperator{\conv}{Conv}
\DeclareMathOperator{\weak}{Weak}
\DeclareMathOperator{\Bot}{bot} 
\DeclareMathOperator{\Top}{top}
\DeclareMathOperator{\fl}{fl}
\DeclareMathOperator{\asc}{asc}
\DeclareMathOperator{\Perm}{Perm}

\newcommand{\ph}{\varphi}
\newcommand{\mc}{\mathcal}
\newcommand{\mf}{\mathfrak}
\newcommand{\bs}{\boldsymbol}
\renewcommand{\tilde}{\widetilde}

\newcommand{\GL}{\mathrm{GL}}
\newcommand{\height}{\mathrm{ht}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Vol}{\mathrm{Vol}}
\newcommand{\id}{\mathrm{id}}
\renewcommand{\O}{\mathcal{O}}

\newcommand\precdot{\mathrel{\ooalign{$\prec$\cr
  \hidewidth\raise0.001ex\hbox{$\cdot\mkern0.6mu$}\cr}}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{def-prop}[theorem]{Definition-Proposition}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{introthm}{Theorem}
\renewcommand{\theintrothm}{\Alph{introthm}}

\theoremstyle{definition}
\newtheorem{ex}[theorem]{Example}
\newtheorem{quest}[theorem]{Question}
\newtheorem{defin}[theorem]{Definition}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\makeatletter
\newcommand*{\da@rightarrow}{\mathchar"0\hexnumber@\symAMSa 4B }
\newcommand*{\da@leftarrow}{\mathchar"0\hexnumber@\symAMSa 4C }
\newcommand*{\xdashrightarrow}[2][]{%
  \mathrel{%
    \mathpalette{\da@xarrow{#1}{#2}{}\da@rightarrow{\,}{}}{}%
  }%
}
\newcommand{\xdashleftarrow}[2][]{%
  \mathrel{%
    \mathpalette{\da@xarrow{#1}{#2}\da@leftarrow{}{}{\,}}{}%
  }%
}
\newcommand*{\da@xarrow}[7]{%
  % #1: below
  % #2: above
  % #3: arrow left
  % #4: arrow right
  % #5: space left 
  % #6: space right
  % #7: math style 
  \sbox0{$\ifx#7\scriptstyle\scriptscriptstyle\else\scriptstyle\fi#5#1#6\m@th$}%
  \sbox2{$\ifx#7\scriptstyle\scriptscriptstyle\else\scriptstyle\fi#5#2#6\m@th$}%
  \sbox4{$#7\dabar@\m@th$}%
  \dimen@=\wd0 %
  \ifdim\wd2 >\dimen@
    \dimen@=\wd2 %   
  \fi
  \count@=2 %
  \def\da@bars{\dabar@\dabar@}%
  \@whiledim\count@\wd4<\dimen@\do{%
    \advance\count@\@ne
    \expandafter\def\expandafter\da@bars\expandafter{%
      \da@bars
      \dabar@ 
    }%
  }%  
  \mathrel{#3}%
  \mathrel{%   
    \mathop{\da@bars}\limits
    \ifx\\#1\\%
    \else
      _{\copy0}%
    \fi
    \ifx\\#2\\%
    \else
      ^{\copy2}%
    \fi
  }%   
  \mathrel{#4}%
}
\makeatother

%\newtheorem{thm}{Theorem}
%\newtheorem{lem}{Lemma}

%\usepackage{lipsum}

%% define your title in the usual way
\title{Bruhat interval polytopes, 1-skeleton lattices, and smooth torus orbit closures}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Christian Gaetz\thanks{\href{mailto:crgaetz@gmail.com}{crgaetz@gmail.com}. The author is supported by a Klarman Postdoctoral Fellowship at Cornell University.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Cornell University, Ithaca, NY}

%% put the date of submission here
\received{October 16, 2022}

%% leave this blank until submitting a revised version
\revised{March 20, 2023}

%% 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{Introduced by Kodama and Williams, \emph{Bruhat interval polytopes} are generalized permutohedra closely connected to the study of torus orbit closures and total positivity in Schubert varieties. We show that the 1-skeleton posets of these polytopes are lattices and classify when the polytopes are simple, thereby resolving open problems and conjectures of Fraser, of Lee--Masuda, and of Lee--Masuda--Park. In particular, we classify when generic torus orbit closures in Schubert varieties are smooth.}

%% 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{Bruhat interval polytope, weak order, Bruhat order, lattice, Schubert variety, torus orbit, smooth}

%% 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{fpsac.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

\section{Introduction}

\subsection{Bruhat interval polytopes}
For a permutation $w$ in $S_n$, write $\bs{w}$ for the vector $(w^{-1}(1),\ldots,w^{-1}(n)) \in \R^n$. The \emph{Bruhat interval polytope} $Q_w$ is defined as the convex hull:
\[
Q_w \coloneqq \conv(\{\bs{u} \mid u \preceq w \}) \subset \R^n,
\]
where $\preceq$ denotes Bruhat order on $S_n$ (see \cref{sec:background}). Bruhat interval polytopes were introduced by Kodama and Williams in \cite{kodama-williams}, where it is shown that they are the images under the \emph{moment map} of the \emph{Schubert variety} $X_w$ in the flag variety, and also of the \emph{totally positive part} $X_w^{\geq 0}$ of the Schubert variety. Therefore, the combinatorics of $Q_w$ encodes information about the actions of the torus and positive torus on $X_w$ and $X_w^{\geq 0}$ respectively.

The combinatorics of $Q_w$ was studied further by Tsukerman and Williams \cite{Tsukerman-Williams}, who showed that $Q_w$ is a \emph{generalized permutohedron} in the sense of Postnikov \cite{postnikov-beyond} and the matroid polytope of a flag \emph{positroid}. Additional connections to the geometry of matroids were made in \cite{boretsky-eur-williams}, and Bruhat interval polytopes have also appeared \cite{Williams} in the context of BCFW-bridge decompositions \cite{arkani-hamed_bourjaily_cachazo_goncharov_postnikov_trnka_2016} from physics, and in the study \cite{lee-conjecture, lee-retractions, lee-toric-bip, lee-poincare} of \emph{generic torus orbit closures} $Y_w$ in $X_w$.

\subsection{The 1-skeleton of $Q_w$ as a lattice}

Throughout this work, we study the \emph{1-skeleton poset} $P_w$ of $Q_w$, a partial order on the lower Bruhat interval $[e,w]=\{u \mid u \preceq w\}$.

\begin{defin}
\label{def:Pw}
The poset $(P_w, \leq_w)$ has underlying set the Bruhat interval $[e,w]$ and cover relations $u \lessdot_w v$ whenever $Q_w$ has an edge between vertices $\bs{u}$ and $\bs{v}$ and $\ell(v)>\ell(u)$, where $\ell$ denotes Coxeter length.
\end{defin}

When $w=w_0$ is the \emph{longest permutation}, the polytope $Q_w$ is the \emph{permutohedron}, a fundamental object in algebraic combinatorics, and the poset $P_w$ is the very well-studied \emph{right weak order} (see \cref{sec:background}). For general $w$, since edges of $Q_w$ must be Bruhat covers by \cite{Tsukerman-Williams}, the order $\leq_w$ is intermediate in strength between right weak order and Bruhat order on $[e,w]$. Since the work of Bj\"{o}rner \cite{bjorner-lattice} it has been known that the weak order $P_{w_0}$ on $S_n$ is a \emph{lattice}; in our first main theorem, we generalize this to all of the posets $P_w$.

\begin{introthm}[Proven as \cref{thm:bip-poset-is-lattice}]
\label{thm:intro-lattice}
Let $w \in S_n$, then $P_w$ is a lattice.
\end{introthm}

As explained below, special cases of this lattice structure confirm a conjecture of Fraser \cite{fraser2020cyclic}, recover several previous results of various authors, imply new properties of $Q_w$, and suggest interesting directions for future work.

\subsubsection{BCFW-bridge decompositions}
In the last decade, there has been an explosion of work (see \cite{arkani-hamed_bourjaily_cachazo_goncharov_postnikov_trnka_2016}) relating the physical theory of \emph{scattering amplitudes} to the combinatorics and geometry of the \emph{totally nonnegative Grassmannian} $Gr(k,n)_{\geq 0}$ by way of the \emph{amplituhedron}. In this setting, \emph{on-shell diagrams} from physics correspond to \emph{reduced plabic graphs}, which give parametrizations of an important cell decomposition of $Gr(k,n)_{\geq 0}$ \cite{postnikov2006total}. 

In \cite{arkani-hamed_bourjaily_cachazo_goncharov_postnikov_trnka_2016} it is shown that reduced plabic graphs for a given cell may be built up recursively using \emph{BCFW-bridge decompositions}. In \cite{Williams}, Williams showed that these decompositions of plabic graphs correspond to the maximal chains in $P_v$ when $v$ is a Grassmannian permutation, analogous to the fact that reduced words for the longest permutation $w_0$ correspond to maximal chains in $P_{w_0}$ (weak order). Since weak order is a lattice, \cref{thm:intro-lattice} extends this analogy and implies new structure within the set of BCFW-bridge decompositions. That $P_v$ is a lattice for Grassmannian permutations was conjectured by Fraser \cite{fraser2020cyclic}. Fraser also conjectured that a larger class of posets, which are not necessarily the 1-skeleton posets of any polytope, are lattices; this problem remains open. 

\subsubsection{Quotients of weak order}
\cref{thm:intro-lattice} is proven by realizing $P_w$ as a quotient of weak order $P_{w_0}$ by an equivalence relation $\Theta_w$ which respects the weak order join operation (but does \emph{not} respect the meet operation!) Thus $P_w$ is a \emph{semilattice quotient} of $P_{w_0}$ but not a \emph{lattice quotient}. The lattice quotients and lattice homomorphisms of weak order have been classified \cite{reading-noncrossing, reading-homomorphisms}. This work thus suggests that semilattice quotients and homomorphisms of weak order are an intriguing topic for further study.

\subsubsection{The parabolic map and the mixed meet}
Let $S_n(I)$ denote the subgroup of $S_n$ generated by a subset $I$ of the simple reflections. Billey, Fan, and Losonczy proved \cite{billey-parabolic} that for any $w \in S_n$ the set $S_n(I) \cap [e,w]$ has a unique maximal element $m(w,I)$ under Bruhat order. Richmond and Slofstra \cite{Richmond-fiber-bundle} showed that this element $m(w,I)$ determines whether the projection of the Schubert variety $X_w \subset G/B$ to a partial flag variety $G/P$ is a fiber bundle, and is thus important for understanding the singularities of $X_w$. We show in \cref{thm:join-of-atoms} that the element $m(w,I)$ is just the join in $P_w$ of the simple reflections from $I$, demonstrating the richness of the lattice structure on $P_w$.

A related operation of \emph{mixed meet} was studied by Bump and Chetard in \cite{bump2021matrix} in relation to certain intertwining operators of representations of reductive groups over nonarchimedean local fields. The mixed meet of $u,v \in S_n$ is the unique Bruhat maximal permutation in $[e,u]_R \cap [e,v]$. In the language of \cref{sec:lattice}, this element is $\Bot_v(u)$, the unique minimal element under $\leq_R$ in the equivalence class of $u$ under the equivalence relation $\Theta_v$ induced on $S_n$ by the normal fan of $Q_v$. This element is a translate of $\mu_v(u)$, where $\mu_v$ is the \emph{matroid map} obtained by viewing $[e,v]$ as a Coxeter matroid \cite{coxeter-matroids}.

\subsubsection{The non-revisiting path property}
A polytope $Q$ has the \emph{non-revisiting path property} if no shortest path in its 1-skeleton between two vertices returns to a face after having left it. This property has long been of interest in the field of combinatorial optimization. In \cite{Hersh}, Hersh proves that any simple polytope whose 1-skeleton poset is a lattice has the non-revisiting path property. Thus, combining \cref{thm:intro-lattice} and the classification of simple Bruhat interval polytopes in \cref{thm:intro-smooth} below, we obtain a rich new family of examples to which Hersh's theorem applies. Additionally, in \cref{sec:directionally-simple} we observe that all polytopes $Q_w$ are \emph{directionally} simple. We therefore ask: does Hersh's theorem extend to directionally simple polytopes?

\subsection{Bruhat interval polytopes and generic torus orbit closures}

\subsubsection{Simple Bruhat interval polytopes and smooth torus orbit closures}
Let $G=GL_n(\mathbb{C})$, let $B$ denote the Borel subgroup of upper triangular matrices, and let $T$ denote the maximal torus of diagonal matrices. The \emph{flag variety} $Fl_n=G/B$ and its Schubert subvarieties $X_w \coloneqq \overline{BwB/B}$ are of fundamental importance in many areas of algebraic combinatorics, algebraic geometry, and representation theory. The torus $T$ acts naturally on $G/B$ via left multiplication, and the fixed points $(G/B)^T$ are the points $wB$ for $w \in S_n$, where we identify $w$ with its permutation matrix. The fixed points of the Schubert variety $X_w$ are $\{uB \mid u \preceq w\}$.

Torus orbits in $G/B$ and their closures are a rich family of varieties, studied since Klyachko \cite{Klyachko} and Gelfand--Serganova \cite{Gelfand-serganova} with close connections to matroids and Coxeter matroids \cite{coxeter-matroids}. One class of torus orbit closures has received considerable interest \cite{lee-conjecture, lee-retractions, lee-toric-bip, lee-poincare} of late: \emph{generic} torus orbit closures in Schubert varieties. A torus orbit closure $Y \subset X_w$ is called generic if $Y^T=X_w^T$; we write $Y_w$ for a generic torus orbit closure in $X_w$.

One of the main properties of interest for torus orbits in the flag variety has historically been their singularities \cite{Carrell-normality, Carrell-smooth-point}, and in particular determining when they are smooth. For Schubert varieties themselves, smoothness was famously characterized by Lakshmibai--Sandhya \cite{Lakshmibai-sandhya} in terms of pattern avoidance. In our next main theorem, we resolve a conjecture of Lee and Masuda \cite{lee-conjecture} by classifying when $Y_w$ is smooth.

\begin{introthm}[Conjectured by Lee--Masuda \cite{lee-conjecture}; Proven below as \cref{cor:smooth-conjecture}]
\label{thm:intro-smooth}
Let $w \in S_n$, then $Q_w$ is a simple polytope if and only if it is simple at the vertex $\bs{w}$; equivalently, $Y_w$ is a smooth variety if and only if it is smooth at the point $wB$.
\end{introthm}

\cref{thm:intro-smooth} is proven by showing (see \cref{thm:degree-monotonicity}) that the degree of a vertex of $Q_w$ is an ordering preserving function of the poset $P_w$.

By \cite{lee-conjecture}, the condition that $Y_w$ is smooth at $wB$ can be checked combinatorially by determining whether a certain graph $\Gamma_w(w)$ is a tree (see \cref{sec:gamma-graphs}). This tree condition has in turn been characterized combinatorially in terms of pattern avoidance \cite{bosquet-melou-forest}, and shown \cite{woo-yong-gorenstein} to characterize when $X_w$ is \emph{locally factorial}. By work of Bj\"{o}rner--Ekedahl \cite{Bjorner-ekedahl} it is also equivalent to the vanishing of the coefficient of $q$ in the associated \emph{Kazhdan--Lusztig polynomial} \cite{kazhdan--lusztig} and thus \cite{kazhdan--lusztig2} the vanishing of a certain middle intersection cohomology group of $X_w$. It would be fascinating to give a purely geometric explanation for the equivalence (by \cref{thm:intro-smooth}) of the smoothness of $Y_w$ with these other geometric conditions on $X_w$. 

\subsubsection{Directionally simple polytopes and $h$-vectors}

In \cref{sec:directionally-simple} we show that, even when $Q_w$ is not a simple polytope, it is still \emph{directionally simple} (see \cref{def:directionally-simple}). This fact was also shown in \cite{lee-poincare} by an involved calculation, but follows directly from our results realizing $P_w$ as a quotient of weak order. This property of $Q_w$ implies that its \emph{h-vector} has positive entries which count certain permutations according to their number of ascents. In \cref{prop:smooth-if-palindromic} we resolve an open problem of Lee--Masuda--Park \cite{lee-survey} by showing that $Y_w$ is smooth if and only if this $h$-vector is palindromic.


\section{Background on the weak and strong Bruhat orders}
\label{sec:background}
We refer the reader to \cite{bjorner-brenti} for basic definitions and results on Coxeter groups.

We view the symmetric group $S_n$ as a Coxeter group with generators $s_1,\ldots,s_{n-1}$, where $s_i\coloneqq (i \: i+1)$ is an adjacent transposition. An expression $w=s_{i_1}\cdots s_{i_{\ell}}$ of minimal length is a \emph{reduced word} for $w$ and in this case the quantity $\ell=\ell(w)$ is the \emph{length} of $w$. There are two important partial orders on $S_n$, each graded by length. The \emph{right weak order} $\leq_R$ by definition has cover relations $w \lessdot_R ws$ whenever $s$ is a simple generator and $\ell(ws)=\ell(w)+1$; the \emph{(strong) Bruhat order} $\preceq$ has cover relations $w \precdot wt$ whenever $\ell(wt)=\ell(w)+1$ and $t$ lies in the set $T$ of transpositions $(ij)$. We write $[v,w]_R$ and $[v,w]$ for the closed interval between $v,w$ in right weak and Bruhat order respectively.

The \emph{left inversions} of an element $w \in S_n$ are the reflections $T_L(w)\coloneqq \{t \in T \: | \: \ell(tw)<\ell(w)\}$. It is well-known that weak order is characterized by containment of inversions:

\begin{prop}
\label{prop:weak-characterized-by-inversions}
Let $v,w \in S_n$, then $v \leq_R w$ if and only if $T_L(v) \subseteq T_L(w)$.
\end{prop}

The symmetric group contains a unique element $w_0$ of maximum length, and $w_0$ is the unique maximal element of $S_n$ under both $\leq_R$ and $\preceq$. In fact, weak order is a lattice.

\begin{theorem}[Bj\"{o}rner \cite{bjorner-lattice}]
\label{thm:weak-is-lattice}
The poset $(S_n, \leq_R)$ is a lattice; we write $\land_R$ and $\lor_R$ for the meet and join in right weak order.
\end{theorem}

\section{The graphs $\tilde{\Gamma}_w$ and $\Gamma_w$}
\label{sec:gamma-graphs}
Lee and Masuda \cite{lee-conjecture} provided a combinatorial model for determining the edges incident to a vertex $\bs{u}$ of $Q_w$.

\begin{defin}[Lee and Masuda \cite{lee-conjecture}]
For $u \preceq w$, the directed graph $\tilde{\Gamma}_w(u)$ has vertex set $[n]$ with directed edges $(u(i),u(j))$ whenever $i<j$, $u(ij) \preceq w$, and $\left| \ell(u(ij))-\ell(u) \right|=1$. We write $\tilde{E}_w(u)$ for this set of edges. The directed graph $\Gamma_w(u)$ is defined to be the transitive reduction of $\tilde{\Gamma}_w(u)$, with edge set $E_w(u)$.
\end{defin}

\begin{prop}[Lee and Masuda \cite{lee-conjecture}, Proposition 7.7]
\label{prop:edges-from-E}
Two vertices $\bs{u}$ and $\bs{v}$ of $Q_w$ are connected by an edge of the polytope if and only if $v=u(ij)$ where $(u(i),u(j)) \in E_w(u)$.
\end{prop}

The proofs of the main theorems rely on a detailed development of the properties of directed paths in the graphs $\Gamma_w(u)$ and $\tilde{\Gamma}_w(u)$, and how these change as $u$ varies, some of which are sampled below.

\subsection{Directed paths and local changes}
When the permutation $w$ is understood, we write $a \xrightarrow{u} b$ when $(a,b) \in \tilde{E}_w(u)$ and $a \xdashrightarrow{u} b$ when there is a directed path from $a$ to $b$ in $\tilde{\Gamma}_w(u)$ (equivalently, in $\Gamma_w(u)$); we write $a \xRightarrow{u} b$ when $(a,b) \in E_w(u)$.

\begin{prop}
\label{prop:reflection-gives-gamma-path}
Let $u,w \in S_n$ with $u \preceq w$, and suppose $(ab)u \preceq w$, where $u^{-1}(a)<u^{-1}(b)$, then $a \xdashrightarrow{u} b$. In particular, if $(ab) \in T_L(u)$, then $a \xdashrightarrow{u} b$.
\end{prop}

The following proposition is a fundamental ingredient in many of proofs of the subsequent theorems. Its proof is rather involved and must be omitted for the sake of space.

\begin{prop}
\label{prop:v-paths-to-u-paths}
Suppose that $u,v \in S_n$ satisfy $u \lessdot_w v = (ab)u$, with $a<b$:
\begin{itemize}
    \item[\normalfont(i)] If $c<d$ and $c \xdashrightarrow{v} d$, then $c \xdashrightarrow{u} d$;
    \item[\normalfont(ii)] If $c>d, c \neq b, d \neq a,$ and $c \xdashrightarrow{v} d$, then $c \xdashrightarrow{u} d$.
\end{itemize}
\end{prop}

\section{The lattice property}
\label{sec:lattice}

\subsection{Generalized permutohedra}

The normal fan of the permutohedron $\Perm_n = Q_{w_0}$ is the fan determined by the \emph{braid arrangement}, which has defining hyperplanes $x_i-x_j=0$ for $\forall i \neq j$. The top-dimensional cones $C(y)$ in this fan are naturally labelled by permutations $y \in S_n$ giving the relative order of the coordinates of a point $(x_1,\ldots,x_n) \in C(y)$; in particular we have $\bs{y} \in C(y)$. 

Following Postnikov \cite{postnikov-beyond}, a polytope whose normal fan coarsens the braid arrangement is called a \emph{generalized permutohedron}. Kodama--Williams \cite{kodama-williams} showed that Bruhat interval polytopes are generalized permutohedra. This implies that each top-dimensional cone $C_w(u)$ (where $u$ now runs over the elements of $[e,w]$) in the normal fan of $Q_w$ contains some of the $C(y)$. We write $[y]_w$ for the equivalence class of $y$ under the equivalence relation $\Theta_w$ induced on $S_n$ by the normal fan of $Q_w$. 

We say $y \in S_n$ is a \emph{linear extension} of $\Gamma_w(u)$ (equivalently, of $\tilde{\Gamma}_w(u)$) if $y^{-1}(i)<y^{-1}(j)$ whenever $i \xdashrightarrow{u} j$. The following proposition is immediate from the construction of $\Gamma_w(u)$ in Section 5 of \cite{lee-conjecture} and the discussion of normal fans of generalized permutohedra in Section 3 of \cite{postnikov-reiner-williams}.

\begin{prop}[See \cite{lee-conjecture, postnikov-reiner-williams}]
\label{prop:classes-are-linear-extensions-of-gamma}
Let $w \in S_n$ and $u \preceq w$, then $[u]_w$ is exactly the set of linear extensions of $\Gamma_w(u)$.
\end{prop}

Somewhat surprisingly, the equivalence classes $[x]_w$ turn out to be intervals in right weak order. This result was established by other means in \cite{lee-conjecture}, but the particulars of our proof will be important later.

\begin{prop}
\label{prop:class-has-min-max-elements}
Let $x,w \in S_n$, then $[x]_w$ contains a unique minimal element $\Bot_w(x)$ and unique maximal element $\Top_w(x)$ under right weak order.
\end{prop}
\begin{proof}
Let $u$ be the unique element of $[e,w] \cap [x]_w$. By \cref{prop:classes-are-linear-extensions-of-gamma}, the elements $y$ of $[x]_w$ are exactly the linear extensions of $\tilde{\Gamma}_w(u)$. Suppose that $(ab) \in T_L(u)$ with $a<b$, then by \cref{prop:reflection-gives-gamma-path} we have $b \xdashrightarrow{u} a$, so by \cref{prop:classes-are-linear-extensions-of-gamma} we have $(ab) \in T_L(y)$ for any $y \in [x]_w$. Thus by \cref{prop:weak-characterized-by-inversions} we have $u \leq_R y$, so $\Bot_w(x)=u$.

The reflections occurring as left inversions of some linear extension of $\tilde{\Gamma}_w(u)$ are exactly those in 
\[
I \coloneqq \{(ab) \mid a<b \text{ and } a \not \xdashrightarrow{u} b\}.
\]
To see that $\Top_w(x)$ exists, we will demonstrate that the corresponding set of roots, $R=\{e_a-e_b \mid (ab) \in I\}$, is biclosed, so that $\Top_w(x)$ will be the unique permutation with left inversion set $I$.

First, note that if $a \xdashrightarrow{u} b$ and $b \xdashrightarrow{u} c$, then $a \xdashrightarrow{u} c$, so $R$ is coclosed. 

For closedness, let $a<b<c$ and assume that $a \xdashrightarrow{u} c$, which implies that $u^{-1}(a)<u^{-1}(c)$. If $u^{-1}(b)<u^{-1}(a)$, then $(ab) \in T_L(u)$, so by \cref{prop:reflection-gives-gamma-path} we have $b \xdashrightarrow{u} a \xdashrightarrow{u} c$, so $b \xdashrightarrow{u} c$. If instead $u^{-1}(b)>u^{-1}(c)$, then $(bc) \in T_L(u)$, so by \cref{prop:reflection-gives-gamma-path} we have $a \xdashrightarrow{u} c \xdashrightarrow{u} b$, so $a \xdashrightarrow{u} b$. Otherwise we have $u^{-1}(a)<u^{-1}(b)<u^{-1}(c)$. Consider a path $a \to a_1 \to \cdots \to a_r \to c_1 \to \cdots \to c_s \to c$, where $u^{-1}(a_i)\leq u^{-1}(b)$ and $u^{-1}(b)<u^{-1}(c_j)$ for all $i,j$. If any $a_i>b$, then $a \xdashrightarrow{u} a_i \xdashrightarrow{u} b$. If any $c_j<b$, then $b \xdashrightarrow{u} c_j \xdashrightarrow{u} c$. Otherwise, since $(a_r \: c_1) u$ covers $u$ in Bruhat order, we must have $a_r=b$, so $a \xdashrightarrow{u} b \xdashrightarrow{u} c$. In all cases, we see $a \xdashrightarrow{u} b$ or $b \xdashrightarrow{u} c$, so $R$ is closed.  
\end{proof}

\subsection{The poset structure}

\begin{theorem}
\label{thm:top-is-order-preserving}
Given $w \in S_n$, the map $\Top_w: S_n \to S_n$ is order preserving with respect to right weak order. That is, if $x \leq_R y$ then $\Top_w(x) \leq_R \Top_w(y)$. Furthermore, the quotient $\weak_R(S_n)/\Theta_w$ is isomorphic to $P_w$ via the map $[x]_w \mapsto \Bot_w(x)$.
\end{theorem}
\begin{proof}
By the proof of \cref{prop:class-has-min-max-elements}, we have for any $z \in S_n$ that 
\begin{equation}
\label{eq:inversions-of-top-from-graph}
T_L(\Top_w(z))=\{(cd) \mid c<d \text{ and } c \not \xdashrightarrow{\Bot_w(z)} d\}.
\end{equation}
Thus if $u= \lessdot_w = v=(ab)u$ with $a<b$ then by \cref{prop:v-paths-to-u-paths}(i) and \eqref{eq:inversions-of-top-from-graph} we have that 
\[
T_L(\Top_w(u)) \subset T_L(\Top_w(v)).
\]
By \cref{prop:weak-characterized-by-inversions} we see $\Top_w(u) <_R \Top_w(v)$. 

Now suppose that $x \lessdot_R y=xs=tx$ with $[x]_w \neq [y]_w$, so $C_w(u)$ and $C_w(v)$ share a facet along the hyperplane fixed by the reflection $t$, where $u \coloneqq \Bot_w(x)$ and $v\coloneqq \Bot_w(y)$. This implies that there is an edge of $Q_w$ with vertices $\bs{u}$ and $\bs{v}$. Since $u \leq_R x$ by \cref{prop:class-has-min-max-elements}, we have that $t \not \in T_L(u)$ by \cref{prop:weak-characterized-by-inversions} and the fact that $t \not \in T_L(x)$. Since the convex cones $C_w(u)$ and $C_w(v)$ share at most one facet, and since $v=ut'$ for some $t' \in T$, we must have in fact that $t=t'$, and thus $\ell(v)>\ell(u)$ and $u \lessdot_w v$. This establishes that $P_w \cong \weak_n/\Theta_w$, and that $\Top_w$ is order preserving, after applying the first paragraph and that fact that $\Top_w(u)=\Top_w(x)$ and $\Top_w(v)=\Top_w(y)$.
\end{proof}

\begin{cor}
\label{cor:bip-poset-is-induced-weak}
Let $w \in S_n$, then the map $\Top_w: [e,w] \to \Top_w([e,w])$ is an isomorphism between the posets $P_w$ and $(\Top_w([e,w]), \leq_R)$.
\end{cor}

The fact that $P_w$ is a lattice also follows easily from \cref{thm:top-is-order-preserving}.

\begin{theorem}
\label{thm:bip-poset-is-lattice}
For any $w \in S_n$, the poset $P_w$ is a lattice, with join operation given by
\[
u \lor_w v = \Bot_w(\Top_w(u) \lor_R \Top_w(v)).
\]
\end{theorem}
\begin{proof}
Let $z=\Bot_w(\Top_w(u) \lor_R \Top_w(v))$. Then 
\[
u \leq_R \Top_w(u) \leq_R \Top_w(u) \lor_R \Top_w(v),
\]
so by \cref{thm:top-is-order-preserving} we have $u \leq_w z$, and similarly $v \leq_w z$. On the other hand, if $y \geq_w u,v$, then by \cref{thm:top-is-order-preserving} we have $\Top_w(y) \geq \Top_w(u), \Top_w(v)$ so $\Top_w(y) \geq \Top_w(u) \lor_R \Top_w(v)$. Thus $y \geq_w z$ and we see that $z$ is the join of $u,v$ in $P_w$. Since $P_w$ is a finite poset with a join and a unique minimal element, it also has a meet and is thus a lattice.
\end{proof}

Unlike weak order, $P_w$ is not in general a semidistributive lattice.

\subsection{The Billey--Fan--Losonczy parabolic map}

Let $S_n(I)$ denote the subgroup of $S_n$ generated by a subset $I$ of the simple reflections. For $w \in S_n$ let $m(w,I)$ denote the unique maximal element of $S_n(I) \cap [e,w]$ under Bruhat order \cite{billey-parabolic} (see Richmond and Slofstra \cite{Richmond-fiber-bundle} for the importance of these elements in determining the fiber bundle structure of Schubert varieties).

\begin{theorem}
\label{thm:join-of-atoms}
Let $w \in S_n$, and let $I$ be a set of simple generators, then:
\[
m(w,I)=\bigvee_w \{s_i \in I \mid s_i \preceq w\}.
\]
\end{theorem}

\section{Directionally simple polytopes}
\label{sec:directionally-simple}
Given a polytope $Q \subset \R^d$, say that a cost vector $c \in \R^d$ is \emph{generic} if $c$ is not orthogonal to any edge of $Q$. A generic cost vector induces an acyclic orientation on the 1-skeleton $G(Q)$ by taking edges to be oriented in the direction of greater inner product with $c$; we write $G_c(Q)$ for the resulting acyclic directed graph. It is clear that every face $F$ of $Q$ contains a unique source $\min_c(F)$ and sink $\max_c(F)$ with respect to this orientation.

\begin{defin}
\label{def:directionally-simple}
We say that a polytope $Q \subset \R^d$ is \emph{directionally simple} with respect to the generic cost vector $c$ if for every vertex $v$ of $Q$ and every set $E$ of edges of $G_c(Q)$ with source $v$ there exists a face $F$ of $Q$ containing $v$ whose set of edges incident to $v$ is $E$.
\end{defin}

\begin{prop}
A simple polytope $Q \subset \R^d$ is directionally simple with respect to any generic cost vector.
\end{prop}

\cref{thm:bip-is-directionally-simple} was proven in \cite{lee-poincare} by an involved direct computation; here we give a new proof using the results of \cref{sec:lattice}.

\begin{theorem}
\label{thm:bip-is-directionally-simple}
Let $w \in S_n$, then $Q_w$ is a directionally simple polytope with respect to the cost vector $c=(n,n-1,\ldots,1)$.
\end{theorem}

\cref{thm:bip-is-directionally-simple} shows that $Q_w$ is always directionally simple, in \cref{sec:monotone} we will determine when $Q_w$ is in fact simple.

\subsection{$h$-vectors of directionally simple polytopes}
The \emph{f-vector} of a polytope $Q \subset \R^d$ is the tuple $f(Q)=(f_0,\ldots,f_d)$ where $f_i$ is the number of $i$-dimensional faces of $Q$. The \emph{h-vector} $h(Q)$ is defined by the equality of polynomials
\begin{equation}
\label{eq:f-and-h-vectors}
\sum_{i=0}^d f_i(x-1)^i = \sum_{k=0}^d h_k x^k.
\end{equation}

\begin{prop}
\label{prop:dir-simple-h-vec}
Let $Q \subset \R^d$ be directionally simple with respect to the generic cost vector $c$, with $h$-vector $h(Q)=(h_0,\ldots,h_d)$. Then for all $k=0,\ldots,d$ the entry $h_k$ is the number of vertices of $Q$ with out-degree exactly $k$ in $G_c(Q)$.
\end{prop}

\begin{remark}
One implication of \cref{prop:dir-simple-h-vec} is that $h_i \geq 0, \forall i$. This by itself is already a very special property of directionally simple polytopes; indeed $h$-vectors of non-simple polytopes are rarely considered, because they are rarely positive or otherwise interesting.
\end{remark}

For $u \in S_n$, write $\asc(u)$ for the number $n-1-|D_R(u)|$ of right ascents of $u$. \cref{cor:h-vec-of-bip} below is an extension to $Q_w$ of the kind of interpretation for $h$-vectors of \emph{simple} generalized permutohedra given by Postnikov--Reiner--Williams \cite{postnikov-reiner-williams}. 

\begin{cor}
\label{cor:h-vec-of-bip}
Let $(h_0,h_1,\ldots)$ be the $h$-vector of $Q_w$, then for all $k$ we have:
\[
h_k = \left| \{ z \in \Top_w([e,w]) \mid \asc(z)=k\} \right|.
\]
\end{cor}

As explained in \cite{lee-poincare}, the $h$-vector of $Q_w$ also gives the Poincar\'{e} polynomial of the toric variety $Y_w$, so \cref{cor:h-vec-of-bip} gives a new formula for that invariant. We can also resolve an open problem raised in \cite{lee-survey}:

\begin{prop}[Resolves Problem 6.1 of \cite{lee-survey}]
\label{prop:smooth-if-palindromic}
The variety $Y_w$ is smooth if and only if its Poincar\'{e} polynomial is palindromic.
\end{prop}

\section{Vertex-degree monotonicity}
\label{sec:monotone}

In \cref{sec:lattice} we applied properties of the relation $c \xdashrightarrow{u} d$ to prove that $P_w$ is a lattice. It is possible to develop and use more refined information about the relation $c \xRightarrow{u} d$ to prove that vertex-degrees of $Q_w$ are monotonic with respect to the partial order $\leq_w$, but we lack the space to do this here. As an application, we resolve a conjecture of Lee--Masuda--Park \cite{lee-conjecture} characterizing smooth generic torus orbit closures in Schubert varieties.

Write $\deg_w(\bs{u})$ for the number of edges of $Q_w$ incident to the vertex $\bs{u}$.

\begin{theorem}
\label{thm:degree-monotonicity}
Let $w \in S_n$. If $u \leq_w v$ then $\deg_w(\bs{u}) \leq \deg_w(\bs{v})$.
\end{theorem}

\cref{thm:degree-monotonicity} will follow from the stronger \cref{thm:injection} below.

\begin{cor}
\label{cor:simple-conjecture}
Let $w \in S_n$, then the polytope $Q_w$ is simple if and only if it is simple at the vertex $\bs{w}$. 
\end{cor}
\begin{proof}
It is clear from \cref{prop:edges-from-E} and the definition of $E_w(e)$ that $Q_w$ is always simple at the vertex $\bs{e}$. Thus if $Q_w$ is also simple at $\bs{w}$, \cref{thm:degree-monotonicity} implies that it is simple at every vertex.
\end{proof}

\cref{cor:simple-conjecture} resolves Conjecture 7.17 of Lee--Masuda \cite{lee-conjecture}. As described there, \cref{cor:simple-conjecture} has the following geometric interpretation.

\begin{cor}
\label{cor:smooth-conjecture}
Let $Y_w$ be a generic torus orbit closure in the Schubert variety $X_w\coloneqq \overline{BwB/B}$, then $Y_w$ is smooth if and only if it is smooth at the torus fixed point $wB$.
\end{cor}


Write $c \xLeftrightarrow{u} d$ if $c \xLeftarrow{u} d$ or $c \xRightarrow{u} d$ (note that we never have both $c \xLeftarrow{u} d$ and $c \xRightarrow{u} d$).

\begin{theorem}
\label{thm:injection}
Let $w \in S_n$ and suppose $u \lessdot_w v = tu$ with $c \xLeftrightarrow{u} d$, then there is a unique edge of $E_w(v)$ described by $c \xLeftrightarrow{v} d$ or $t(c) \xLeftrightarrow{v} t(d)$. Moreover, the map $\ph:E_w(u) \to E_w(v)$ sending the edge $c \xLeftrightarrow{u} d$ to the corresponding edge of $E_w(v)$ is an injection.
\end{theorem}

\cref{thm:degree-monotonicity} follows from \cref{thm:injection} since, by \cref{prop:edges-from-E} we have $\deg_w(\bs{u})=\left| E_w(u) \right|$ for all $u \preceq w$.


\acknowledgements{I thank Lauren Williams, Alex Postnikov, Nathan Reading, Patricia Hersh, Chris Fraser, Grant Barkley, Allen Knutson, Vic Reiner, and Richard Stanley for helpful conversations.}

%% 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}
