%% 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{36}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amssymb}
\usepackage{tikz-cd}
\usepackage{tikz}
\usepackage{array}
\usetikzlibrary{decorations.markings}
\usetikzlibrary{patterns}
\usepackage{enumitem}
\usepackage{amsfonts}
% \usepackage[utf8]{inputenc}
\usepackage{subcaption}
\usepackage{graphicx}
\usepackage{caption}
\usepackage[export]{adjustbox}
\usepackage{mathdots}
\usepackage{comment}
\usepackage{hyperref}
\usepackage{cleveref}
\usetikzlibrary{calc, shapes, backgrounds,arrows,positioning,decorations.pathmorphing}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}


\theoremstyle{definition}
\newtheorem{ex}[theorem]{Example}
\newtheorem{quest}[theorem]{Question}
\newtheorem{prob}[theorem]{Problem}
\newtheorem{defin}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lem-def}[theorem]{Lemma/Definition}

\theoremstyle{plain}
\newtheorem{claim}[theorem]{Claim}

\captionsetup[subfigure]{labelformat=simple}
\renewcommand\thesubfigure{(\Alph{subfigure})}

\makeatletter
% \newcommand\circled[1]{%
%   \mathpalette\@circled{#1}%
% }
% \newcommand\@circled[2]{%
%   \tikz[baseline=(math.base)] \node[draw,circle,inner sep=1pt] (math) {$\m@th#1#2$};%
% }
% \newcommand{\gr}{\mathrm{Gr}}
% \newcommand{\RNum}[1]{\uppercase\expandafter{\romannumeral #1\relax}}
\makeatother
\newcommand{\shiliang}[1]{{\color{blue} \sf Shiliang: [#1]}}
\newcommand{\jiyang}[1]{{\color{red} \sf Jiyang: [#1]}}
\newcommand{\yibo}[1]{{\color{orange} \sf Yibo: [#1]}}

% \DeclareMathOperator{\Red}{Red}
% \DeclareMathOperator{\Inv}{Inv}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\depth}{depth}
\DeclareMathOperator{\codim}{codim}


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

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



%% define your title in the usual way
\title[]{Quantum Bruhat Graphs and Tilted Richardson Varieties}

%% 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{Jiyang Gao\thanks{\href{mailto:jgao@math.harvard.edu}{jgao@math.harvard.edu}.% JG was partially supported by NSF Grant DMS-2152991
}\addressmark{1}, Shiliang Gao\thanks{\href{mailto:shiliang.gao@cornell.edu}{shiliang.gao@cornell.edu}. SG was partially supported by NSF MSPRF under grant No. DMS-2402285}\addressmark{2}, \and Yibo Gao\thanks{\href{mailto:gaoyibo@bicmr.pku.edu.cn}{gaoyibo@bicmr.pku.edu.cn}. YG was partially supported by NSFC Grants 12471309}\addressmark{3}}{Jiyang Gao, Shiliang Gao, and Yibo Gao}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Harvard University, Cambridge, MA \\ \addressmark{2}Department of Mathematics, Cornell University, Ithaca, NY \\ \addressmark{3} Beijing International Center for Mathematical Research, Peking University, Beijing.}

%% 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 quantum Bruhat graph is a weighted directed graph on a finite Weyl group first defined by Brenti--Fomin--Postnikov. It encodes quantum Monk's rule and can be utilized to study the $3$-point Gromov--Witten invariants of the flag variety. In this paper, we provide a combinatorial formula for the minimal weights between any pair of permutations on the quantum Bruhat graph, and consequently obtain an Ehresmann-like characterization for the tilted Bruhat order. We define the tilted Richardson variety $\mathcal{T}_{u,v}$, with a stratification that gives a geometric meaning to intervals in the tilted Bruhat order. We prove some fundamental geometric properties of this new family of varieties, including their dimensions, closure relations, irreducibility, and a Deodhar-like decomposition. We demonstrate their equivalence to the two-point curve neighborhoods of Schubert varieties $X_u$ and $X^v$ in the minimal degree, and relate their cohomology classes to quantum products of Schubert classes.
}


% The quantum Bruhat graph, initially introduced by Brenti, Fomin, and Postnikov, is a weighted directed graph defined on finite Weyl groups. It serves as a valuable tool for exploring the quantum cohomology ring of the flag variety. In this presentation, we present a combinatorial formula for the minimal weights between any pair of permutations within the quantum Bruhat graph. Furthermore, for an ordered pair of permutations u and v, we introduce the tilted Richardson variety T_{u,v}, demonstrating its equivalence to the two-pointed curve neighborhood of opposite Schubert varieties X_u and X^v in the minimal degree d. We establish a Deodhar-like decomposition for tilted Richardson varieties, leveraging it to prove several results. This is joint work with Shiliang Gao and Yibo Gao.

% The quantum Bruhat graph is a weighted directed graph on a finite Weyl group first defined by Brenti--Fomin--Postnikov. It encodes quantum Monk's rule and can be utilized to study the $3$-point Gromov--Witten invariants of the flag variety. In this paper, we provide an explicit formula for the minimal weights between any pair of permutations on the quantum Bruhat graph, and consequently obtain an Ehresmann-like characterization for the tilted Bruhat order. Moreover, for any ordered pair of permutations $u$ and $v$, we define the tilted Richardson variety $\mathcal{T}_{u,v}$, with a stratification that gives a geometric meaning to intervals in the tilted Bruhat order. We provide a few equivalent definitions to this new family of varieties that include Richardson varieties, and establish some fundamental geometric properties including their dimensions and closure relations.}

%% put your French abstract here, or comment this out if you don't have one


%% put your keywords here, or comment this out if you don't have them yet
\keywords{quantum Bruhat graphs, quantum Schubert calculus, Richardson varieties.}

%% 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{fpsac-2025.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}\label{sec:intro}
Hilbert's fifteenth problem, Schubert calculus, concerns the full flag variety \[\mathrm{Fl}_n=\{0\subset V_1\subset \cdots\subset V_{n-1}\subset \mathbb{C}^n\:|\: \dim V_i=i\text{ for }i=1,\ldots,n-1\}\]
and its Schubert decomposition $\mathrm{Fl}_n=\bigsqcup_{w\in S_n} X_w^{\circ}$. The cohomology ring $H^*(\mathrm{Fl}_n)$ has a linear basis given by the Schubert varieties $\{[X_w]\}_{w\in S_n}$. The corresponding structure constants $c_{u,w}^v$'s, also referred to as the \emph{generalized Littlewood--Richardson numbers}, are known to be nonnegative integers from transversal intersection. It has been a long standing open problem to find a combinatorial interpretation of these numbers. The study of flag varieties, Schubert varieties and the structure constants is central in algebraic geometry and algebraic combinatorics.

The small quantum cohomology ring $QH^*(\mathrm{Fl}_n)$ is a deformation of the cohomology ring. %It shows up naturally in theoretical physics. 
The structure constants of $QH^*(\mathrm{Fl}_n)$ with respect to the Schubert basis are known to be the \emph{3-point genus-0 Gromov--Witten invariants}. They extend the generalized Littlewood--Richardson numbers in the ``quantum" direction. 
% more quantum stuff

The problem of multiplying Schubert classes in $QH^*(\mathrm{Fl}_n)$ can be naturally encoded via the \emph{quantum Bruhat graph}, first defined by Brenti--Fomin--Postnikov \cite{BFP-tilted-Bruhat} and utilized by Postnikov \cite{Postnikov-quantum-Bruhat-graph}. The quantum Bruhat graph can be seen as a graphical representation of the \emph{quantum Monk's rule} and enjoys very rich algebraic and combinatorial properties. In particular,  the minimal degree $q^d$ that appears in the quantum product $[X_u]\star [X^v]$ is the weight of any shortest directed path from $u$ to $v$ \cite{Postnikov-quantum-Bruhat-graph}. The quantum Bruhat graph directly gives rise to the \emph{tilted Bruhat order} \cite{BFP-tilted-Bruhat}. These are our main combinatorial objects of interest for this paper.


%\textbf{Main result 1:} 
Our first set of main results are about the weights in the quantum Bruhat graph. Specifically, we provide:
% weights in the quantum Bruhat graph:
\begin{enumerate}
\item An explicit combinatorial formula for the minimal weight between any pair of permutations $u$ to $v$ (\Cref{thm:weight-distance}).
\item An Ehresmann-like characterizaiton for the tilted Bruhat order (\Cref{thm:tilted-criterion}).
\end{enumerate}


We remark that \Cref{thm:weight-distance} was also obtained via a combination of Postnikov's toric Schur polynomials \cite{Postnikov-quantum-Schur} on the quantum cohomology ring of the Grassmannian, and a geometric result by Buch--Chung--Li--Mihalcea \cite{bclm2020-quantumK} (see also \cite{FW}). Our proof is independent and purely combinatorial. 

While weights on the quantum Bruhat graph encode important information in the quantum cohomology of the flag variety, we present a novel geometric interpretation of intervals in the tilted Bruhat order with a more classical flavor. For any pair of permutations $u,v\in S_n$, we define the \emph{tilted Richardson variety} $\mathcal{T}_{u,v}$ and the \emph{open tilted Richardson variety} $\mathcal{T}_{u,v}^{\circ}$ (\Cref{def:main}), which reduces to the well-known (open) Richardson variety if $u\leq v$ in the Bruhat order. 

% \

% \textbf{Main result 2:} equivalent definitions of the (open) tilted Richardson variety using
% \begin{enumerate}
% \item rank conditions;
% \item cyclically rotated Richardson varieties in the Grassmannian;
% \item multi-Pl\"ucker coordinates ;
% \item intersection of tilted Schubert cells.
% \end{enumerate}

The tilted Richardson varieties are our central geometric objects of study. %Their geometric properties resemble those of Richardson varieties. 
%However, since an analogue of Schubert varieties do not exist in our setting, most of the analysis requires new insights and techniques. 
Our second set of results concern geometric properties of tilted Richardson varieties (\Cref{thm:geometric}). We prove:
\begin{enumerate}
\item a stratification $\mathcal{T}_{u,v}=\bigsqcup_{[x,y]\subseteq[u,v]}\mathcal{T}_{x,y}^{\circ}$ that relates the tilted Bruhat order;
\item $\dim\mathcal{T}_{u,v}=\dim\mathcal{T}_{u,v}^{\circ}=$ the length of any shortest paths from $u$ to $v$ in the quantum Bruhat graph;
\item the closure relation $\overline{\mathcal{T}_{u,v}^{\circ}}=\mathcal{T}_{u,v}$;
\item irreducibility of $\mathcal{T}_{u,v}^\circ$ and $\mathcal{T}_{u,v}$.
\end{enumerate}

Deodhar \cite{Deodhar} introduced his decomposition of open Richardson varieties as a tool for understanding \emph{Kazhdan--Lusztig polynomials} \cite{KL79}. As a key ingredient in proving irreducibility of the tilted Richardson varieties, we introduce a decomposition of $\mathcal{T}_{u,v}^\circ$, generalizing Deodhar's decomposition. The decomposition also allows us to compute the $\mathbb{F}_q$-point count of open tilted Richardson varieties, a generalization of R-polynomials. More specifically, we give:
\begin{enumerate}
    \item A decomposition of the (open) tilted Richardson varieties into simple pieces of the form $(\mathbb{C}^*)^a\times \mathbb{C}^b$, extending Deodhar's decomposition (\Cref{thm:deodhar});
    \item A formula for the $\mathbb{F}_q$-point counts of open tilted Richardson varieties using Hecke algebras (\Cref{thm:hecke}).
\end{enumerate}

In \cite{curveneighborhood}, Buch--Chaput--Mihalcea--Perrin introduced the \emph{two-point curve neighborhoods} $\Gamma_{d}(X_u,X^v)$ in their study of the quantum cohomology ring $QH^*(\mathrm{Fl}_n)$ (see also \cite{BCMP}). They encode information about the Gromov--Witten invariants of degree $d$, but little in the way of explicit descriptions of the curve neighborhoods was known \cite{LiMihalcea, BM15}. We present the first concrete combinatorial description in the minimal degree case by establishing a connection with tilted Richardson varieties. We show that:
\begin{enumerate}
    \item The tilted Richardson variety $\mathcal{T}_{u,v}$ is equal to the minimal degree two-point curve neighborhood $\Gamma_{d_{\text{min}}}(X_u,X^v)$ (\Cref{thm:Gamma=T});
    \item The cohomology classes $[\mathcal{T}_{u,v}] = [\Gamma_{d_{\text{min}}}(X_u,X^v)]\in H^*(\mathrm{Fl}_n)$ are equal to the minimal quantum degree component in the quantum product $[X_u]\star [X^v]$ (\Cref{thm:cohomology}).
\end{enumerate}


\section{Minimal weights in the quantum Bruhat graphs}

Let $S_n$ be the symmetric group on $n$ elements, generated by the \emph{simple transpositions} $\{s_1,\dots,s_{n-1}\}$.
We typically write a permutation $w$ using its \emph{one-line} notation $w_1w_2\cdots w_n$. For $w\in S_n$, let $\ell(w)$ be the \emph{Coxeter length} of $w$, which is the smallest $\ell$ such that $w=s_{\alpha_1}\cdots s_{\alpha_{\ell}}$ is a product of $\ell$ simple transpositions. Let $t_{ij}=(i\ j)$ be a transposition in $S_n$.

\begin{defin}[\cite{BFP-tilted-Bruhat}]\label{def:quantum-bruhat-graph}
The \textbf{quantum Bruhat graph} $\Gamma_n$ is a weighted directed graph on $S_n$ with the following two types of edges:
\[
\begin{cases}
w\rightarrow wt_{ij}\text{ of weight }1&\text{ if }\ell(wt_{ij})=\ell(w)+1,\\
w\rightarrow wt_{ij}\text{ of weight }q_iq_{i+1}\cdots q_{j-1}&\text{ if }\ell(wt_{ij})=\ell(w)+1-2(j-i),
\end{cases}
\]
where $1\leq i<j\leq n$. Write $\wt(w\rightarrow wt_{ij})\in\mathbb{Z}[q_1,\ldots,q_{n-1}]$ for the weight.
\end{defin}

The quantum Bruhat graph for $n=3$ is shown in \Cref{fig:quantum-Bruhat-graph-n=3}.
\begin{figure}[!ht]
\centering
\begin{tikzpicture}[scale=0.8]
\coordinate (a) at (0,-2);
\coordinate (b) at (1.73205080757,-1);
\coordinate (c) at (1.73205080757,1);
\coordinate (d) at (0,2);
\coordinate (e) at (-1.73205080757,1);
\coordinate (f) at (-1.73205080757,-1);
\node at (a) {$\bullet$};
\node[below] at (a) {$123$};
\node at (b) {$\bullet$};
\node[right] at (b) {$132$};
\node at (c) {$\bullet$};
\node[right] at (c) {$312$};
\node at (d) {$\bullet$};
\node[above] at (d) {$321$};
\node at (e) {$\bullet$};
\node[left] at (e) {$231$};
\node at (f) {$\bullet$};
\node[left] at (f) {$213$};
\draw[postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (a) -- (b);
\draw[postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (a) -- (f);
\draw[postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (b) -- (c);
\draw[postaction={decorate,decoration={markings,mark=at position 0.4 with {\arrow{>}}}}] (b) -- (e);
\draw[postaction={decorate,decoration={markings,mark=at position 0.4 with {\arrow{>}}}}] (f) -- (c);
\draw[postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (f) -- (e);
\draw[postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (e) -- (d);
\draw[postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (c) -- (d);
\draw[blue, postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (b) to[bend left=40] (a);
\node[blue] at (1.4,-1.9) {$q_2$};
\draw[blue, postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (c) to[bend left=40] (b);
\node[blue] at (2.4,0) {$q_1$};
\draw[blue, postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (d) to[bend left=40] (c);
\node[blue] at (1.4,1.9) {$q_2$};
\draw[blue, postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (d) to[bend right=40] (e);
\node[blue] at (-1.4,1.9) {$q_1$};
\draw[blue, postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (e) to[bend right=40] (f);
\node[blue] at (-2.4,0) {$q_2$};
\draw[blue, postaction={decorate,decoration={markings,mark=at position 0.5 with {\arrow{>}}}}] (f) to[bend right=40] (a);
\node[blue] at (-1.4,-1.9) {$q_1$};
\draw[blue, postaction={decorate,decoration={markings,mark=at position 0.4 with {\arrow{>}}}}] (d) to (a);
\node[blue] at (0.4,0.8) {$q_1q_2$};
\end{tikzpicture}
\caption{Quantum Bruhat graph $\Gamma_3$ (unlabeled edges have weight $1$)}
\label{fig:quantum-Bruhat-graph-n=3}
\end{figure}

\begin{defin}
For a directed path $P:w^{(0)}\rightarrow w^{(1)}\rightarrow\cdots\rightarrow w^{(k)}$ in $\Gamma_n$, we say that $P$ has length $k$, with weight 
\[
 \wt(P):= \prod_{i=1}^k\wt(w^{(i-1)}\rightarrow w^{(i)}).
\]
For $u,v\in S_n$, let $\ell(u,v)$ be the length of a shortest path from $u$ to $v$.
\end{defin}
Postnikov \cite{Postnikov-quantum-Bruhat-graph} established nice properties regarding weights of shortest paths. Write $q^d$ for $q_1^{d_1}\cdots q_{n-1}^{d_{n-1}}$. 
\begin{lemma}[\cite{Postnikov-quantum-Bruhat-graph}]\label{lem:shortest-length-equals-weight}
For any $u,v\in S_n$, all shortest paths from $u$ to $v$ have the same weight $q^{d_{u,v}}$. Moreover, the weight of any path from $u$ to $v$ is divisible by $q^{d_{u,v}}$. %In addition, if a path from $u$ to $v$ has weight $q^{d_{u,v}}$, it must be a shortest path. 
\end{lemma}

\begin{remark}
    The weight $q^{d_{u,v}}$ is the unique minimum quantum degree that appears in the quantum product of two Schubert classes $\sigma_u\star\sigma_{w_0v}$ in the quantum cohomology ring $QH^\ast(\mathrm{Fl}_n)$ \cite{Postnikov-quantum-Bruhat-graph}.
    We further discuss this connection to $QH^\ast(\mathrm{Fl}_n)$ in \Cref{sec:QH}.
\end{remark}
% \Cref{lem:shortest-length-equals-weight} is essentially saying that shortest length paths are precisely minimal weight paths. We remark that the last sentence from \Cref{lem:shortest-length-equals-weight} is not explicitly written done in \cite{Postnikov-quantum-Bruhat-graph}, but follows directly from the proof of Lemma~1 of \cite{Postnikov-quantum-Bruhat-graph}, with much of the main content established in Lemma~6.7 of \cite{BFP-tilted-Bruhat}. From now on, write $q^{d(u,v)}=q_1^{d_1(u,v)}q_2^{d_2(u,v)}\cdots q_{n-1}^{d_{n-1}(u,v)}$ for the minimal weight from $u$ to $v$, where $d_{u,v}$ is a $(n-1)$-tuple.
% \begin{ex}
% Let $u=321$ and $v=213$. There are two shortest paths from $u$ to $v$ of length $2$: $321\rightarrow 231\rightarrow 213$ and $321\rightarrow 123\rightarrow 213$. We see that both paths have the same weight $q_1q_2$ so $d(321,213)=(1,1)$. It is straightfroward to check that any other paths from $u$ to $v$ have weight divisible by (and not equal to) $q_1q_2$. 
% \end{ex}


Our first theorem provides an explicit formula that computes the minimal weight $q^{d_{u,v}}$ for any pair of permutation $u,v\in S_n$. 
\begin{defin}\label{def:up-down-path}
For $A,B\subset[n]$ with $|A|=|B|$, we construct a lattice path $P(A,B)$ starting at $(0,0)$ and ending at $(n,0)$ with $n$ steps as follows. For each $i=1,\ldots,n$, the $i^{th}$ step is
\begin{itemize}
\item an upstep $(1,1)$ if $i\in A$ and $i\notin B$,
\item a downstep $(1,-1)$ if $i\notin A$ and $i\in B$,
\item a horizontal step $(1,0)$ if $i\in A\cap B$ or $i\notin A\cup B$. 
\end{itemize}
Define its \textbf{depth}, denoted as $\depth(A,B)$, to be the largest number $y\geq0$ such that $P(A,B)$ passes through $(x,-y)$ for some $x$. 
\end{defin}

\begin{theorem}\label{thm:weight-distance}
Let $u,v\in S_n$. All shortest paths from $u$ to $v$ in the quantum Bruhat graph $\Gamma_n$ have weight $q^{d_{u,v}}=q_1^{d_1}\cdots q_{n-1}^{d_{n-1}}$ where $d_k=\depth(u[k],v[k])$. Here, $w[k]:=\{w_1,\ldots,w_k\}$.
\end{theorem}

\begin{ex}\label{ex:lattice-path-PAB}
Consider $u=7364152$ and $v=2513746$ in $S_7$. To figure out $d_4(u,v)$, we need to construct a lattice path $P_4(u[4],v[4])$ with upsteps $u[4]=\{3,4,6,7\}$ and downsteps $v[4]=\{1,2,3,5\}$, as shown in \Cref{fig:lattice-path-PAB} with $\depth(u[4],v[4])=2$. In the end, we arrive at $q^{d_{u,v}}=q_1q_2q_3^2q_4^2q_5q_6$.
\begin{figure}[!ht]
\centering
\begin{tikzpicture}[scale=0.7]
\node at (0,0) {$\bullet$};
\node at (1,-1) {$\bullet$};
\node at (2,-2) {$\bullet$};
\node at (3,-2) {$\bullet$};
\node at (4,-1) {$\bullet$};
\node at (5,-2) {$\bullet$};
\node at (6,-1) {$\bullet$};
\node at (7,0) {$\bullet$};
\draw(0,0)--(2,-2)--(3,-2)--(4,-1)--(5,-2)--(7,0);
\draw[dashed](0,0)--(7,0);
\node (d) at (8.5,-1) {$\mathrm{depth}=2$};
\draw[->] (d)--(8.5,0);
\draw[->] (d)--(8.5,-2);
\node[above] at (0.6,-0.7) {$1$};
\node[above] at (1.6,-1.7) {$2$};
\node[above] at (2.5,-2.1) {$3$};
\node[above] at (3.4,-1.7) {$4$};
\node[above] at (4.6,-1.7) {$5$};
\node[above] at (5.4,-1.7) {$6$};
\node[above] at (6.4,-0.7) {$7$};
\end{tikzpicture}
\caption{The lattice path $P(u[4],v[4])$}
\label{fig:lattice-path-PAB}
\end{figure}
\end{ex}
% \begin{ex}
% Consider $u=7364152$ and $v=2513746$ in $S_7$. We need to figure out $d_k(u,v)$ for $k=1,\ldots,n-1$. For $k=1$, $u[1]=\{7\}$ and $v[1]=\{2\}$ so we need to construct a lattice path with an upstep at position $7$ and a downstep at position $2$. This lattice path has depth $1$, meaning that $d_1(u,v)=1$. We continue this procedure for all $k$'s. For example, at $k=4$, the lattice path $P(u[4],v[4])$ is discussed in \Cref{ex:lattice-path-PAB} with $d_4(u,v)=2$. In the end, we arrive at $q^{d(u,v)}=q_1q_2q_3^2q_4^2q_5q_6$.
% \end{ex}

\begin{defin}[\cite{BFP-tilted-Bruhat}]\label{def:tilted-Bruhat-order}
For $u\in S_n$, define the \textbf{tilted Bruhat order} $D_u$ to be the graded partial order on $S_n$ such that $w\leq_u v$ if
\begin{equation}\label{eqn:tilted-order-def}
    \ell(u,w)+\ell(w,v) = \ell(u,v).
\end{equation}
Equivalently, $w\leq_{u} v$ if there is a shortest path in the quantum Bruhat graph from $u$ to $v$ that passes through $w$. For $w\leq_u v$, define the \textbf{tilted Bruhat interval} to be 
\[[w,v]_u = \{x\in S_n:w\leq_u x \leq_u v\}.\]
\end{defin}

The tilted Bruhat order $D_{132}$ is shown in \Cref{fig:tilted-132}.
\begin{figure}[!ht]
\centering
\begin{tikzpicture}[scale=0.8]
\node at (0,0) {$\bullet$};
\node[below] at (0,0) {$132$};
\node at (-1.6,1) {$\bullet$};
\node[left] at (-1.6,1) {$123$};
\node at (0,1) {$\bullet$};
\node[above] at (0,1) {$231$};
\node at (1.6,1) {$\bullet$};
\node[right] at (1.6,1) {$312$};
\node at (-0.8,2) {$\bullet$};
\node[above] at (-0.8,2) {$213$};
\node at (0.8,2) {$\bullet$};
\node[above] at (0.8,2) {$321$};
\draw(0,0)--(-1.6,1)--(-0.8,2)--(0,1)--(0,0);
\draw(0,0)--(1.6,1)--(0.8,2)--(0,1);
\end{tikzpicture}
\caption{The tilted Bruhat order $D_{132}$}
\label{fig:tilted-132}
\end{figure}

\begin{remark}
    It follows from \eqref{eqn:tilted-order-def} that $[w,v]_u = [w,v]_{u'}$ as long as $w\leq_u v$ and $w\leq_{u'} v$. Since $w\leq_w v$, we omit the subscript and write $[w,v]$ instead of $[w,v]_u$ from now on.
\end{remark}

\begin{remark}
    When $u = id$, the tilted Bruhat order $D_u$ is the strong Bruhat order.%    A special case of the tilted Bruhat order is the strong Bruhat order. This is the case when $u = id$.
\end{remark}

Our second theorem provides a combinatorial criterion for the tilted Bruhat order.
\begin{defin}
For $r\in [n]$, let $\leq_r$ be the \textbf{shifted linear order} on $[n]$ given by $r<_r\cdots <_r n <_r 1 <_r \cdots <_r r-1$. Define the \textbf{shifted Gale order} $\leq_r$ on $\binom{[n]}{k}$ as
%we write 
\[\{a_1 <_r \cdots <_r a_k\}\leq_r \{b_1<_r \cdots <_r b_k\} \iff a_i \leq_r b_i \text{ for all }i\in [k].\]
%for the \emph{shifted Gale order} $\leq_r$.
For a sequence $\mathbf{a}=(a_1,a_2,\dots,a_{n})\in[n]^{n}$, define the \textbf{$\mathbf{a}$-shifted order} $\leq_\mathbf{a}$ on $S_n$ as
\[u\leq_\mathbf{a} v\iff u[k]\leq_{a_k}v[k]\text{ for all }k\in[n].\]
\end{defin}

\begin{theorem}\label{thm:tilted-criterion}
For $u,v,w\in S_n$, the following are equivalent:
\begin{enumerate}
\item $w\leq_u v$;
\item $w\in [u,v]$;
\item for any sequence $\mathbf{a} = (a_1,\dots, a_{n})$ such that $u\leq_\mathbf{a}v$, we have $u\leq_\mathbf{a}w\leq_\mathbf{a}v$;
\item there exists a sequence $\mathbf{a} = (a_1,\dots, a_{n})$ such that $u\leq_\mathbf{a}w\leq_\mathbf{a}v$.
\end{enumerate}
\end{theorem}

\begin{ex}
    Let $u = 132$, $w = 123$, $v = 213$. From \Cref{fig:tilted-132}, we can see $w\leq_u v$. Let $\mathbf{a}=(1,3,1)$, we have $u\leq_\mathbf{a} w\leq_\mathbf{a} v$ since
    \begin{align*}
        &\{1\}\leq_1 \{1\} \leq_1 \{2\} & 
        \{3,1\} &\leq_3 \{1,2\} \leq_{3} \{1,2\} & &[3]\leq_1 [3] \leq_1 [3].
    \end{align*}
    Alternatively, $u\leq_\mathbf{a'} w\leq_\mathbf{a'} v$ also for $\mathbf{a'}=(3,3,2)$ since
    \begin{align*}
        &\{1\}\leq_3 \{1\} \leq_3 \{2\} & 
        &\{3,1\} \leq_3 \{1,2\} \leq_{3} \{1,2\} & &[3]\leq_2 [3] \leq_2 [3].
    \end{align*}
\end{ex}

\section{Tilted Richardson varieties}

Let $G = {GL}_n(\mathbb{C})$ and $B,B_{-}\subset G$ be the Borel and opposite Borel subgroup of $G$ consisting of invertible upper and lower triangular matrices respectively. Let $T=B\cap B_{-}$ be the maximal torus of diagonal matrices in $G$. 

The \emph{complete flag variety} is defined to be $\mathrm{Fl}_n = G/B$. Fixing a basis of $\mathbb{C}^n$, we can identify a point $gB\in G/B$ with a \emph{flag} $F_{\bullet} = 0=F_0\subsetneq F_1 \subsetneq F_2 \subsetneq \cdots \subsetneq F_{n-1}\subsetneq F_n=\mathbb{C}^n$ where $F_k\in\mathrm{Gr}(k,n)$ is the span of the first $k$ column vectors of any $n\times n$ matrix representative $M_F\in gB$.

\begin{defin}\label{def:cyclicinterval}
For $a,b\in [n]$, define the \textbf{cyclic interval} $[a,b)_c:=\{a,\ldots,b-1\}$ if $a\leq b$ and $[a,b)_c:=\{a,\ldots,n\}\cup\{1,\ldots,b-1\}$ if $a>b$. %We can similarly define cyclic intervals $[,]_c$, $(,]_c$ and $[,)_c$.
\end{defin}

Motivated by our characterization of tilted Bruhat order (\Cref{thm:tilted-criterion}), we define the (open) tilted Richardson varieties:
\begin{defin}\label{def:main}
%$Y_{u,v}^{\mathbf{a}}$ that depends on $\mathbf{a}$.
For $S$ any subset of $[n]$, let $\mathrm{Proj}_S:\mathbb{C}^{n}\twoheadrightarrow \mathbb{C}^{|S|}$ be the projection onto the coordinates with indices in $S$. For $u,v\in S_n$ and a sequence $\mathbf{a}$ where $u\leq_\mathbf{a}v$, define the \textbf{tilted Richardson variety} by:
\begin{align}\label{eqn:tiltRich}
    \mathcal{T}_{u,v,\mathbf{a}} = \left\{F_{\bullet} \in \mathrm{Fl}_n:
    \begin{array}{c}
         \dim (\mathrm{Proj}_{[a_i,j)_c}(F_i))\leq \#\{u[i]\cap [a_i,j)_c\},   \\
         \dim (\mathrm{Proj}_{[j,a_{i})_c}(F_i))\leq \#\{v[i]\cap [j,a_i)_c\} 
    \end{array} 
    %\text{ for all }
    \forall i,j\in [n]
     \right\},
\end{align}
and the \textbf{open tilted Richardson variety} $\mathcal{T}_{u,v,\mathbf{a}}^\circ$ by replacing all ``$\leq$" with ``$=$" in \eqref{eqn:tiltRich}.
% \begin{align}\label{eqn:tiltRichOpen}
%     \mathcal{T}_{u,v,\mathbf{a}}^\circ = \left\{F_{\bullet} \in \mathrm{Fl}_n:
%     \begin{array}{c}
%          \dim (\mathrm{Proj}_{[a_i,j)_c}(F_i))= \#\{u[i]\cap [a_i,j)_c\},   \\
%          \dim (\mathrm{Proj}_{[j,a_{i})_c}(F_i))= \#\{v[i]\cap [j,a_i)_c\} 
%     \end{array} 
%     %\text{ for all }
%     \forall i,j\in [n]
%      \right\}.
% \end{align}
% to be:

\end{defin}

\begin{ex}\label{ex:4321-3142} 
Let $u = 4231, v = 3142$ and $\mathbf{a} = (4,2,2,3)$. Then $u\leq_\mathbf{a} v$. In \Cref{fig:rank-ex}, the $\star$ and $\bullet$ represent $u$ and $v$ respectively, and the red horizontal line segment in column $k$ represents the cutoff of $[n]$ under $\leq_{a_k}$ for each $k\in [4]$.

For $F_\bullet \in \mathcal{T}_{u,v,\mathbf{a}}$, there are $8$ rank conditions imposed on $F_2$ as in \eqref{eqn:tiltRich}. These conditions can be interpreted as rank conditions on submatrices of $M_{F}$ in the first two columns with (cyclically) consecutive rows starting or ending at the red line. For example, the condition $\dim(\mathrm{Proj}_{\{1,2,3\}}(F_2))\leq 2 = \#\{v[2]\cap\{1,2,3\}\}$ is interpreted as the rank of the shaded submatrix of $M_F$ in \Cref{fig:4321-3142} being at most $2$, the number of $\bullet$ in said region. The condition $\dim(\mathrm{Proj}_{\{2,3\}}(F_2))\leq 1 = \#\{u[2]\cap \{2,3\}\}$ is the rank of shaded submatrix in \Cref{fig:4321-3142.2} being at most $1$, the number of $\star$ in said region.
\begin{figure}[ht!]
    \centering
\subcaptionbox{$\dim(\mathrm{Proj}_{\{3,4,1\}}(F_2))\leq 2$ \label{fig:4321-3142}}[.4\textwidth]{
    \begin{tikzpicture}[scale = 0.6]
    \fill [green, opacity  = 0.25] (0,3) rectangle (2,4);
    \fill [green, opacity  = 0.25] (0,0) rectangle (2,2);
    \draw (0,0)--(4,0)--(4,4)--(0,4)--(0,0);
    \draw (1,0) -- (1,4);
    \draw (2,0) -- (2,4);
    \draw (3,0) -- (3,4);
    \draw (0,1) -- (4,1);
    \draw (0,2) -- (4,2);
    \draw (0,3) -- (4,3);
    \node at (-0.5,0.5) {$4$};
    \node at (-0.5,1.5) {$3$};
    \node at (-0.5,2.5) {$2$};
    \node at (-0.5,3.5) {$1$};
    \node at (0.5,-0.5) {$1$};
    \node at (1.5,-0.5) {$2$};
    \node at (2.5,-0.5) {$3$};
    \node at (3.5,-0.5) {$4$};
    \node[orange] at (0.5,0.5) {$\star$};
    \node[orange] at (1.5,2.5) {$\star$};
    \node[orange] at (2.5,1.5) {$\star$};
    \node[orange] at (3.5,3.5) {$\star$};
    \node[blue] at (0.5,1.5) {$\bullet$};
    \node[blue] at (1.5,3.5) {$\bullet$};
    \node[blue] at (2.5,0.5) {$\bullet$};
    \node[blue] at (3.5,2.5) {$\bullet$};
    \draw[line width=0.55mm, red] (0,1) -- (1,1);
    \draw[line width=0.55mm, red] (1,3) -- (2,3);
    \draw[line width=0.55mm, red] (2,3) -- (3,3);
    \draw[line width=0.55mm, red] (3,2) -- (4,2);
    \end{tikzpicture}
    }
    %\caption{$u = 4321,v = 3142$}
    %\label{fig:4321-3142}
\subcaptionbox{$\dim(\mathrm{Proj}_{\{2,3\}}(F_2))\leq 1$ \label{fig:4321-3142.2}}[.4\textwidth]{
    \begin{tikzpicture}[scale = 0.6]
    \fill [green, opacity  = 0.25] (0,1) rectangle (2,3);
    \draw (0,0)--(4,0)--(4,4)--(0,4)--(0,0);
    \draw (1,0) -- (1,4);
    \draw (2,0) -- (2,4);
    \draw (3,0) -- (3,4);
    \draw (0,1) -- (4,1);
    \draw (0,2) -- (4,2);
    \draw (0,3) -- (4,3);
    \node at (-0.5,0.5) {$4$};
    \node at (-0.5,1.5) {$3$};
    \node at (-0.5,2.5) {$2$};
    \node at (-0.5,3.5) {$1$};
    \node at (0.5,-0.5) {$1$};
    \node at (1.5,-0.5) {$2$};
    \node at (2.5,-0.5) {$3$};
    \node at (3.5,-0.5) {$4$};
    \node[orange] at (0.5,0.5) {$\star$};
    \node[orange] at (1.5,2.5) {$\star$};
    \node[orange] at (2.5,1.5) {$\star$};
    \node[orange] at (3.5,3.5) {$\star$};
    \node[blue] at (0.5,1.5) {$\bullet$};
    \node[blue] at (1.5,3.5) {$\bullet$};
    \node[blue] at (2.5,0.5) {$\bullet$};
    \node[blue] at (3.5,2.5) {$\bullet$};
    \draw[line width=0.55mm, red] (0,1) -- (1,1);
    \draw[line width=0.55mm, red] (1,3) -- (2,3);
    \draw[line width=0.55mm, red] (2,3) -- (3,3);
    \draw[line width=0.55mm, red] (3,2) -- (4,2);
    \end{tikzpicture}
}
\caption{Rank conditions on $\mathcal{T}_{u,v,\mathbf{a}}$ for $u = 4231$, $v = 3142$, and $\mathbf{a}=(4,2,2,3)$}
\label{fig:rank-ex}    
\end{figure}
\end{ex}

%Indeed, for any $u\leq_{\mathbf{a}}v$, $\dim (\mathrm{Proj}_{[a_i,j)_c}(wB/B)) = \#\{w[i]\cap [a_i,j)_c\}$. Therefore
It follows immediately from \Cref{thm:tilted-criterion} that the set of $T$-fixed points on $\mathcal{T}_{u,v,\mathbf{a}}$ is 
\begin{equation}\label{eqn:T-fixed}
    \{e_w:=wB/B\in \mathcal{T}_{u,v,\mathbf{a}}\} = [u,v].
\end{equation}
In particular, $e_w\in \mathcal{T}_{u,v,\mathbf{a}}$ is independent of the choice of $\mathbf{a}$. In fact,
\begin{prop}
    $\mathcal{T}_{u,v,\mathbf{a}}$ and $\mathcal{T}_{u,v,\mathbf{a}}^\circ$ are both independent of $\mathbf{a}$ as long as $u\leq_{\mathbf{a}}v$.
\end{prop}
As a result, we omit the index $\mathbf{a}$ and write $\mathcal{T}_{u,v}^\circ$ and $\mathcal{T}_{u,v}$ for the (open) tilted Richardson varieties.


% We can visualize $\mathcal{T}_{u,v}^\circ$ and $\mathcal{T}_{u,v}$ as follows. For any $S\subseteq [n]$, $k\in [n]$ and $M\in \mathrm{Mat}_{n\times n}$, define $r_{S,k}(M)$ to be the rank of the submatrix of $M$ obtained by taking the rows in $S$ and the left $k$ columns. Let $M_F$ be a matrix representative of $F_\bullet$ and pick any $\mathbf{a} = (a_1,\dots, a_{n-1})$ such that $u\leq_{\mathbf{a}}v$. Then
% \begin{align}\label{eqn:Tuvrank}
%     F_\bullet \in \mathcal{T}_{u,v} \iff \begin{cases}
%         \begin{split}
%         r_{[a_i,j]_c,i}(M_F)&\leq r_{[a_i,j]_c,i}(u)\\
%         r_{[j,a_{i}-1]_c,i}(M_F)&\leq r_{[j,a_{i}-1]_c,i}(v)
%     \end{split}
%     \end{cases},\text{ for all }i,j\in [n]
% \end{align}
% and $F_\bullet\in\mathcal{T}_{u,v}^{\circ}$ if we replace ``$\leq$" with ``$=$" in \eqref{eqn:Tuvrank}.


\begin{remark}
    If $u\leq v$ in strong Bruhat order, namely $u\leq_\mathbf{a} v$ where $\mathbf{a} = (1,\dots, 1)$, then $\mathcal{T}_{u,v}^\circ$ and $\mathcal{T}_{u,v}$ are the (open) Richardson variety $\mathcal{R}_{u,v}^\circ$ and $\mathcal{R}_{u,v}$ respectively.
\end{remark}

\begin{remark}
    In \cite{GGG}, we give three other equivalent definitions of the (open) tilted Richardson varieties using cyclically rotated Grassmannian Richardson varieties, vanishing loci of multi-Pl\"ucker coordinates, and intersections of tilted Schubert cells.
\end{remark}


We prove the following geometric properties of the tilted Richardson varieties, analogous to those of the classical Richardson varieties. 

\begin{theorem}\label{thm:geometric}
    For $u,v\in S_n$,
    \begin{enumerate}
        \item[(1)] (stratification) $\mathcal{T}_{u,v} = \bigsqcup_{[x,y]\subseteq [u,v]}\mathcal{T}_{x,y}^\circ$;
        \item[(2)] (dimension) $\dim(\mathcal{T}_{u,v}^\circ) = \dim(\mathcal{T}_{u,v}) = \ell(u,v)$;
        \item[(3)] (closure relation) $\mathcal{T}_{u,v} = \overline{\mathcal{T}_{u,v}^\circ}$;
        \item[(4)] (irreducibility) $\mathcal{T}_{u,v}$ and $\mathcal{T}_{u,v}^\circ$ are irreducible.
    \end{enumerate}
\end{theorem}

\section{Tilted Deodhar decomposition}

% In the study of KL polynomial, an important ingredient is to understand the R-polynomial $R_{u,v}(\mathbb{F}_q)$. In order to compute this polynomial, Deodhar had the idea of splitting the Richardson varieties into simple pieces $D_{\mathbf{u},\mathbf{v}}$ labeled by a reduced word $\mathbf{v}$ and distinguished subword $\mathbf{u}$, such that each simple piece is isomorphic to

In \cite{KL79}, Kazhdan--Lusztig introduced the \emph{Kazhdan--Lusztig R-polynomial} $R_{u,v}(q)$ for $u\leq v$. They are used to give a recursive formula for the \emph{Kazhdan--Lusztig polynomials}. The polynomial $R_{u,v}(q)$ is determined by $\mathbb{F}_q$-point counts on the open Richardson varieties
\[R_{u,v}(q)=\#\mathcal{R}^\circ_{u,v}(\mathbb{F}_q).\]


For any pair of permutations $u,v\in S_n$, we define a generalization called \textbf{tilted R-polynomial} $R^\text{tilt}_{u,v}(q)$, which gives the $\mathbb{F}_q$-point counts on open tilted Richardson varieties
\[R^\text{tilt}_{u,v}(q)=\#\mathcal{T}^\circ_{u,v}(\mathbb{F}_q).\]


To understand $R_{u,v}(q)$, Deodhar \cite{Deodhar} introduced a decomposition of $\mathcal{R}^\circ_{u,v}$ into simple pieces $D_\alpha$ that are isomorphic to $\mathbb{C}^a\times (\mathbb{C}^\ast)^b$. This gives an explicit formula for $R_{u,v}(q)$:

\[\mathcal{R}^\circ_{u,v}=\bigsqcup_\alpha\mathbb{C}^a\times (\mathbb{C}^\ast)^b\implies R_{u,v}(q)=\sum_\alpha q^a(q-1)^b.\]


In this section, we extend Deodhar's decomposition to tilted Richardson varieties
\begin{equation}\label{eqn:deodhar}
    \mathcal{T}_{u,v}^\circ=\bigsqcup_{\mathbf{u}\prec\mathbf{v}}D_{\mathbf{u},\mathbf{v}},
\end{equation}
This decomposition allows us to prove irreducibility of tilted Richardson varieties, and give an explicit formula for the tilted R-polynomials (\Cref{cor:deodhar}).

We now define the \emph{tilted reduced expression} $\mathbf{v}$ and the \emph{distinguished subexpression} $\mathbf{u}$ indexing the pieces in \eqref{eqn:deodhar}.
Let $\mathbf{a}=(a_1,a_2,\dots,a_n)\in[n]^{n}$ be a sequence. Define
\[J_\mathbf{a}=\{j_1>j_2>\cdots> j_t\}:=\{j\in[n]:a_j\neq a_{j+1}\},\quad(a_{n+1}=1).\]

\begin{defin}
    An \textbf{$\mathbf{a}$-tilted reduced expression} $\mathbf{v}$ for $v\in S_n$ is a sequence of black or blue (overlined) simple transpositions, whose product is $v$ and of the form
    \[\mathbf{v}=s_{\alpha_1}s_{\alpha_2}\cdots s_{\alpha_{N_1}}{\color{blue}\overline{s_{\alpha_{N_1+1}}\cdots  s_{\alpha_{N_2}}}} s_{\alpha_{N_2+1}}\cdots s_{\alpha_{N_3}}{\color{blue}\overline{s_{\alpha_{N_3+1}}\cdots s_{\alpha_{N_4}}}}\cdots s_{\alpha_{N_{2t}+1}}\cdots s_{\alpha_N}\]
    satisfying the following properties:
    \begin{enumerate}
        %\item the product $\prod_{\alpha\in \mathbf{w}}s_\alpha=w$;
        \item $\mathbf{v}$ is the concatenation of $2t+1$ subexpressions, alternatively colored black and blue, such that each subexpression is a reduced expression for some permutation;
        \item for all $k\in [t]$, $\alpha_i<j_k$ if $i> N_{2k-1}$;
        %all integers in or after the $k$-th blue subsequence are less than $j_k$, for all $k\in[t]$;
        \item let $v_{(d)}=\prod_{i = 1}^d s_{\alpha_i}$. Then the first $j_k$ entries of $v_{(N_{2k-1})}$ are increasing under the shifted order $<_{a_{j_k+1}}$, and the first $j_k$ entries of $v_{(N_{2k})}$ are increasing under the shifted order $<_{a_{j_{k}}}$, for all $k\in[t]$.
    \end{enumerate}
\end{defin}

%For a tilted reduced expression $\mathbf{v}=s_{\alpha_1}s_{\alpha_2}\cdots s_{\alpha_N}$ for $v$. A \emph{subexpression} $\mathbf{u}$ is  obtained from the reduced expression $\mathbf{v}$ by replacing some of the factors with $1$. Given a subexpression $\mathbf{u}$, set $u_{(d)}$ to be the product of the leftmost $d$ factors in $\mathbf{u}$.

\begin{defin}
Given an $\mathbf{a}$-tilted reduced expression $\mathbf{v} = s_{\alpha_1}s_{\alpha_2}\cdots s_{\alpha_N}$, a \textbf{distinguished subexpression} for $u\in S_n$ is a sequence $\mathbf{u} = u_1\dots u_N$ whose product is $u$ and each factor $u_i\in \{1,s_{\alpha_i},{\color{blue}\overline{s_{\alpha_i}}},{\color{red}\widetilde{s_{\alpha_i}}}\}$ satisfies the following rules:
    \[u_i=\begin{cases}
        1\text{ or }s_{\alpha_i}&\text{ if } s_{\alpha_i} \text{ is black in }\mathbf{v} \text{ and } \ell(u_{(i-1)}s_{\alpha_i},v_{(i)})=\ell( u_{(i-1)},v_{(i-1)}),\\
        {\color{red}\widetilde{s_{\alpha_i}}}&\text{ if } s_{\alpha_i} \text{ is black in }\mathbf{v} \text{ and } \ell(u_{(i-1)}s_{\alpha_i},v_{(i)})>\ell(u_{(i-1)},v_{(i-1)}),\\
        {\color{blue}\overline{s_{\alpha_i}}}&\text{ if } {\color{blue}\overline{s_{\alpha_i}}} \text{ is blue in }\mathbf{v}.
    \end{cases}
    \]
Here we set $u_{(i)}$ to be the product of the leftmost $i$ factors of $\mathbf{u}$. We write $\mathbf{u}\prec \mathbf{v}$ if $\mathbf{u}$ is a distinguished subexpression of $\mathbf{v}$.
    
    % For any subword $R\subseteq \mathbf{v}$ and $i\in [N]$, set 
    % \[R^{(i)} = \prod_{\substack{j\leq i\\j\in R}} s_{\alpha_j}.\]
    % A distinguished subword for $u$ is a subword $R\subseteq \mathbf{v}$ such that 
    % \begin{enumerate}
    %     \item $R^{(N)} = u$, and
    %     \item if $N_{2k-1}<i\leq N_{2k}$ for some $k\in [t]$ or $\ell(R^{(i-1)}s_{\alpha_i},v_{(i)})> \ell(R^{(i-1)}, v_{(i)})$, then $\alpha_i\in R$.
    % \end{enumerate}
    
    
    % and their product is $u$. We denote $\mathbf{u}\prec \mathbf{v}$. 
\end{defin}

% \begin{defin}
%     An \emph{$\mathbf{a}$-tilted reduced word} $\mathbf{w}$ for $w\in S_n$ is a sequence of integers and bars
%     \[\mathbf{w}=\alpha_1\alpha_2\cdots\alpha_{N_1}|\alpha_{N_1+1}\cdots\alpha_{N_2}|\cdots|\alpha_{N_t+1}\cdots\alpha_N\]
%     that satisfies the following properties:
%     \begin{enumerate}
%         \item the product $\prod_{i\in \mathbf{w}}s_i=w$;
%         \item all integers after the $k$-th bar are less than $j_k$, for all $k\in[t]$;
%         \item \shiliang{which one of the following two is better?}
%         \item the sequence between any two adjacent bars (or before the first bar/after the last bar) is a reduced word for some permutation;
%         \item $\alpha_{N_j+1}\dots \alpha_{N_{j+1}}$ is a reduced word of some permutation for all $0\leq j\leq t$, where we set $N_0 = 0$ and $N_{t+1} = N$.
%         \item let $\mathbf{w}_{(k)}$ be the subsequence of $\mathbf{w}$ before the $k$-{th} bar. Then the first $j_k$ entries of $w_{(k)}=\prod_{i\in \mathbf{w}_{(k)}}s_i$ are increasing under the shifted order $<_{a_{j_k}}$
        
%     \end{enumerate}
% \end{defin}
\begin{ex}
    If $v=246513$ and $\mathbf{a}=(5,5,5,1,1,1)$, the set $J_\mathbf{a}=\{3\}$, and an example of an $\mathbf{a}$-tilted reduced expression for $v$ is $\mathbf{v}=s_3s_4s_5s_1s_2s_3s_4s_3{\color{blue}\overline{s_2s_1}}s_1s_2$.
There are $4$ distinguished subexpressions for $u = 512346$:
        \begin{align*}
        \mathbf{u}&= 111111s_4s_3{\color{blue}\overline{s_2s_1}}11 & \mathbf{u}&= 111s_111s_4s_3{\color{blue}\overline{s_2s_1}}1{\color{red}\widetilde{s_2}}\\
        \mathbf{u}&= s_31111{\color{red}\widetilde{s_3}}s_4s_3{\color{blue}\overline{s_2s_1}}11 & 
        \mathbf{u}&= s_311s_11{\color{red}\widetilde{s_3}}s_4s_3{\color{blue}\overline{s_2s_1}}1{\color{red}\widetilde{s_2}}
        \end{align*}
\end{ex}

Unfortunately, we don't know whether $u\leq_\mathbf{a} v$ will ensure the existence of a distinguished subexpression for $u$ in $\mathbf{v}$. This motivates the following Lemma/Definition, which gives a sufficient condition.

%Given $\mathbf{v}$, an $\mathbf{a}$-tilted reduced expression for $v$, if $u$ has a distinguished subexpression in $\mathbf{v}$, it is not necessarily true that $u\leq_\mathbf{a} v$. Moreover, given $u\leq_\mathbf{a} v$ and $\mathbf{a}$ an $\mathbf{a}$-tilted reduced expression for $v$, it is also not necessarily true that there is a distinguished subexpression for $u$. However, the following Lemma/Definition 

\begin{lem-def}
    For any $u,v\in S_n$, there exists $\mathbf{a}$ such that $u\leq_{\mathbf{a}}v$, and $u[k]\leq_{a_{k+1}}v[k]$ for all $k\in [n]$. We say such $\mathbf{a}$ is \textbf{flat}. In this case, any $\mathbf{a}$-tilted reduced expression $\mathbf{v}$ has a distinguished subexpression for $u$. 
\end{lem-def}

For each $j\in[n-1]$, define $y_j(p),x_j(m)$ and $\dot{s}_j\in {GL}_n$ to be
\begin{align*}
    y_j(p)&=\phi_{j}\begin{pmatrix}
             1 & 0\\ p & 1
        \end{pmatrix}, &
    \dot{s}_j(p)&=\phi_{j}\begin{pmatrix}
             0 & -1\\ 1 & 0
        \end{pmatrix}, &
    x_j(m)&=\phi_{j}\begin{pmatrix}
             1 & m\\ 0 & 1
        \end{pmatrix},
\end{align*}
where $\phi_j\left(\begin{smallmatrix}
    a & b\\
    c& d
\end{smallmatrix}\right)$ replaces the $2\times 2$ block of the identity matrix in the $j$ and ($j+1$)-th row/column by $\left(\begin{smallmatrix}
    a & b\\
    c& d
\end{smallmatrix}\right)$. The following is our main theorem of this section.
\clearpage
\begin{theorem}\label{thm:deodhar}
Let $u\leq_\mathbf{a} v$ where $\mathbf{a}$ is flat. Let $\mathbf{v}$ be an $\mathbf{a}$-tilted reduced expression for $v$. Then 
    \[\mathcal{T}^\circ_{u,v}=\bigsqcup_{\mathbf{u}\prec \mathbf{v}}D_{\mathbf{u},\mathbf{v}},\text{ where each }D_{\mathbf{u},\mathbf{v}}\cong (\mathbb{C}^\ast)^{\#1\text{'s in }\mathbf{u}}\times \mathbb{C}^{\#{\color{red}\widetilde{s_{\alpha_i}}}\text{'s in }\mathbf{u}}.\]
    Each tilted Deodhar cell $D_{\mathbf{u},\mathbf{v}}$ for $\mathbf{u}=u_1\cdots u_N\prec \mathbf{v}$ is parametrized by
    \[D_{\mathbf{u},\mathbf{v}}:=\left\{gB=g_1g_2\cdots g_N B\;\middle\vert\begin{aligned}\;g_i&=y_{\alpha_i}(p_i), &\text{if }u_i&=1\\ \;g_i&=\dot{s}_{\alpha_i}, &\text{if }u_i&=s_{\alpha_i} \text{ or }{\color{blue}\overline{s_{\alpha_i}}}\\ \;g_i&=x_{\alpha_i}(m_i)\dot{s}_{\alpha_i}^{-1}, &\text{if }u_i&={\color{red}\widetilde{s_{\alpha_i}}}\end{aligned}\right\}/B.\]
Here $p_i\in \mathbb{C}^\ast$ and $m_i\in \mathbb{C}$ are parameters.
\end{theorem}
    

\begin{cor}\label{cor:deodhar}
    There is a unique tilted Deodhar cell $D_{\mathbf{u},\mathbf{v}}$ of maximal dimension $\ell(u,v)$, hence $\mathcal{T}_{u,v}^\circ$ is irreducible. The $\mathbb{F}_q$-point counts of $\mathcal{T}_{u,v}^\circ$ is
    \[R^\text{tilt}_{u,v}(q)=\#\mathcal{T}_{u,v}^\circ(\mathbb{F}_q) = \sum_{\mathbf{u}\prec \mathbf{v}} (q-1)^{\#1\text{'s in }\mathbf{u}} \times q^{\#{\color{red}\widetilde{s_{\alpha_i}}}\text{'s in }\mathbf{u}}. \]
\end{cor}

We give an alternate formula for $R^\text{tilt}_{u,v}(q)$ using Hecke algebra, generalizing classical results for $R_{u,v}(q)$ (see \cite[Section~2.3]{GL24}). The \emph{Hecke algebra} $\mathcal{H}$ of $S_n$ is a $\mathbb{C}[q^{\pm 1}]$-algebra generated by the set $\{T_i\}_{i\in [n-1]}$ satisfying the braid relations and the \emph{Hecke relation}:
\[(T_i+q)(T_i-1) = 0 \text{ for }i \in [n-1].\]
For $w\in S_n$, let $T_w :=
T_{\alpha_1}T_{\alpha_2}\dots T_{\alpha_{\ell(w)}}$ for any reduced expression $w = s_{\alpha_1}\cdots s_{\alpha_{\ell(w)}}$. The set $\{T_w:w\in S_n\}$ forms a $\mathbb{C}[q^{\pm 1}]$-basis of $\mathcal{H}$. The \emph{trace map} $\epsilon:\mathcal{H} \rightarrow \mathbb{C}[q^{\pm 1}]$ is the $\mathbb{C}[q^{\pm 1}]$-linear map defined by
\[\epsilon(T_w) = \begin{cases}
    1 & \text{ if }w = id\\
    0 & \text{otherwise}
\end{cases}.\]


For an expression $\mathbf{w}=s_{\alpha_1}s_{\alpha_2}\cdots s_{\alpha_N}$, denote $T_\mathbf{w}:=T_{\alpha_1}T_{\alpha_2}\cdots T_{\alpha_N}$. 

\begin{theorem}\label{thm:hecke}
    Fix $u\leq_\mathbf{a} v$ where $\mathbf{a}$ is flat. Let $\mathbf{u},\mathbf{v}$ be $\mathbf{a}$-tilted reduced expressions for $u,v$ respectively. We have
    \[R^\text{tilt}_{u,v}(q) = q^{\ell(u,v)}\epsilon(T_{\mathbf{v}}^{-1} T_{\mathbf{u}}).\]
\end{theorem}


% where let $\phi_j: \mathrm{GL}_2\rightarrow \mathrm{GL}_n$ be the map such that $\phi_j\begin{pmatrix}
%     a & b\\
%     c& d
% \end{pmatrix}$ is 

% \[g_k=\begin{cases}
%         \phi_{i_k}{\small\begin{pmatrix}
%              1 & 0\\ p & 1
%         \end{pmatrix}}, p\neq0, &\text{if }u_k=1,\\
%         \phi_{i_k}{\small\begin{pmatrix}
%             0 & -1\\ 1 & 0
%         \end{pmatrix}}, &\text{if }u_k=s_{i_k},\\
%         \phi_{i_k}{\small\begin{pmatrix}
%             -m & 1\\ -1 & 0
%         \end{pmatrix}}, &\text{if }u_k={\color{red}s_{i_k}}.
%     \end{cases}\]


\section{Curve neighborhoods and the cohomology classes \texorpdfstring{$[\mathcal{T}_{u,v}]$}{T(u,v)}}\label{sec:QH}
For $w\in S_n$, define the \emph{Schubert variety} $X^w = \overline{BwB/B}$ and the \emph{opposite Schubert variety} $X_w = \overline{B_-wB/B}$.
Let $\rho_i\in H_2(\mathrm{Fl}_n)$ be the homology class of $X^{s_i}$. For an effective degree $d = \sum_{i = 1}^{n-1} d_i\rho_i \in H_2(\mathrm{Fl}_n)$, the \emph{Kontsevich moduli space} $\mathcal{M}_d = \overline{\mathcal{M}}_{0,3}(\mathrm{Fl}_n,d)$ parametrizes the set of degree $d$, genus zero stable curves in $\mathrm{Fl}_n$ with $3$ marked points. We will represent $d$ by the vector $(d_1,\dots,d_{n-1})$.
The space $\mathcal{M}_d$ is naturally equipped with evaluation maps $ev_i:\mathcal{M}_d \rightarrow \mathrm{Fl}_n$ sending a curve to its $i$-th marked point for $i = 1,2,3$. 


The \emph{quantum cohomology ring} $QH^*(\mathrm{Fl}_n)\cong H^*(\mathrm{Fl}_n)\otimes_\mathbb{Z} \mathbb{Z}[q_1,\dots,q_{n-1}]$ is a free $\mathbb{Z}[q]$-module generated by the Schubert classes $\{\sigma_w:=[X_w]:w\in S_n\}$, where the products are given by
\begin{equation}\label{eqn:quantumprod}
    \sigma_u\star \sigma_v = \sum_{\substack{w\in S_n,\ d\in \mathbb{N}^{n-1}}} \langle \sigma_u,\sigma_v,\sigma_{w_0w} \rangle_d\, q^d \sigma_w.
\end{equation}
Here $\langle \sigma_u,\sigma_v,\sigma_{w_0w} \rangle_d$ are the \emph{Gromov--Witten invariants} of the flag variety defined as
\[\langle \sigma_u,\sigma_v,\sigma_{w_0w} \rangle_d  = \int_{\mathcal{M}_d} ev_1^*(\sigma_u) \cdot ev_2^*(\sigma_v) \cdot ev_3^*(\sigma_{w_0w}).\]
Informally, these invariants count the equivalence classes of degree $d$ rational curves passing through the given Schubert varieties in general positions. 


Fulton--Woodward \cite{FW} initiated the study of minimal quantum degrees $d$ appearing in \eqref{eqn:quantumprod}. Postnikov \cite{Postnikov-quantum-Bruhat-graph} showed that $d_{u,w_0v}$ is the unique such minimal degree. Our \Cref{thm:weight-distance} gives an explicit combinatorial description for this degree.

    
In their study of the quantum K-theory of homogeneous spaces $G/P$, Buch--Chaput--Mihalcea--Perrin \cite{BCMP} introduced the \emph{Gromov--Witten variety} $M_d(X_u,X^v) := ev_1^{-1}(X_u)\cap ev_2^{-1}(X^v)$ and the \emph{curve neighborhood} $\Gamma_d(X_u,X^v) := ev_3(M_d(X_u,X^v))$. These varieties encode information about the Gromov--Witten invariants \cite{curveneighborhood}. 

The main theorems of this section relate tilted Richardson varieties with curve neighborhoods and quantum Schubert calculus. 
\begin{theorem}\label{thm:Gamma=T}
    For any $u,v\in S_n$, $\Gamma_{d_{u,v}}(X_u,X^v)= \mathcal{T}_{u,v}$.
\end{theorem}


\begin{theorem}\label{thm:cohomology}
    The cohomology class $[\mathcal{T}_{u,v}] = [\Gamma_{d_{u,v}}(X_u,X^v)]\in H^*(\mathrm{Fl}_n)$ is equal to
    \begin{equation}\label{eqn:class}
        [q^{d_{u,v}}] \sigma_u \star \sigma_{w_0v} = \sum_{w\in S_n} \langle\sigma_u,\sigma_{w_0v},\sigma_{w_0w}\rangle_{d_{u,v}}\sigma_w.
    \end{equation}
\end{theorem}

% We sketch the proof for the two results above.
\begin{proof}[Proof Sketch]
For \Cref{thm:Gamma=T}, we first show that the two varieties share the same set of $T$-fixed points $\{e_w:w\in [u,v]\}$, using \eqref{eqn:T-fixed} and results in \cite{FW}. We then prove $\mathcal{T}_{u,v}$ is the largest $T$-invariant subvariety of $\mathrm{Fl}_n$ with $T$-fixed points $[u,v]$, hence $\mathcal{T}_{u,v}\supseteq\Gamma_{d_{u,v}}(X_u,X^v)$. Finally, the theorem follows from the fact that both varieties have the same dimension and $\mathcal{T}_{u,v}$ is irreducible (\Cref{thm:geometric} and \cite{FW}).

For \Cref{thm:cohomology}, by the projection formula, 
\[[\mathcal{T}_{u,v}] = [\Gamma_{d_{u,v}}(X_u,X^v)] = \frac{1}{c} [q^{d_{u,v}}] \sigma_u \star \sigma_{w_0v} \text{ for some $c\in \mathbb{Z}_{>0}$}.\]
Postnikov \cite{Postnikov-quantum-Bruhat-graph} gave a polynomial representative of \eqref{eqn:class} using \emph{path Schubert polynomials} $\mathfrak{S}_{u,v}(x,q)$. We show that the leading monomial of $\mathfrak{S}_{u,v}(x,q)$ has coefficient $1$, implying $c = 1$.
\end{proof}

 

\acknowledgements{We are grateful to Alex Postnikov for introducing us to quantum Bruhat graphs. We thank Grant Barkley, Sara Billey, Anders Buch, Sergey Fomin, Allen Knutson, Thomas Lam, Leonardo Mihalcea, Melissa Sherman-Bennett, Lauren Williams, Weihong Xu and Alexander Yong for many helpful conversations.}

\printbibliography



\end{document}

Given a permutation $w\in S_n$, we also view $w$ as the permutation matrix with $1$ at $(w_i,i)$ and $0$ everywhere else\footnote{We note that in some literature, this is the permutation matrix that corresponds to $w^{-1}$ instead of $w$.}. The set of $T$-fixed points on $\mathrm{Fl}_n$ is $\{e_w = wB/B: w\in S_n\}$. Define the \emph{Schubert cell} $X_{w}^\circ = Be_w$ to be the Borel orbit of $e_w$ and the \emph{Schubert variety} $X_{w} = \overline{X_w^\circ}$ to be the closure of the Schubert cell. Similarly, define the \emph{opposite Schubert cell} $\Omega_{w}^\circ = B_{-}e_w$ and the \emph{opposite Schubert variety} $\Omega_w = \overline{\Omega_w^\circ}$. 


It is perhaps easier to visualize Schubert and opposite Schubert varieties in the following way. For any $I\subset [n], k\in [n]$ and $M\in \mathrm{Mat}_{n\times n}$, define $r_{I,k}(M)$ to be the rank of the submatrix of $M$ obtained by taking the rows in $I$ and the left $k$ columns. 
We will make use of the following equivalent definition of (opposite) Schubert cells and Schubert varieties. For $S$ any subset of $[n]$, let $\mathrm{Proj}_S:\mathbb{C}^{n}\twoheadrightarrow \mathbb{C}^{|S|}$ be the projection onto the coordinates with indices in $S$. 
The Schubert cell is
\[X_w^{\circ} = \{F_{\bullet}\in \mathrm{Fl}_n: \dim(\mathrm{Proj}_{[i,n]}(F_k)) = r_{[i,n],k}(w)\} \text{ for all }i,k\in [n]\},\]
and the Schubert variety is defined by replacing ``$=$" with ``$\leq$"
Similarly, the opposite Schubert cell is
\[\Omega_w^{\circ} = \{F_{\bullet}\in \mathrm{Fl}_n: \dim(\mathrm{Proj}_{[i]}(F_k)) = r_{[i],k}(w)\} \text{ for all }i,k\in [n]\},\]
and the opposite Schubert variety is defined by replacing ``$=$" with ``$\leq$".


% The (opposite) Schubert varieties possess a stratification by (opposite) Schubert cells:
% \[X_{w} = \bigsqcup_{u\leq w}X_u^\circ\ \text{and } \Omega_w = \bigsqcup_{w\leq v}\Omega_v^\circ,\]
% where ``$\leq$" denotes the strong Bruhat order on $S_n$.
 

Define the \emph{open Richardson variety} to be $\mathcal{R}^\circ_{u,v} = X^\circ_{v}\cap \Omega^\circ_{u}$ and the \emph{Richardson variety} to be $\mathcal{R}_{u,v} = X_{v}\cap \Omega_u$. 
% In particular, $\mathcal{R}^\circ_{u,v}$ and $\mathcal{R}_{u,v}$ are non-empty if and only if $u\leq v$, in which case we have
% \[\dim(\mathcal{R}_{u,v}) = \dim(\mathcal{R}_{u,v}^\circ) = \ell(v)-\ell(u) = \ell(u,v).\]
% Similar to Schubert varieties, we also have
% \begin{equation}\label{eqn:Richardson}
%     \mathcal{R}_{u,v} = \overline{\mathcal{R}_{u,v}^{\circ}}\ \text{and }\mathcal{R}_{u,v} = \bigsqcup_{[x,y]\subseteq [u,v]}\mathcal{R}_{x,y}^\circ,
% \end{equation}
% where the disjoint union is taken over all Bruhat intervals $[x,y]$ contained in $[u,v]$.
