%% 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]{FPSAC2025}
\articlenumber{8}
%% 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}
\appto\bibfont{\setlength{\emergencystretch}{.5em}}

\usepackage{color}
%\usepackage{hyperref}
%\usepackage[capitalize, nameinlink, noabbrev, nosort]{cleveref}


%\theoremstyle{definition}
\newtheorem{Thm}{Theorem}[section]
\newtheorem{theorem}[Thm]{Theorem}
\newtheorem{lemma}[Thm]{Lemma}
\newtheorem{corollary}[Thm]{Corollary}
\newtheorem{proposition}[Thm]{Proposition}
\newtheorem{conjecture}[Thm]{Conjecture}

\theoremstyle{definition}
\newtheorem{example}[Thm]{Example}
\newtheorem{definition}[Thm]{Definition}
\newtheorem{remark}[Thm]{Remark}
\newcounter{Prb}
\newtheorem{problem}[Prb]{Problem}

\newcommand{\MSB}[1]{\textcolor{blue}{[MSB: #1]}}
\newcommand{\MS}[1]{\textcolor{blue}{[MS: #1]}}

\DeclareMathOperator{\interior}{int}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\supR}{supR}
\DeclareMathOperator{\Grid}{Grid}
\DeclareMathOperator{\Fl}{Fl}
%\DeclareMathOperator{\rCorner}{rc}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\HH}{\mathbb{H}}
\newcommand{\mcc}{\mathcal{C}}
\newcommand{\AR}{\operatorname{AR}}
\newcommand{\bip}[1]{\mathcal{P}_{#1}}
\newcommand{\momentbp}[1]{\widetilde{\mathcal{P}}_{#1}}
\newcommand{\twist}[1]{\widetilde{#1}}
\newcommand{\untwist}[1]{\widehat{#1}}
\newcommand{\Perm}{\operatorname{Perm}_n}
\def\wo{w_\circ}
\def\lin{\lambda}
\def\hgt{h}
\def\cp{P}
\def\pbolic^#1{^{<#1>}}
\def\bw{\mathbf{w}}
\def\bc{\mathbf{c}}
\def\bq{\mathbf{q}}
\def\bp{\mathbf{p}}
\def\bu{\mathbf{u}}
\def\vl#1{v_{(#1)}}
\def\supp_#1^#2{\supR(#1,#2)}
\def\hc{h^c}
\def\rib_#1{\rho_{#1}}
\def\grid_#1{\Grid(#1)}
\def\path{L}
\def\skew{\nu}
\newcommand{\rich}[1]{\mathcal{R}_{#1}}
%\def\rc_#1{\rCorner(#1)}
\newcommand{\GHV}{\textcolor{blue}{Cool Variety }}
\newcommand{\Hess}[1]{\operatorname{Hess}(#1)}


\DeclareMathOperator{\conv}{conv}



%% define your title in the usual way
\title[]{Permutahedral subdivisions and class formulas from Coxeter elements}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author[]{\texorpdfstring{Allen Knutson\addressmark{1}, Mario Sanchez\addressmark{1,2}, \and Melissa Sherman-Bennett\thanks{\href{mailto:mshermanbennett@ucdavis.edu}{mshermanbennett@ucdavis.edu}. MSB was partially supported by NSF Award No. 2103282 and 2349015.}\addressmark{3}}{Allen Knutson, Mario Sanchez, and Melissa Sherman-Bennett}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Cornell University \\ \addressmark{2}Institute for Advanced Study\\ \addressmark{3}Department of Mathematics, UC Davis}

%% 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{The Bruhat interval polytope $\mathcal{P}_{u,v}$ is the convex hull of the Bruhat interval $[u,v]$ in $S_n$, where each permutation $z$ is interpreted as a vector $(z(1), \dots, z(n)) \in \mathbb{R}^n$. One example is the permutahedron, which is $\mathcal{P}_{e,w_{\circ}}$. We explore the combinatorics of regular subdivisions of the permutahedron into Bruhat interval polytopes. In particular, we identify $2^{n-2}$ \emph{finest} such subdivisions, one for each Coxeter element of $S_n$. For each subdivision, we provide an explicit height vector and determine exactly the constituent Bruhat interval polytopes. We also obtain an algebro-geometric counterpart of these subdivisions: for each Coxeter element $c \in S_n$, we obtain a formula for the class of the permutahedral variety as a sum of Richardson classes, where the terms in the sum exactly correspond to maximal polytopes in the subdivision. We further obtain formulas for the cohomology class of more general subvarieties of $G/B$ which include Hessenberg varieties.}

%% 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, flag Dressian, permutahedron, Richardson variety}

%% 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, giveninits]{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

\section{Introduction}

The permutahedron is the convex hull of the permutation vectors $\{(w(1), \dots, w(n)): w \in S_n\}$ in $\RR^n$. It is the moment map image of both the complete flag variety $\Fl_n$ and the \emph{permutahedral variety} $\overline{Tx}$, the closure of a generic torus orbit in $\Fl_n$. The permutahedron has appeared widely in combinatorics and in combinatorial algebraic geometry. For example, the permutahedral variety has played a key role in the Hodge theory of matroids. 

\emph{Bruhat interval polytopes} are a natural generalization of the permutahedron. Introduced by Kodama--Williams \cite{KW15}, the Bruhat interval polytope $\bip{u,v}$ is the convex hull of the permutations in the Bruhat interval $[u,v]$. The permutahedron is $\bip{e, \wo}$. Bruhat interval polytopes are examples of \emph{flag matroid polytopes}, and $\momentbp{u, v}:=\bip{\wo v^{-1},\wo u^{-1}}$ is the moment map image of the Richardson variety $\rich{u,v} \subset \Fl_n$. Their combinatorial properties have been studied in e.g. \cite{BEW24,GH24,LMP21,TW15}.

\subsection{Main results}

The first main result of this extended abstract (\Cref{thm:subdivision}) concerns the combinatorics of regular subdivisions of the permutahedron $\bip{e, \wo}$ into Bruhat interval polytopes. For each Coxeter element $c \in S_n$, we define an explicit height function $\hc$ on the vertices of $\bip{e, \wo}$ (\Cref{def:height-from-c}). We show that the regular subdivision induced by $\hc$ is exactly the decomposition
\begin{equation}\label{eq:subdiv}\bip{e, \wo} = \bigcup_{\substack{{w\colon \ell(wc)=}\\{\ell(w)+\ell(c)}}} \momentbp{w, wc}.
\end{equation}
We also show that these subdivisions are \emph{finest}, and discuss the numerology of the maximal cells. We obtain similar results for the type B permutahedron as well.

The second main result (\Cref{thm:class-formula}) concerns the geometry of the permutahedral variety, and mirrors Equation \eqref{eq:subdiv}. For each Coxeter element $c \in S_n$, we show that the class of the permutahedral variety is a sum of Richardson classes
\begin{equation}\label{eq:class-formula}
[\overline{Tx}] = \sum_{\substack{{w\colon \ell(wc)=}\\{\ell(w)+\ell(c)}}} [\rich{w,wc}].\end{equation}
In fact, this equation is a special case of a formula for a more general class of subvarieties of $G/B$ which includes the Hessenberg varieties, see \ref{thm:class-formula-general}.

\subsection{Scientific context}
The subdivisions of the permutahedron studied here are examples of regular subdivisions of a flag matroid polytope (the permutahedron) into flag positroid polytopes (Bruhat interval polytopes). See \Cref{ssec:rel-to-matroid-polytopes}. Such subdivisions are known to be in correspondence with the cones of a polyhedral fan, the \emph{positive flag Dressian}, which is also the positive tropicalization of $\Fl_n$ \cite{B23,JLLO23}. Regular matroidal subdivisions of matroid polytopes have been the focus of substantial interest in the past two decades, as have the ``positive'' and ``flag'' variants of this setup\footnote{We direct the reader to \cite{BEW24} for a more comprehensive history and references.}. Heuristically, the ``positive'' variants exhibit surprisingly nice behavior compared to the general matroid version \cite{SW21,BEW24}. Much of the work on these objects has concerned the structure of the parametrizing polyhedral fans; the combinatorics of e.g. which polytopes appear together in a subdivision remains quite mysterious. The finest subdivisions found here constitute a first investigation of this question in the ``positive flag'' case. We note that in just the ``positive'' case, there is a family of finest positroidal subdivisions of the hypersimplex indexed by Catalan objects, whose combinatorics is completely understood. We view our finest Bruhat interval subdivisions of the permutahedron, indexed by Coxeter elements, as roughly analogous.

Our results generalize results of \cite{HHMP19}, who proved \eqref{eq:subdiv} in the special case of a ``standard'' Coxeter element $c=s_{n-1} \dots s_{1}= n1 23\dots (n-1)$ via a connection to Gelfand--Tsetlin polytopes. In this special case, \eqref{eq:class-formula} can be deduced from \cite{AT10}. When $c=s_{n-1} \dots s_{1}$, each of the Bruhat interval polytopes $\momentbp{w,wc}$ in \eqref{eq:subdiv} is combinatorially a cube. This cubical subdivision of $\bip{e,\wo}$ was utilized in \cite{NT23Re} to provide a combinatorial interpretation of a $q$-analogue of Postnikov's mixed Eulerian numbers. Another perspective on the relationship between \eqref{eq:subdiv} and \eqref{eq:class-formula} in the $c=234\dots n 1$ case was given in \cite{Lian24}, which showed that there is a degeneration of the permutahedral variety $\overline{Tx}$ to the union $\cup \rich{w,wc}$ which occurs inside the flag variety $\Fl_n$. We speculate that such a degeneration exists for arbitrary $c$, and in arbitrary type.

%We note that the result on subdivisions and the result on class formulas are proved separately, using combinatorics and convex geometry for the former and degenerations of double Schubert varieties for the latter. However, \eqref{eq:subdiv} and \eqref{eq:class-formula} together suggest that for each Coxeter element $c$, there should be a degeneration of $\overline{Tx}$ to the union $\cup \rich{w,wc}$ which occurs entirely inside $G/B$. This degeneration has been found for a single choice of $c=s_1s_2 \dots s_{n-1}$ in \cite{Lian24}.

\section{Subdivisions from Coxeter elements}
\subsection{Combinatorial background}

We use the notation $[n]:=\{1,2, \dots, n\}$. For a permutation $z \in S_n$, both $z(i)$ and $z_i$ are the image of $i$, and $z[1\colon i]:=\{z(1), \dots, z(i)\}$. The simple transposition exchanging $i$ and $i+1$ is $s_i$.
A \emph{reduced word} for $z \in S_n$ is an expression $z=s_{i_1} s_{i_2} \cdots s_{i_{\ell}}$ where $\ell:= \ell(z)$ is minimal. We call $\ell(z)$ the \emph{length} of $z$. A product $uw$ is \emph{length-additive} if $\ell(uw)=\ell(u) + \ell(w)$.
For $u,v \in S_n$, $u \leq v$ in the Bruhat order if any reduced expression for $v$ contains a reduced expression for $u$ as a subword. Intervals in Bruhat order are denoted $[u, v] :=\{z \in S_n : u \leq z \leq v\}$. The longest permutation is $\wo:i \mapsto n-i+1$. We define $\twist{w}:= \wo w^{-1}$ and $\untwist{w}:= w^{-1} \wo$. These operations are involutive anti-automorphisms of the Bruhat order.

\begin{definition}[\cite{KW15}] Let $u \leq v$. The \emph{Bruhat interval polytope} $\bip{u,v}$ is the polytope 
\[\bip{u,v}:= \conv\{(z(1), z(2), \dots, z(n)): z \in [u,v]\} \subset \RR^n.\]
The \emph{twisted Bruhat interval polytope} $\momentbp{u,v}$ is the polytope
\[\momentbp{u,v}:= \conv\{(\twist{z}(1), \twist{z}(2), \dots, \twist{z}(n)): z \in [u,v]\} \subset \RR^n.\]
\end{definition}
The set of Bruhat interval polytopes and the set of twisted Bruhat interval polytopes is the same; the only difference is how each polytope is labeled by an interval. In particular, $\momentbp{u,v}= \bip{\twist{v}, \twist{u}}$. %While the definition of twisted Bruhat interval polytope may look less natural, it will prove useful later.
The Bruhat interval polytope $\bip{e, \wo}$ is the \emph{permutahedron}, which is the convex hull of all permutations. We note that the vertex set of $\bip{u,v}$ is the interval $[u,v]$, and every face of $\bip{u,v}$ is itself a Bruhat interval polytope \cite[Theorem 4.1]{TW15}. 

%We will be interested in \emph{regular subdivisions} of the permutahedron $\bip{e, \wo}$ into Bruhat interval polytopes.

\begin{definition} Let $P \subset \RR^d$ be a polytope with vertices $v_1, \dots, v_r$, and let \[ h:\{v_1, \dots, v_r\} \to \RR \] be a \emph{height vector}. We write $v_i^h:= (v_i, h(v))$ for the \emph{lifted vertex}, which is a point in $\RR^d \times \RR$. The lifted polytope is 
\[P^h:= \conv\{v_i^h: i=1, \dots, r\} \subset \RR^d \times \RR.\]
A \emph{lower face} of $P^h$ is a face which minimizes a linear functional of the form $\langle (x, 1), - \rangle$.
The \emph{regular subdivision of $P$ induced by $h$}, also called the \emph{$h$-subdivision of $P$}, is the collection of polytopes
\[\{\conv\{v_i\}_{i \in I} \subset P: \conv\{v_i^h\}_{i \in I} \text{ is a lower face of }P^h\}.\]
Each polytope in the collection is called a \emph{cell} of the subdivision. Cells are partially ordered by inclusion. A regular subdivision of the permutahedron $\bip{e, \wo}$ is a regular \emph{Bruhat interval subdivision} if all cells are Bruhat interval polytopes.
\end{definition}



\subsubsection{Relation to matroidal subdivisions, Dressians, tropical Grassmannians}\label{ssec:rel-to-matroid-polytopes}

Before stating our results regarding Bruhat interval subdivisions, we give additional context for the reader familiar with matroid theory. See \cite{BEW24} for additional details. %The twisted Bruhat interval polytope $\momentbp{u,v}$ is the moment map image of the Richardson variety $R_{u,v} \subset \Fl_n$ (see \Cref{sec:class-formulas}). 

The twisted Bruhat interval polytope $\momentbp{u,v}$ is the \emph{flag matroid polytope} of the flag matroid $M_{u,v}:=(M_{u,v}^1, \dots, M_{u,v}^{n-1})$, where $M_{u,v}^i$ is the matroid with bases $\{z[1\colon i]: z \in [u,v]\}$. The matroid polytope of the constituent matroid $M_{u,v}^i$ is 
\[\conv\{e_{z[1\colon i]} : z \in [u,v]\} \subset \RR^n\]
where for $I \subset [n]$, $e_I = \sum_{i \in I} e_i$ is the indicator vector of $I$. We have that $\momentbp{u,v}$ is the Minkowski sum of the matroid polytopes of $M_{u,v}^1, \dots, M_{u,v}^{n-1}$. Each of the matroids $M_{u,v}^i$ is a \emph{positroid}, meaning that $M_{u,v}^i$ can be realized by a $i \times n$ matrix with nonnegative maximal minors. The flag matroids $M_{u,v}$ are exactly the \emph{flag positroids}, meaning they are the only flag matroids which can be realized by an $n \times n$ matrix with nonnegative \emph{flag minors}.

The permutahedron $\bip{e, \wo}$ is the flag matroid polytope of the \emph{uniform flag matroid}, meaning the constitutent matroids $M_{e, \wo}^i$ are all uniform. Thus, a regular Bruhat interval subdivision of $\bip{e, \wo}$ is a regular flag-positroidal subdivision of the uniform flag matroid polytope. The height vectors $h$ giving rise to such subdivisions form a polyhedral fan called the \emph{positive flag Dressian} \cite{JLLO23}, which is equal to the \emph{positive tropical flag variety} \cite{JLLO23,B23}. There is a bijective correspondence between cones of the positive flag Dressian\footnote{Technically, one can endow the positive flag Dressian with a number of different fan structures. Here, we choose the secondary fan structure.} and regular Bruhat interval subdivisions of $\bip{e, \wo}$. Containment of cones corresponds to coarsening of subdivisions. We note that, while \cite{B23} gives a parametrization of the positive flag Dressian, very little is known about its fan structure---such as the number of rays or maximal cones---or about which Bruhat interval polytopes form regular Bruhat interval subdivisions. 


%Finally, we note that the analogue of the positive flag Dressian for regular flag-positroidal subdivisions of more general flag positroid polytopes was studied in \cite{BEW24}. 

\subsection{Regular Bruhat interval subdivisions from Coxeter elements}
In this subsection, we define a height vector $\hc$ for each Coxeter element $c \in S_n$ and state our main result on the combinatorics of the $\hc$-subdivision of $\bip{e, \wo}$.

\begin{definition}
A permutation $c\in S_n$ is a \emph{Coxeter element} if it has a reduced expression in which each simple transposition appears exactly once.
\end{definition}

\begin{example}
For $S_4$, the Coxeter elements are $s_1 s_2 s_3$, $s_3 s_2 s_1$, $s_1 s_3 s_2= s_3 s_1 s_2$ and $s_2 s_1 s_3=s_2 s_3 s_1$. 
\end{example}

It is well-known that $S_n$ has $2^{n-2}$ Coxeter elements. We will define a height function on $S_n$, i.e. on the vertices of $\bip{e, \wo}$, using a Coxeter element. We first need the notion of rightmost subexpressions.

\begin{definition}
	Let $\bw=s_{i_1} \dots s_{i_r}$ be a word (not necessarily reduced) in the simple transpositions of $S_n$. A \emph{subexpression} for $v$ in $\bw$ is an expression for $v$ of the form $v=s_{h_1}^v \dots s_{h_r}^v$ where $s_{h_i}^v \in \{e, s_{h_i}\}$. The set of indices $i \in [r]$ where $s_{h_i}^v \neq e$ is the \emph{support} of the subexpression. The \emph{rightmost subexpression}\footnote{Also called the \emph{positive distinguished subexpression} for $v$ in the literature.} for $v$ is constructed using a greedy procedure, moving from right to left, as follows: set  $\vl{r+1}=v$. If $\vl{j+1}$ is already determined, then $\vl{j}$ is equal to either $\vl{j+1}$ or $\vl{j+1}s_{i_{j}}$, whichever is smaller in the Bruhat order. In the first case, $s_{i_j}^v=e$; in the second, $s_{i_j}^v=s_{i_j}$. See \Cref{ex:height}. %We denote by $\supp_v^{\bw}$ the support of the rightmost expression for $v$ in $\bw$.
\end{definition}

% \begin{remark}
% The rightmost subexpression for $v$ in $\bw$ is indeed the ``rightmost'' reduced subexpression for $v$; among all subexpressions with support of size $\ell(v)$, it is the subexpression whose support is colexicographically largest\footnote{A subset $\{a_1< a_2 < \dots < a_r\}$ is larger than $\{b_1 < \dots < b_r\}$ in colexicographic order if there is some $m\in [r]$ such that $a_p= b_p$ for $p >m$ and $a_m>b_m$.}.
% \end{remark}

%Denote by $S_n\pbolic^{i}:=\{w \in S_n: ws_j>w \text{ for } j \neq i\}$ the maximal quotient of $S_n$ corresponding to $i$. For $w \in S_n$, denote by $w\pbolic^{i} \in S_n\pbolic^{i}$ the minimum length coset representative of $w(S_i \times S_{n-i})$ in $S_n/(S_i \times S_{n-i})$. 
For $I \subset [n]$, let $v^I$ be the permutation obtained by putting the elements of $I$ in increasing order, followed by the complement in increasing order. %In other words, $w\pbolic^{i}$ is the projection of $w$ to the maximal quotient indexed by $i$. 
Recall that $\twist{w}:= \wo w^{-1}$ and $\untwist{w}:= w^{-1}\wo$.

\begin{definition}\label{def:height-from-c}
	%\MSB{This is the word theoretic def of the height, which is not actually what I used to prove things, but should be equivalent.} 
	Let $c \in S_n$ be a Coxeter element and fix a word $\bc$ for $c$. Let $\bc^m=s_{i_1} \cdots s_{i_r}$, where $m$ is large enough that $\bc^m$ contains a subexpression for $\wo$. Weight each letter of $\bc^m$ according to which copy of $\bc$ it is in: for $j \in [r]$, 
	$\wt(j):=\#\{k\in [j+1, r]: s_{i_k}=s_{i_j}\}.$
    The weight of a subexpression of $\bc^m$ is the sum of weights of its support.
	Given $I \subset[n]$, we define $\wt(I)$ to be the weight of the rightmost subexpression for $v^I$ in $\bc^m$.
	%\[\wt(I):= \wt(\text{rightmost subexp. for } w^I \text{ in }\bc^N)\]
	%where the sum is over the support of the rightmost subexpression for $w^I$ in $\bc^N$. 
    Finally, we define
	\begin{equation}\label{eq:hc-def}
		\hc(w):=\sum_{i=1}^{n-1} \wt(\untwist{w}[1\colon i]) \quad \text{or equivalently}\quad \hc(\twist{w}):=\sum_{i=1}^{n-1} \wt({w}[1\colon i]).
	\end{equation}
\end{definition}

\begin{example}\label{ex:height}
Let $\bc=s_1s_2s_3$, and $\bc^m=s_1s_2s_3s_1s_2s_3s_1s_2s_3$. The weights of the letters are $222111000$. Consider $w=3412$ so $\twist{w}=2143$. 
From the table below, we see $\hc(\twist{w})=1+2+0=3$.
%\MSB{Original example had a bunch of typos, so changed to a new example}

\begin{center}
\renewcommand{\arraystretch}{1.5}
    \begin{tabular}{|c|c|c|c|c|}
        $i$ & $I=w[1\colon i]$ & $v^I$ & rightmost subexp. for $v^I$ in $\bc^m$ & $\wt(I)$ \\
                \hline
        $1$ & \{3\} & 3124 & $s_1s_2s_3s_1\boxed{s_2}s_3\boxed{s_1}s_2s_3$ & $1+0=1$ \\
        \hline
        $2$ & \{3,4\} & 3412 & $s_1s_2s_3s_1\boxed{s_2}\boxed{s_3}\boxed{s_1}\boxed{s_2}s_3$ & $1+1+0+0=2$ \\
        \hline
        $3$ & \{1,3,4\}   & 1342 & $s_1s_2s_3s_1s_2s_3s_1\boxed{s_2}\boxed{s_3}$ & $0+0=0$\\
        \hline
        % \hline
        % $1$ & \{2\} & 2134 & $s_1s_2s_3s_1s_2s_3\boxed{s_1}s_2s_3$ & $0$ \\
        % \hline
        % $2$ & \{2,4\} & 2413 & $s_1s_2s_3s_1s_2\boxed{s_3}\boxed{s_1}\boxed{s_2}s_3$ & $1+1+0=2$ \\
        % \hline
        % $3$ & \{1,2,4\}   & 1243 & $s_1s_2s_3s_1s_2s_3s_1s_2\boxed{s_3}$ & 0\\
    \end{tabular}
\end{center}
\end{example}

\begin{remark}
Recall from \Cref{ssec:rel-to-matroid-polytopes} that $\bip{e, \wo}$ is the Minkowski sum of uniform matroid polytopes, also called hypersimplices, whose vertices are the indicator vectors $e_I$. In effect, \Cref{def:height-from-c} defines a height function on vertices of hypersimplices, where the height of $e_I$ is $\wt(I)$. Then $\hc$ is the height function on the vertices of $\bip{e, \wo}$ induced by writing each vertex as a sum of hypersimplex vertices and then taking the sum of heights.
\end{remark}

The following is the main theorem of this section.

\begin{theorem}\label{thm:subdivision}
	Let $c\in S_n$ be a Coxeter element and let $c^*:= \wo c \wo$. Then the subdivision of $\bip{e, \wo}$ induced by the height function $\hc:S_n \to \RR$ is a finest regular Bruhat interval subdivision of $\bip{e, \wo}$. The maximal cells of this subdivision are
	\[\{\bip{u, c^*u}: c^* u \text{ length-additive}\} =\{\momentbp{w, wc}: wc \text{ length-additive}\}. \]
 The dimension $i$ cells are 
 \[\{\momentbp{p,q}: [p, q] \subset [w, wc] \text{ for some $w$ with $wc$ length-additive},~\ell(q)-\ell(p)= i\}.\]
\end{theorem}

To prove \Cref{thm:subdivision}, we show via careful analysis of $\hc$ that each $\momentbp{w,wc}$ lifts to a hyperplane, and that the lifted polytopes satisfy the \emph{local folding condition} of \cite[Theorem 2.3.20]{DLRS-triang-book}.

\begin{example}\label{ex:max-cells} For $c=s_1s_2s_3=2341$, the maximal cells in the $\hc$-subdivision of the permutahedron $\bip{1234,4321}$ are
\[\momentbp{1234,2341},~ \momentbp{1324,3241},~\momentbp{1243,2431},~\momentbp{1423,4231},~ \momentbp{1342,3421},~\momentbp{1432,4321}.\]
For $c=s_1s_3s_2=2413$, the maximal cells in the $\hc$-subdivision of the permutahedron $\bip{1234,4321}$ are
\[\momentbp{1234,2413},~\momentbp{1324,3412},~ \momentbp{2314, 3421},~ \momentbp{1423, 4312},~\momentbp{2413, 4321}. \]
\end{example}

We obtain the following immediate corollary, utilizing the correspondence between finest regular Bruhat interval subdivisions and the maximal cones of the positive flag Dressian (cf. \Cref{ssec:rel-to-matroid-polytopes}).

\begin{corollary}
    For each Coxeter element $c \in S_n$, the vector $\hc$ lies in a maximal cone in the positive flag Dressian, endowed with secondary fan structure. Thus, there are at least $2^{n-2}$ maximal cones.
\end{corollary}


Our results extend to the type $B$ and type $C$ variants of Bruhat interval polytopes via a folding argument. As this result does not depend on the weight lattice, it suffices to state it for type $C$. Let $S_n^{\pm}$ be the signed permutation group, acting by reflections on $\RR^n$. The group $S_n^{\pm}$ is the type $BC$ Coxeter group, and so is equipped with the (strong) Bruhat order. Given an interval $[u,v]$ in $S_n^{\pm}$, the \emph{type $C$-Bruhat interval polytope} $\momentbp{u,v}^C$ is the polytope
 \[\momentbp{u,v}^C = \operatorname{conv}\left( w \cdot (n,n-1,\ldots,1) : w \in [u,v]\right). \]

\begin{theorem}
Let $c \in S_n^{\pm}$ be a Coxeter element. Then, there is a height function $h_c: S_{n}^{\pm} \to \RR$ such that the corresponding regular subdivision of $\momentbp{e,w_0}^C$ is a finest regular subdivision into type $C$ Bruhat interval polytopes with maximal cells
\[\{\momentbp{w, wc}^C: wc \text{ length-additive}\}. \]
\end{theorem}

\subsection{Numerology of maximal cells}

In this section, we discuss the number of maximal cells in the $\hc$-subdivision of $\bip{e, \wo}$. As we will see, this number varies depending on the choice of $c$.

\begin{remark} Regular Bruhat interval subdivisions of $\bip{e, \wo}$ are the ``flag'' analogue of regular positroidal subdivisions of the hypersimplex $\Delta_{k,n}$. In the latter context, all finest subdivisions have the same $f$-vector, and in particular have $\binom{n-2}{k}$ maximal cells. In \cite{BEW24}, it was shown for $n=4$ that, in contrast, finest regular Bruhat interval subdivisions of $\bip{e, \wo}$ need not have the same number of maximal cells. The results of this section show that this continues for arbitrary $n$.
\end{remark}

We use $\le_L$ to denote the left weak order on $S_n$. Recall that $u \le_L v$ if and only if $v$ has a reduced expression which has a reduced expression for $u$ as a suffix. Equivalently, $u \le_L v$ if and only if $v$ can be written as $v=xu$ where $xu$ is length-additive. Left weak order can also be rephrased in terms of right inversions.

\begin{definition}
    For $u \in S_n$, let $T_R(u):= \{(a,b): a<b, u_a > u_b\}$ be the set of \emph{right inversions} of $u$. We define $\succcurlyeq_u$ to be the poset on [n] defined by $a \succcurlyeq_u b$ if $(a,b) \in T_R(u)$ or if $a=b$.
\end{definition}

It is straightforward to verify that $\succcurlyeq_u$ is indeed a partial ordering on $[n]$. It follows from \cite[Proposition 3.1.3]{BB05} that for $u \in S_n$
\[[u, \wo]_L= \{v \in S_n: v(a)>v(b) \text{ for all }a \neq b \text{ with }a \succcurlyeq_u b \}\]
where the set on the right is exactly the set of linear extensions of $\succcurlyeq_u$.



The following lemma is straightforward.

\begin{lemma} \label{lem:cells-bijection-weak-order-interval} Let $c \in S_n$ be a Coxeter element.
    Then 
    \begin{align*}
        \{v: c \le_L v\} &\to \{\momentbp{w,wc}: wc \text{ length-additive}\}\\
        v &\mapsto \momentbp{vc^{-1}, v}
    \end{align*}
    is a bijection. That is, the maximal cells of the $\hc$-subdivision of $\bip{e, \wo}$ are in bijection with the left weak order interval $[c, \wo]_{L}$ and the linear extensions of $\succcurlyeq_c.$
\end{lemma}

Using this lemma, we obtain a count for the number of maximal cells in the subdivisions of \Cref{thm:subdivision}.

\begin{corollary}
        Let $c \in S_n$ be a Coxeter element. The number of maximal cells in the $\hc$-subdivision of $\bip{e,wo}$ is the number of linear extensions of $\succcurlyeq_c$.
\end{corollary}

% We now more explicitly describe the poset $\succcurlyeq_c$ for $c$ a Coxeter element. Recall that $i$ is an \emph{excedance} of a permutation $u$ if $u_i>i$.

% \begin{proposition}
%     Let $c \in S_n$ be a Coxeter element and $\rib_c$ the corresponding ribbon strip (cf. \Cref{def:skew-shape-btw-paths}).
%     \begin{itemize}
%         \item The Hasse diagram of $\succcurlyeq_c$ may be obtained as follows. Place vertex $i$ on step $i$ of the bottom boundary. For each box $b$ of $\rib_c$, extend a ``hook'' which goes horizontally to the right from $b$ and vertically down from $b$. Say the horizontal leg of the hook hits step $i$ of the bottom boundary and the vertical leg hits step $j$. Then $b$ contributes an edge $i \to j$ to the Hasse diagram.
%         \item The maximal elements of $\succcurlyeq_c$ are the excedances of $c$; the minimal elements are the non-excedances. In particular, every maximal chain consists of two elements.
%     \end{itemize}
% \end{proposition}

% \begin{proof}
%    For the first item: recall that inversions of $c$ correspond to the crosses in any wiring diagram of $c$. Interpreting $\rib_c$ as a wiring diagram, there is one cross in each box $b$. We are interested in right inversions, so to determine the right inversion corresponding to $b$, we need to record the right endpoints of the wires that cross in $b$. This is exactly the $i$ and $j$ specified in the proposition statement.

%    For the second item: The excedances of $c$ are the labels of the vertical steps on the lower boundary of $\rib_c$; the non-excedances are the labels of the horizontal steps. From the above item, it is clear that no edges of the Hasse diagram point towards a vertical step, and no edges point away from a horizontal step.
% \end{proof}

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.9\textwidth]{Hasse-ex}
    \caption{On the left, the Hasse diagram of $\succcurlyeq_c$ when $c=s_5s_7s_6s_1s_2s_4s_3=23614857$. On the right, the general shape of the Hasse diagram of $\succcurlyeq_c$, which is a zig-zag (in blue) with claws attached to the peaks and valleys. The numbers $a_1, \dots, a_r$ are arbitrary nonnegative integers.}
    \label{fig:Hasse-ex}
\end{figure}

See \Cref{fig:Hasse-ex} for an example of the poset $([n],\succcurlyeq_c)$, as well as their general ``shape''. Note that the posets $([n],\succcurlyeq_c)$ are height 2 tree posets on $[n]$. As a result, the number of linear extensions may be computed using a polynomial-time algorithm \cite{Atk90}.

\begin{example} For an $\hc$-subdivision of $\bip{e, \wo}$, the number of maximal cells achieves its maximum when $c=s_1s_2 \dots s_{n-1}= 234\cdots n 1$ or its inverse. In this case, $([n],\succcurlyeq_c)$ is a \emph{claw}, and has $(n-1)!$ linear extensions. This subdivision was first studied by \cite{HHMP19}, who showed that each maximal cell is combinatorially a cube.

The number of maximal cells achieves its minimum when $c=\prod_{i \text{ even}} s_i \prod_{i \text{ odd}} s_i$ or its inverse. In this case, $([n],\succcurlyeq_c)$ is a \emph{zig-zag poset}. Linear extensions are in bijection with ``up/down'' permutations and are counted by Euler numbers (see \Cref{tab:Euler-vs-factorial}).
\end{example}


\begin{table}[h]
    \centering
    \begin{tabular}{c|c|c|c|c|c|c|c|}
        $n$ & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
        \hline
        $(n-1)!$ & 2 & 6 & 24 & 120 & 720 & 5040 & 40320\\
        \hline
        Euler number & 2 & 5 & 16 & 61 & 272 & 1385 & 7936 \\
        \hline
    \end{tabular}
    \caption{Ranging over all Coxeter elements $c$ in $S_n$, the largest possible number of maximal cells in an $\hc$-subdivision of $\bip{e, \wo}$ is $(n-1)!$. The smallest possible number of maximal cells is the $n$th Euler number. The two numbers are contrasted above.}
    \label{tab:Euler-vs-factorial}
\end{table}



\section{Formulas for the Permutahedral class from Coxeter elements}\label{sec:class-formulas}
In this section, we turn to our second main result on formulas for the permutahedral class.

 Let $G$ be a simply connected semisimple algebraic group with Borel subgroup $B$, opposite Borel $B_-$, maximal torus $T$, and Weyl group $W$. In type A, $G=SL_n$, $B$ is the subgroup of upper triangular matrices, $B_-$ the lower triangular matrices, $T$ is the diagonal matrices, and $W=S_n$. The quotient $G/B$ is the (generalized) flag variety. The flag variety admits two well-known decompositions into $B$-orbits and $B_-$-orbits:
 \[G/B= \bigsqcup_{w \in W} BwB/B = \bigsqcup_{w \in W} B_- w B/B.\]
 The \emph{Richardson variety} $\rich{u,v}$ is the closure of the intersection $B_- u B/B \cap BvB/B$.
 
 
 The (Coxeter) Bruhat interval polytope $\momentbp{u,v}$ is the moment map image of the Richardson variety $\rich{u,v} \subset G/B$. The Coxeter permutahedral variety is the torus-orbit closure $\overline{Tx}$ of a generic point $x \in G/B$ and its moment map image is the Coxeter permutahedron.

%There is a general philosophy that coherent subdivisions of polytopes are reflecting degenerations of the corresponding toric varieties. Our subdivisions suggest that there should be a family of formulas, parameterized by Coxeter elements, expressing the class of the permutahedral variety in $H^*(G/B)$ in terms of the classes of certain Richardson varieties. In Section (), we prove results of this type for a more general class of varieties.


%%%%%%%%%%
%Possible Double Schubert
%%%%%%%%%
Given an element $v \in W$ and $X \in T$, we define the subvariety\footnote{We note that the choice of $X$ does not change the isomorphism class of the variety.} $\mathcal{H}_v(X)$ of $G/B$ by
 \[\mathcal{H}_v(X) = \{ hB \; : \; h^{-1}Xh \in \overline{BvB}\}. \]
 The most general form of our cohomological result calculates the cohomology class of $\mathcal{H}_v(X)$.
 
 
In type $A_n$, when $v$ is a \emph{dominant} permutation, $\mathcal{H}_v(X)$ is a regular semisimple Hessenberg variety, whose definition we now recall. 
Given a function $h:[n] \to [n]$ with the property $h(i) \geq i$ and a linear operator $X$, the type A \textbf{Hessenberg variety} $\Hess{X,h}$ is the subvariety of the flag variety given by
 \[\Hess{X,h} = \{ F_{\bullet} \in \operatorname{Fl}_n \; : \; XF_i \subseteq F_{i+1} \text{ for $i=1,2,\ldots,n$}\}.\] 
When $h$ is the function $h(i) = \operatorname{min}\{i+1,n\}$ and $X$ is semisimple and regular, $\Hess{X,h}$ is the permutahedral variety.
Hessenberg varieties have appeared in many contexts and are important, for instance, in the study of the chromatic symmetric function of special graphs. See the survey \cite{AT20} for more information. %\MS{What about other types? What exactly are the conditions on $X$ that we need here?}



Our proof uses the  \textbf{double Schubert varieties} $\mathbf{\Omega}_w$ defined by Anderson in \cite{And07}. This is the subvariety of $G/B \times G/B$ given by
\begin{align*}
    \mathbf{\Omega}_w &:= \overline{G_\Delta \cdot (wB,B)} = \{(gB,hB)\colon h^{-1}g \in \overline{BwB} \}
\end{align*}
There are two key ideas in our proof. The first is that $\mathcal{H}_v(X)$ is the projection onto the second factor of $G/B \times G/B$ of the transverse intersection $(X \times 1) \mathbf{\Omega}_{e} \cap \mathbf{\Omega}_v.$
The second is that the double Schubert $\mathbf{\Omega}_w$ degenerates to $\bigcup \{\overline{B_-uB/B} \times \overline{BvB/B}: v^{-1}u \leq w\}$. Combining these ideas together gives our main second result.

\begin{theorem}\label{thm:class-formula-general}
    We have
     \[[\mathcal{H}_v(X)] = \sum_{\substack{u \in W \\ uv^{-1} \text{length-additive}}} [\rich{u,uv^{-1}}] \]
    in $H^*(G/B)$. %\MS{Do we need $X \in T$ here or just that it is regular?}
\end{theorem}

When $v$ is a Coxeter element, $\mathcal{H}_v(X)$ is the permutahedral variety $\overline{Tx}$ which gives as a corollary the geometric counterpart to \Cref{thm:subdivision}.

\begin{theorem}\label{thm:class-formula}
    Let $c$ be a Coxeter element in $W$. Let $T$ be the torus in $G$ and let $x$ be a generic point in $G/B$. For a pair of permutations $u \leq v$ in $W$, let $\rich{u,v}$ denote the corresponding Richardson variety.
    
    Then we have
     \[[\overline{Tx}] = \sum_{\substack{w \in W \\ \ell(wc) = \ell(w) + \ell(c)}} [\rich{w,wc}]. \]
\end{theorem}

When $c=s_{n-1} s_{n-2} \dots s_{1}=n12\dots (n-1)$ is a ``standard'' Coxeter element, this recovers the formula for the permutahedral variety in \cite{AT10}.

\begin{remark}
    The class of a regular Hessenberg variety $\operatorname{Hess}(X,h)$ does not depend on the choice of regular $X$ \cite{ADHM18}. Hence, this also gives formulas for the class of the Peterson variety.
\end{remark}





\acknowledgements{MSB would like to thank Alejandro Morales for helpful conversations regarding linear extensions of tree posets.}

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