\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}
\usepackage{tikz}
\DeclarePairedDelimiter\abs{\lvert}{\rvert} %Something useful only for this sample's sake: you can erase this
\newcommand{\D}{\mathfrak{D}}
\newcommand{\Cbb}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\I}{\mathfrak{I}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\RC}{\mathcal{RC}}
\DeclareMathOperator{\Fl}{Fl}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\CT}{CT}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\code}{code}
%%%%%%%%% a placer avant \begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
\author[\initial{Y.} Gao]{\firstname{Yibo} \lastname{Gao}}
\address{Massachusetts Institute of Technology\\
Department of Mathematics\\
Cambridge\\
MA 02142, USA}
\email{gaoyibo@mit.edu}
%%%%% Sujet
\keywords{Schubert polynomial, dual Schubert polynomial, Bruhat chains}
\subjclass{05E05, 14N15}
%%%%% Gestion
\DOI{10.5802/alco.105}
\datereceived{2019-01-02}
\daterevised{2019-11-29}
\dateaccepted{2019-12-15}
%%%%% Titre et résumé
\title
[On a Conjecture by Postnikov and Stanley]
{An involution on RC-graphs and a conjecture on dual Schubert polynomials by Postnikov and Stanley}
\begin{abstract}
In this paper, we provide explicit formula for the dual Schubert polynomials of a special class of permutations using certain involution principals on RC-graphs, resolving a conjecture by Postnikov and Stanley.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
\section{Introduction and Preliminaries}\label{sec:intro}
Alexander Postnikov and Richard Stanley~\cite{postnikov2009chains} defined dual Schubert Polynomials $\D_w$ where the label $w$ belongs to some Weyl group. In type A, the polynomials $\D_w$ are dual to the Schubert polynomials $\mathfrak{S}_w$ with respect to some natural pairing on polynomials. Thus, certain change of basis matrix for the coinvariant algebra, which is the cohomology ring of the complex flag manifold, can now be formulated via dual Schubert polynomials, providing more ways for the study of Schubert calculus. The readers are referred to~\cite{postnikov2009chains} for more details on dual Schubert polynomials.
In this paper, we resolve Conjecture 16.1 of~\cite{postnikov2009chains}, which asks for a form for the dual Schubert polynomial $\D_w$ where $w$ is \emph{special}. We prove this conjecture by involution principal on RC-graphs for a fixed permutation, via ladder moves or chute moves utilized by Bergeron and Billey~\cite{bergeron1993rc}. In Section~\ref{sec:intro}, we introduce related background knowledge on dual Schubert polynomials and Schubert polynomials and in Section~\ref{sec:main}, we formulate our main theorem and provide a proof.
\subsection{Dual Schubert Polynomials}
First, we recall some facts about symmetric groups and fix some notations. Let $S_n$ denote the symmetric group on $n$ elements. For $w\in S_n$, let $\ell(w)$ be its Coxeter length, \ie the number of inversions of $w$. And let $s_i$ be the simple transposition $(i,i+1)$ and let $t_{ij}$ be the transposition $(i,j)$. The \emph{(right) weak (Bruhat) order} on $S_n$ is defined by the covering relations $w\lessdot_w ws_i$ for all $\ell(w)=\ell(ws_i)-1$ while the \emph{(strong) Bruhat order} is defined by the covering relations $w\lessdot_s wt_{ij}$ for all $\ell(w)=\ell(wt_{ij})-1$. We use superscripts $w$ and $s$ for weak and strong order respectively.
We are now going to define dual Schubert polynomials. To do this, in the strong Bruhat order, let us assign the weight $m(w,ws_{ij})=x_i-x_j$ to each edge of its Hasse diagram. For a saturated chain $C=(u_0\lessdot u_1\lessdot u_2\lessdot\cdots\lessdot u_{\ell})$ in the strong Bruhat order, define its weight as $m_C(x)=m(u_0,u_1)m(u_1,u_2)\cdots m(u_{\ell-1},u_{\ell}).$
\begin{defi}[\cite{postnikov2009chains}]
Define the following polynomials
\[
\D_{u,w}(x):=\frac{1}{\big(\ell(w)-\ell(u)\big)!}\sum_{C}m_C(x),
\]
where the sum is over all saturated chains from $u$ to $w$ in the strong Bruhat order. Let $\D_w(x):=\D_{\id,w}$ be the \emph{dual Schubert polynomial} labeled by $w\in S_n$.
\end{defi}
The polynomials $\D_{u,w}$ are defined naturally in a more general context for arbitrary Weyl groups by Postnikov and Stanley~\cite{postnikov2009chains}. And they have the following geometric interpretation. For $w\in W$, where $W$ is any Weyl group, and $\lambda$ a dominant weight, the $\lambda$-degree $\deg_{\lambda}(X_w)$ of the Schubert variety $X_w$ equals $\ell(w)!\cdot\D_w(\lambda)$. In this paper, we will only be concerned with the type A case $W=S_n$.
Combinatorially, the dual Schubert polynomial at the longest permutation $w_0\in S_n$ has a beautiful expression. The following theorem is first due to Stembridge~\cite{stembridge2002weighted}, in arbitrary Weyl groups.
\begin{theorem}\label{thm:stembridge}
For the longest permutation $w_0\in S_n$,
\[
\D_{w_0}(x)=\prod_{1\leq i0}^2\setminus D$ are drawn as non-crossings. After connecting them by strands, we can read off its permutation directly and reducibility corresponds to whether no pairs of strands intersect more than once. We can also represent crossings as $+$ and non-crossings as $\cdot$ or just nothing. See Figure~\ref{fig:rcex} for an example.
\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=0.3]
\draw (0,-1)--(6,-1);
\draw (6,-1) arc (270:360:1);
\draw (0,-3)--(4,-3);
\draw (4,-3) arc (270:360:1);
\draw (5,-2)--(5,0);
\draw (0,-5) arc(270:360:1);
\draw (1,-4)--(1,0);
\draw (0,-7) arc (270:360:1);
\draw (2,-5) arc (90:180:1);
\draw (2,-5)--(4,-5);
\draw (4,-5) arc (270:360:1);
\draw (6,-3) arc (90:180:1);
\draw (6,-3) arc (270:360:1);
\draw (8,-1) arc (90:180:1);
\draw (8,-1) arc (270:360:1);
\draw (0,-9) arc (270:360:1);
\draw (2,-7) arc (90:180:1);
\draw (2,-7) arc (270:360:1);
\draw (3,-6)--(3,0);
\node at (-1,-1) {1};
\node at (-1,-3) {2};
\node at (-1,-5) {3};
\node at (-1,-7) {4};
\node at (-1,-9) {5};
\node at (1,1) {$w_3$};
\node at (3,1) {$w_5$};
\node at (5,1) {$w_2$};
\node at (7,1) {$w_1$};
\node at (9,1) {$w_4$};
\node at (15,-1) {1};
\node at (15,-3) {2};
\node at (15,-5) {3};
\node at (15,-7) {4};
\node at (15,-9) {5};
\node at (17,1) {1};
\node at (19,1) {2};
\node at (21,1) {3};
\node at (23,1) {4};
\node at (25,1) {5};
\node at (17,-1) {+};
\node at (19,-1) {+};
\node at (21,-1) {+};
\node at (23,-1) {$\cdot$};
\node at (17,-3) {+};
\node at (19,-3) {+};
\node at (21,-3) {$\cdot$};
\node at (17,-5) {$\cdot$};
\node at (19,-5) {+};
\node at (17,-7) {$\cdot$};
\end{tikzpicture}
\caption{An example of an RC-graph for permutation $w=35214$ and of type $(3,2,1,0,0,\ldots)$}
\label{fig:rcex}
\end{figure}
For a piece of notation, for an RC-graph $D$, write $w(D)$ for its permutation and $\alpha(D)$ for its type. Let $\RC(w)$ be the set of all RC-graphs for permutation $w$. And for $\alpha=(\alpha_1,\alpha_2,\ldots)\in\Z_{\geq0}^{\infty}$ with finitely many nonzero positive integer entries, let $x^{\alpha}:=x_1^{\alpha_1}x_2^{\alpha_2}\cdots.$ The following theorem is usually formulated in terms of reduced words.
\begin{theorem}[\cite{billey1993some,fomin1994schubert}]\label{thm:rc}
$\mathfrak{S}_w=\sum_{D\in\RC(w)}x^{\alpha(D)}.$
\end{theorem}
Note that Theorem~\ref{thm:rc} proves a stability property of the Schubert polynomials. Namely, for $w\in S_n$, let $w'$ be its image under the most natural inclusion map $S_n\hookrightarrow S_{n+1}$ by permuting the first $n$ elements. Then $\mathfrak{S}_w=\mathfrak{S}_{w'}$. As a result, from now on, instead of concerning ourselves with $S_n$ where $n$ varies, we will be considering $S_{\infty}$, which is the injective limit of symmetric groups $S_1\hookrightarrow S_2\hookrightarrow S_3\hookrightarrow\cdots$, whose elements are permutations of $\Z_{>0}$ with finitely many non-fixed points. Then $\mathfrak{S}_w$ is well-defined for $w\in S_{\infty}$.
Local moves on RC-graphs for a fixed permutation are described in~\cite{bergeron1993rc}. A \emph{chute move} $C_{ij}$, can be applied to $D\in\RC(w)$, when the following conditions are satisfied:
\begin{itemize}
\item $(i,j)\in D$, $(i+1,j)\notin D$;
\item $(i,j-m),(i+1,j-m)\notin D$ for some $0i:w(j)0$. We can then view $w$ as a permutation in $S_{n+k}\hookrightarrow S_{\infty}$.
Define
\[
g_{\delta}(y_1,\ldots,y_m)=\sum_{u\in S_m}(-1)^{\ell(w_0)-\ell(u)}y_1^{u(1)}\cdots y_m^{u(m)}=y_1\cdots y_m\prod_{1\leq in+k$. From now on, for a special type $\alpha$, we view it as an array of $n+k$ numbers, instead of an infinite array. Let $\RC_s(u)$ be the set of all RC-graphs for permutation $u$ and of special types. Moreover, for each $D\in\RC_s(u)$, we can associate a sign $\wt(\alpha)$ to $D$ based on its type $\alpha$ according to $f$. It is possible to write down explicitly the sign, but for our purpose, the following rules are more useful:
\begin{enumerate}
\item\label{proof_theo2.2_prem1} If $\alpha=\code(w)$, $\wt(\alpha)=1$;
\item\label{proof_theo2.2_prem2} If $\alpha'$ is obtained from $\alpha$ by switching two nonzero entries, then $\wt(\alpha')=-\wt(\alpha)$;
\item\label{proof_theo2.2_prem3} If $\alpha'$ is obtained from $\alpha$ by switching a zero with its adjacent nonzero entry such that $\alpha'$ remains special, then $\wt(\alpha')=-\wt(\alpha)$.
\end{enumerate}
Let's justify the rules here. For~\eqref{proof_theo2.2_prem1}, when $\alpha=\code(w)$, the corresponding valid set $J$ satisfies that $J\supset\{a_{i-1}+1,\ldots,a_i-1\}$ so $(j_1+\cdots+j_n)+(a_1+\cdots+a_k)=1+2+\cdots+(n+k)$ and as a result, $d_J=0$, $\epsilon_J=1$. And as the nonzero entries of $\alpha$ are increasing, the sign of $\alpha$ is the same as $\epsilon_J$. Rule~\eqref{proof_theo2.2_prem2} follows from the fact that a transposition changes the sign of a permutation. For~\eqref{proof_theo2.2_prem3}, let $J$ and $J'$ be the corresponding valid sets for $\alpha$ and $\alpha'$ respectively. As $J$ and $J'$ differ by an adjacent pair of numbers, $d_J$ and $d_J'$ differ by 1 so their signs are different. But the permutations (in the expansion of $g_{\delta}$) associated with $\alpha$ and $\alpha'$ are the same so in the end, $\wt(\alpha')=-\wt(\alpha)$.
Since for a special type $\alpha$, $(x^{\alpha},x^{\alpha})_D=1!2!\cdots n!$, we can interpret $(f,\mathfrak{S}_u)_D$ as a weighted sum of RC-graphs in $\RC_s(u)$, where the weights are $\pm1$ explained above.
For example, if $w=41532$ is special, then $\code(w)=(3,0,2,1,0)$. There are a total number of 36 special types: 2 possibilities for the position of the first zero that appears as either $\alpha_1$ or $\alpha_2$, 3 possibilities for the position of the second zero, and 6 possibilities for the permutation of $3,2,1$. As for the weights, we have $\wt(3,0,2,1,0)=1$, $\wt(0,3,2,1,0)=-1$, $\wt(0,1,2,3,0)=1$, $\wt(0,1,2,0,3)=-1$, etc.
Our strategy is using flip moves to pair up RC-graphs of special types with different signs. We will do this in steps. Let $I=\{1,2,\ldots,n+k\}\setminus\{a_1,a_2,\ldots,a_k\}$ be the index set of positions where $\code(w)$ is nonzero. We say that $D\in\RC_s(u)$ is 1-\emph{flippable}, if there exists $i\in I$ such that $(i,1)\notin D$. For each 1-flippable RC-graph $D\in\RC_s(u)$, we can pair it up with $F_{i_0,1}(D)$ where $i_0$ is the smallest index in $I$ such that $(i_0,1)\notin D$. Notice that in this case, $D'=F_{i_0,1}(D)$ is also 1-flippable because of the existence of $i_0$ and that $i_0$ is the smallest index in $I$ such that $(i_0,1)\notin D'$ as well. Moreover, $\alpha(D')$ can be obtained from $\alpha(D)$ by switching the $i_0^{th}$ entry and $(i_0+1)^{th}$ entry. Thus, $D'\in\RC_s(u)$ and $D'$ and $D$ have opposite signs. As a result, $F_{*,1}$ is a sign-reversing involution on the set of all 1-flippable RC-graphs in $\RC_s(u)$. By taking out all such graphs, we are left with RC-graphs that are not 1-flippable. Denote such set as $\RC_{s'}(u)$.
Notice that for $D\in\RC_{s'}(u)$ and $\alpha=\alpha(D)$, since $(i_0,1)\in D$ for all $i_0\in I$, we know that $\alpha_{a_i}=0$ for $i=1,\ldots,k$. Our next step will be a generalization to the above procedure.
We say that $D\in\RC_{s'}(u)$ is $j$-\emph{flippable}, for some $j\geq1$, if there exists $i\in I$ satisfying the following condition:
\begin{enumerate}
\item\label{proof_theo2.2_deux1} If $a_{t-1}+1\leq i\alpha_{i+1}$. Similarly, $\alpha_i>\alpha_{i+2}$ for $i=a_t-1$. Thus, the nonzero entries of $\alpha$ are decreasing, and thus $\alpha=\code(w)$. Next, we use backwards induction to show that $(i,1),(i,2),\ldots,(i,\alpha_i)\in D$, $i\in I$. As we already know $(i,1)\in D$ for all $i\in I$, the base case $i=a_k-1$ is established. For a general $i$, if $a_{t-1}+1\leq i< a_t-1$, then $i+1\in I$ and $(i+1,1),\ldots,(i+1,\alpha_{i+1})\in D$. The non-flippable property directly implies that $(i,1),\ldots,(i,\alpha_{i+1}+1)\in D$ so we are done as $\alpha_{i+1}+1=\alpha_i$. If $i=a_t-1$ for some $t$, then $i+1\notin I$, $i+2\in I$, $\alpha_{i}=\alpha_{i+2}+1$. The non-flippable property implies that the cardinality of $\{(i,1),\ldots,(i,\alpha_i+1)\}\cap D$ is $\alpha_i$ so we just need to figure out which box among $(i,1),\ldots,(i,\alpha_i+1)$ is not in $D$. If $(i,k)\notin D$ for some $k\leq\alpha_i$, then the two strands emanating up and right from $(i+2,k-1)$ meet again at $(i,\alpha_{i}+1)$ (Figure~\ref{fig:indNon}), meaning $D$ is not reduced. Thus, $(i,1),\ldots,(i,\alpha_i)\in D$ and our induction step goes through. This RC-graph $D$ is indeed the bottom RC-graph for $w$, which is reduced and corresponds to $w$ (see~\cite{bergeron1993rc}).
\end{proof}
\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=0.4]
\node at (0,-2) {$i$};
\node at (0,-4) {$i$+1};
\node at (0,-6) {$i$+2};
\node at (8,0) {$j$};
\node at (12,0) {$\alpha_i$+1};
\node at (2,-2) {+};
\node at (4,-2) {+};
\node at (6,-2) {+};
\node at (8,-2) {$\cdot$};
\node at (10,-2) {+};
\node at (12,-2) {+};
\node at (2,-4) {$\cdot$};
\node at (4,-4) {$\cdot$};
\node at (6,-4) {$\cdot$};
\node at (8,-4) {$\cdot$};
\node at (10,-4) {$\cdot$};
\node at (2,-6) {+};
\node at (4,-6) {+};
\node at (6,-6) {+};
\node at (8,-6) {+};
\draw (12,-3)--(12,-2)--(9,-2);
\draw (9,-2) arc (90:180:1);
\draw (7,-4) arc (270:360:1);
\draw (7,-4) arc (90:180:1);
\draw (6,-5)--(6,-6)--(9,-6);
\draw (11,-4) arc (270:360:1);
\draw (11,-4) arc (90:180:1);
\draw (9,-6) arc (270:360:1);
\end{tikzpicture}
\caption{A configuration that is not reduced}
\label{fig:indNon}
\end{figure}
Let's now look at a slight generalization to Theorem~\ref{thm:main}. Suppose that we have positive integers $0b_k$. The base case $i=b_k-1$ is established. Moreover, this claim is trivial if $i\notin I$. For a general $i$, let $i'$ be the smallest element greater than $i$ in $I$. By the non-flippable property of $D$, $\{(i,1),\ldots,(i,b_k-i)\}\cap D$ has greater cardinality than $\{(i',1),\ldots,(i',b_k-i')\}\cap D$, which is $\alpha_{i'}$ by induction hypothesis. As $\alpha_i=\alpha_{i'}+1$, we know that $\{(i,1),\ldots,(i,b_k-i)\}\cap D$ must have cardinality $\alpha_i$ so there cannot be more boxes in $i^{th}$ row after $b_k-i$. The induction step goes through. Thus, the decomposition of the permutation of $D$ uses only $s_i$ for $i