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

\articlenumber{8}
\addbibresource{8.bib}

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{etex}
%\reserveinserts{28}
\usepackage{pict2e}
\usepackage{xypic}
\usepackage{tikz}
\usepackage{MnSymbol}
%\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{stmaryrd}
%\topmargin=0in
%\headheight=0.4in
%\headsep=0.4in
%\parindent=0in
% \textheight=8.5in
% \oddsidemargin=+0.0in
% \textwidth=6.4in
% \evensidemargin=+0.0in
%\parskip=11pt
%\renewcommand{\baselinestretch}{1.5}
%\textheight=8in
%\input epsf
\newcommand{\Mut}{\operatorname{Mut}}

%\usepackage[capitalize,nameinlink,noabbrev,nosort]{cleveref}
%\def\source{\operatorname{source}}
%\def\target{\operatorname{target}}
%\def\Rect{\operatorname{Rect}}
\usepackage{pictex}
\usepackage{amscd}
%\usepackage{showkeys}
%\usepackage[inline]{showlabels}
\usepackage{afterpage}
\usepackage{youngtab}
\usepackage{psfrag}
\usepackage[boxsize=.3 em]{ytableau}

%\usepackage[utf8x]{inputenc}
\usepackage{verbatim}
%\usepackage{url}
%\usepackage{mathtools}




\usepackage{graphics}
\usepackage{graphicx}


%\usepackage[active]{srcltx} % SRC Specials: DVI [Inverse] Search
% ----------------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small
% THEOREMS -------------------------------------------------------

%For rc-graphs, courtesy Nantel Bergeron, command names rewritten by EM
\font\co=lcircle10
\def\petit#1{{\scriptstyle #1}}
\def\plus{\petit +}
\def\dt{\hspace{.17ex}\cdot\hspace{.17ex}}
%\def\Le{\hbox{\rotatedown{$\Gamma$}}}
%Pair of avoiding elbows looks kind of like a `j' and then an `r'
\def\jr{\rotatedown{\smash{\raise2pt\hbox{\co \rlap{\rlap{\char'005} \char'007}}
               \raise6pt\hbox{\rlap{\vrule height6.5pt}}
                \raise2pt\hbox{\rlap{\hskip4pt \vrule
          height0.4pt depth0pt
                width7.7pt}}}}}
%\def\jr{\smash{\raise2pt\hbox{\co \rlap{\rlap{\char'005} \char'007}}
%               \raise6pt\hbox{\rlap{\vrule height6.5pt}}
%                \raise2pt\hbox{\rlap{\hskip4pt \vrule
%          height0.4pt depth0pt
%                width7.7pt}}}}
\def\textcross{\ \smash{\lower4pt\hbox{\rlap{\hskip4.15pt\vrule height14pt}}
                \raise2.8pt\hbox{\rlap{\hskip-3pt \vrule height.4pt depth0pt
                                width14.7pt}}}\hskip12.7pt}

\def\textelbow{\ \hskip.1pt\smash{\raise2.75pt%
%               \hbox{\co \hskip 4.15pt\rlap{\rlap{\char'005} \char'007}
                \hbox{\co \hskip 4.15pt\rlap{\rlap{\char'004} \char'006}
                \lower6.8pt\rlap{\vrule height3.5pt}
                \raise3.6pt\rlap{\vrule height3.5pt}}
                \raise2.8pt\hbox{%
                  \rlap{\hskip-7.15pt \vrule height.4pt depth0pt
width3.5pt}%
                  \rlap{\hskip4.05pt \vrule height.4pt depth0pt
width3.5pt}}}
                \hskip8.7pt}




\newtheorem{thm}{Theorem}[section]
%\newtheorem{theorem}{Theorem}[section]
\newtheorem{theorem}[thm]{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{corollary}[thm]{Corollary}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{proposition}[thm]{Proposition}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{definition}[thm]{Definition}
\newtheorem{rem}[thm]{Remark}  %now remarks look like defns
\newtheorem{remark}[thm]{Remark}  %now remarks look like defns
\newtheorem{rems}[thm]{Remarks}
\newtheorem{strategy}[thm]{Strategy}
%\theoremstyle{remark}
%\newtheorem{rem}[thm]{Remark}
%\newtheorem{rems}[thm]{Remarks}
\numberwithin{equation}{section}
% MATH -----------------------------------------------------------

\newcommand{\Comment}[1]{{\color{blue} \sf ($\clubsuit$ #1 $\clubsuit$)}}


\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\R}{\mathbb R}
\newcommand{\CC}{\mathbb C}
\newcommand{\PPP}{\mathbb P}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}

\newcommand{\ayo}{a_{\ydiagram{1}}}
\newcommand{\ayz}{a_{\ydiagram{2}}}
\newcommand{\ayoo}{a_{\ydiagram{1,1}}}
\newcommand{\ayzz}{a_{\ydiagram{2,2}}}
\newcommand{\ayt}{a_{\ydiagram{3}}}
\newcommand{\aytt}{a_{\ydiagram{3,3}}}


\newcommand{\pyo}{p_{\ydiagram{1}}}
\newcommand{\pyz}{p_{\ydiagram{2}}}
\newcommand{\pyoo}{p_{\ydiagram{1,1}}}
\newcommand{\pyzz}{p_{\ydiagram{2,2}}}
\newcommand{\pyt}{p_{\ydiagram{3}}}
\newcommand{\pytt}{p_{\ydiagram{3,3}}}



\newcommand{\HDG}{H_{A}}
\newcommand{\HB}{H_{B}}
\newcommand{\HA}{H_{A}}

\newcommand{\tildeHA}{\tilde H_{A}}
\newcommand{\Sh}{\mathcal{P}}
\newcommand{\Shkn}{{\mathcal P_{k,n}}}
\newcommand{\rect}{\mathrm{rec}}
\newcommand{\wt}{\mathrm{wt}}
\newcommand{\Ck}{\mathbb{K}}
%\newcommand{\Xcheck}{\check X}
%\newcommand{\Xcheckbar}{\check{\mathbb X}}
\newcommand{\Spec}{\mathrm{Spec}}

\newcommand{\pa}{a}

\newcommand{\pb}{b}
\newcommand{\ta}{\tau}
\newcommand{\hbarr}{\hbar}
\newcommand{\hbarrB}{z}

\def\O{\mathcal{O}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\inv}{^{-1}}
\newcommand{\si}{\sigma}
\newcommand{\x}{\times}

\newcommand{\K}{\overline{\mathbb K}}
\renewcommand{\k}{\mathbb K}
\newcommand{\w}{{\bf w}}
\renewcommand{\v}{{\bf v}}
\newcommand{\wR}{{\bf w_R}}
\newcommand{\B}{{\mathcal B}}
\newcommand{\Hom}{{\operatorname{Hom}}}
\newcommand{\val}{{\operatorname{val}}}

\newcommand{\xx}{\widetilde{\mathbf{x}}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\T}{\mathcal{T}}
\newcommand{\Pn}{\mathcal{P}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\h}{\mathfrak h}
\newcommand{\Proj}{\operatorname{Proj}}
\newcommand{\Gl}{\operatorname{GL}}
\newcommand{\Fl}{\operatorname{Fl}}
\newcommand{\Trop}{\operatorname{Trop}}
\newcommand{\Sym}{\operatorname{Sym}}
\def\Fcal{\mathcal{F}}
\def\Q{\mathbb{Q}}
\def\TT{\mathbb{T}}
\def\Xcal{\mathcal{X}}
\def\Acal{\mathcal{A}}
\def\ZZ{\mathbb{Z}}
\newcommand{\overunder}[2]{
\!\begin{array}{c}
\scriptstyle{#1}\\[-.1in]
-\!\!\!-\!\!\!-\\[-.1in]
\scriptstyle{#2}
\end{array}
\!
}


\newcommand{\mathbbX}{\mathbb X}
\newcommand{\checkX}{\check{\mathbb X}}
\newcommand{\openX}{\check{\mathbb X}^\circ}

\newcommand{\p}{{p}}
\newcommand{\Ji}{J_i}
\newcommand{\Jip}{J_{i\ \widehat{i+1}}}

\newcommand{\Le}{\rotatebox[origin=c]{180}{$\Gamma$}} %for Le symbol. Command is text, not math mode.
\newcommand{\pathne}[1]{L^\nearrow_{#1}} %For lattice paths, going northeast. #1 either a partition or the vertical steps
\newcommand{\pathsw}[1]{L^\swarrow_{#1}}
\newcommand{\vertne}[1]{V^\nearrow(#1)} %For vertical steps of paths, going northeast. #1 either a lattice path or partition
\newcommand{\vertsw}[1]{V^\swarrow(#1)}
\newcommand{\partne}[1]{\lambda^\nearrow(#1)} % For partitions associated to subsets of vertical steps (or lattice paths, I guess), going northeast
\newcommand{\partsw}[1]{\lambda^\swarrow(#1)}
\newcommand{\permne}[1]{u^\nearrow_{#1}} % For permutations associated to partitions or lattice paths or subsets of vertical steps, going northeast
\newcommand{\ppermne}[1]{\pi^\nearrow_{#1}} % For permutations associated to partitions or lattice paths or subsets of vertical steps, going northeast
\newcommand{\permsw}[1]{u^\swarrow_{#1}}
\newcommand{\ppermsw}[1]{\pi^\swarrow_{#1}}



%% define your title in the usual way
\title{Combinatorics of cluster structures in Schubert varieties}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Khrystyna Serhiyenko\thanks{\href{mailto:khrystyna.serhiyenko@berkeley.edu}{khrystyna.serhiyenko@berkeley.edu}}\addressmark{1}, 
Melissa Sherman-Bennett\thanks{\href{mailto:m\_shermanbennett@berkeley.edu}{m\_shermanbennett@berkeley.edu}}\addressmark{1},\\  \and Lauren  Williams\thanks{\href{mailto:williams@math.harvard.edu}{williams@math.harvard.edu}}\addressmark{2}}
%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of California at Berkeley \\ \addressmark{2}Department of Mathematics, Harvard University}

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

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

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We give an explicit combinatorial description of 
cluster structures in Schubert varieties of the Grassmannian in terms of 
(target labelings of)
Postnikov's \emph{plabic graphs}.  This description is a natural generalization
of the description given by (Scott 2006) for the Grassmannian
	%\footnote{though in fact Scott used
%source labelings}, 
	and has been
	believed by experts essentially since (Scott 2006), 
	though the statement was not formally written down
until (Muller--Speyer 2016).
%More generally,
%we prove a plabic graph description of cluster structures in 
%Richardson varieties of the form $\mathcal{R_{v,w}}$
%where $w=xv$ with $\ell(w) = \ell(x)+\ell(v)$.  This was conjectured in 
To prove this conjecture we use a result of (Leclerc 2016), who used the module category of the preprojective algebra  
%\Comment{Khrystyna, what is best way to describe what he used?}
to prove that coordinate rings of 
many Richardson varieties in the complete flag variety 
admit cluster structures. We also adapt a construction of (Karpman 2016) 
to 
build cluster seeds associated to reduced expressions.
Further, we explicitly describe cluster structures 
in skew Schubert varieties using plabic graphs
whose boundary vertices need not be labeled in cyclic order.}
%}
%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]
\resumetitle{R\'esum\'e}
\resume{Nous donnons une description combinatoire explicite des structures 
en amas des vari\'et\'es de Schubert des  grassmanniennes en termes de graphes plabiques.
Cette description est une g\'en\'eralisation naturelle de la description donn\'ee par (Scott
2006) pour les grassmanniennes, et correspond \`a ce qui \'etait attendu par les experts depuis (Scott
2006), bien que l'\'enonc\'e  n'ait pas \'et\'e formellement \'ecrit avant (Muller--Speyer
2016).
Nous d\'ecrivons aussi explicitement les structures en amas des vari\'et\'es de Schubert g\'en\'eralis\'ees
en utilisant des graphes plabiques dont les sommets ne sont pas num\'erot\'es dans l'ordre cyclique.
%}
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{cluster algebra, Schubert variety, positroid, plabic graph}

%% 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, ie. [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=true, maxbibnames=99]{biblatex}
%\addbibresource{bibliographyFPSAC.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{Results}\label{sec:intro}

\section{Introduction}

The main result of this extended abstract is that the coordinate ring of (the affine cone over)
any (open) Schubert variety
of the Grassmannian (embedded into projective space via the Pl\"ucker embedding)
admits a cluster algebra structure, which is described explicitly in terms of 
plabic graphs. In the first section, we give some background on Schubert varieties, state our main result, and discuss some applications. Background material on cluster algebras and plabic graphs is delayed to \cref{sec:background}. 

 \emph{Cluster algebras} are a class of commutative rings
which were  introduced by Fomin and Zelevinsky \cite{ca1}; they are connected to 
many fields of mathematics including Teichm\"uller theory and quiver representations,
and their generators satisfy many nice properties, including the \emph{Laurent phenomenon}
\cite{ca1} 
and \emph{positivity theorem} \cite{LeeSchiffler, GHKK}. 
\emph{Plabic graphs} are certain planar bicolored
graphs which were introduced by Postnikov \cite{Postnikov}; plabic graphs (or rather an 
equivalent object, namely alternating strand diagrams) were subsequently used by 
Scott \cite{Scott} to show that the coordinate ring of the affine cone over the 
Grassmannian in its Pl\"ucker embedding admits a cluster algebra structure.

There is a natural plabic graph 
generalization of Scott's construction which experts have believed
for some time should give a cluster structure for Schubert varieties 
(and more generally,
positroid varieties).  
This construction was stated explicitly as a conjecture in 
a recent paper of Muller--Speyer \cite{MullerSpeyer0}, who 
additionally provided some 
evidence in \cite{MullerSpeyer}.  The conjecture 
can be stated roughly as follows.
\begin{conjecture}\label{conj:vague}
	Let $G$ be a reduced plabic graph corresponding to an (open) Schubert (or more generally an open positroid) variety.
	Then the target labeling of the faces of $G$ (which we identify
	with a collection of Pl\"ucker coordinates)
together with the dual quiver of $G$ gives rise to a seed for a cluster
	structure in the coordinate ring of the open Schubert (or positroid) 
	variety.
\end{conjecture}
Meanwhile, Leclerc \cite{Leclerc} constructed a subcategory $\mathcal{C}_{v,w}$ of the module category of the preprojective algebra that has a cluster structure,
%(\Comment{more detail?})
to show that the coordinate ring of 
each Richardson variety $\mathcal{R}_{v,w}$ of the 
complete flag variety contains a subalgebra which is a cluster algebra; when 
$w$ has a factorization of the form $w=xv$ with 
$\ell(w) = \ell(x)+\ell(v)$,  he showed that 
this subalgebra coincides with the 
coordinate ring.  
Because Schubert varieties are isomorphic to Richardson varieties with 
the above property,
Leclerc's result implies that their coordinate rings admit a cluster structure.
However, Leclerc's description of the cluster structure is 
very different from the 
plabic graph description and is far from explicit:
e.g. his cluster quiver is defined in terms of 
morphisms between modules of the preprojective algebra. 

In this paper we prove 
\cref{conj:vague} for Schubert varieties by relating 
Leclerc's cluster structure to the conjectural one coming from plabic graphs.
We also generalize our result to the setting of \emph{skew Schubert varieties}; 
 interestingly, these cluster structures for skew Schubert varieties
 depart from the one in 
\cref{conj:vague}, since they 
use \emph{generalized} plabic graphs (with 
boundary vertices which are no longer cyclically labeled).

Once we have proved that the coordinate rings of Schubert and skew Schubert
varieties have cluster structures, we obtain a number of results ``for free''
 from the cluster theory, including the Laurent phenomenon
and the positivity theorem for cluster variables.
We also obtain many combinatorially 
explicit cluster seeds for each Schubert and skew Schubert
variety. Other applications of our results, including a characterization of which Schubert varieties exhibit finite type cluster structures, are described in  \cref{sec:applications}.
%Note that Schubert varieties provide examples
%of cluster structures of all the finite type simply-laced cluster types ($ADE$), 
%see 
%\cref{sec:conclusion}.  
%Combining our main results with 
%\cite[Theorem 3.3]{MullerSpeyer0} and \cite{Muller}, we find that the coordinate rings of Schubert and skew Schubert varieties (viewed as cluster algebras) are \emph{locally acyclic},
%which implies that each one is finitely generated, normal, locally a complete
%intersection, and equal to its own upper cluster algebras.
%Combining our result with \cite[Theorem 1.2]{FordSer}, we find that the quivers giving 
%rise to the cluster structures for Schubert and skew Schubert varieties admit
%\emph{green-to-red sequences}, which by \cite{GHKK} implies that the cluster algebras have
%\emph{Enough Global Monomials} and hence each coordinate ring has a canonical basis of 
%theta functions, parameterized by the lattice of $g$-vectors.


\subsection{Notation for the flag variety}

Let $\Gl_n$ denote the general linear group, $B$ the Borel subgroup of 
lower triangular matrices, $B^+$ the opposite Borel subgroup of 
upper triangular matrices, and 
$W=S_n$ the Weyl group (which in this case is the symmetric group on $n$ letters).
$W$ is generated by the simple reflections $s_i$ for $1 \leq i \leq n-1$, where 
$s_i$ is the transposition exchanging $i$ and $i+1$, and it contains 
a longest element, which we denote by $w_0$, with $\ell(w_0) = {n \choose 2}$.
The \emph{complete flag variety} $\Fl_n$ is the homogeneous
space $B\setminus \Gl_n$. 
Concretely, each element $g$ of $\Gl_n$ gives rise to a flag of 
subspaces $\{V_1 \subset V_2 \subset \dots \subset V_n\}$, 
where $V_i$ denotes the span of the top $i$ rows of $g$.
The action of $B$ on the left preserves the flag, so we can identify 
$\Fl_n$ with 
the set of \emph{flags} $\{V_1 \subset V_2 \subset \dots \subset V_n\}$
where $\dim V_i = i$.

Let $\pi:\Gl_n \to \Fl_n$  
denote the natural projection 
$\pi(g):= Bg$.  The Bruhat decomposition 
$$\Gl_n = \bigsqcup_{w\in W} BwB$$
projects to the Schubert decomposition 
$$\Fl_n = \bigsqcup_{w\in W} C_w$$
where $C_w = \pi(BwB)$ is the \emph{Schubert cell} associated to $w$, 
 isomorphic to $\C^{\ell(w)}$.
We also have the Birkhoff decomposition 
$$\Gl_n = \bigsqcup_{w\in W} BwB^+,$$ which projects to the 
{opposite} Schubert decomposition 
$$\Fl_n = \bigsqcup_{w\in W} C^w$$
where $C^w = \pi(B w B^+)$ is the \emph{opposite Schubert cell} 
associated to $w$, isomorphic to $\C^{\ell(w_0) - \ell(w)}$.

The intersection $$\mathcal{R}_{v,w}:=C^v \cap C_w$$
has been considered by Kazhdan and Lusztig \cite{KL} in relation to 
Kazhdan-Lusztig polynomials.  $\mathcal{R}_{v,w}$ is 
nonempty only if $v \leq w$ in the Bruhat order of $W$, 
and it is then a smooth irreducible locally closed subset of $C_w$ 
of dimension $\ell(w)-\ell(v)$.  Sometimes $\mathcal{R}_{v,w}$
is called an \emph{open Richardson variety} \cite{KLS} because its closure 
is a \emph{Richardson variety} \cite{Rich}.
We have a stratification of the complete flag variety
$$\Fl_n = \bigsqcup_{v \leq w} \mathcal{R}_{v,w}.$$

%\Comment{Do we really need the minimal-length coset reps on both sides?
%If so, let's think carefully about the best notation, I'm not thrilled 
%with the above.}

%=:\mathcal{P}_{v, w}$ \Comment{is this notation worth it?} 


\subsection{Notation for 
 the Grassmannian}

Fix $1 < k < n$.
The parabolic subgroup 
$W_K = \langle s_1,\dots,s_{k-1}\rangle \times \langle s_{k+1}, s_{k+2},\dots,
s_{n-1} \rangle < W$ 
gives rise to a parabolic subgroup 
%$P_K$ in $\Gl_n$, namely
$P_K = \bigsqcup_{w \in W_K} B \dot{w} B$ in $\Gl_n$, where $\dot{w}$ is a matrix representative for $w$
in $\Gl_n$.
The longest element $w_K$ of $W_K$ has length
 $\ell(w_K) = {k \choose 2} + {n-k \choose 2}$. 
%\Comment{replace $n-k+1$ by $n-k$?}

The \emph{Grassmannian} $Gr_{k,n}$ 
is the homogeneous space 
$P_K\setminus \Gl_n$.
We can think of the 
{Grassmannian} $Gr_{k,n} = 
P_K\setminus \Gl_n$ more concretely as 
the set of all $k$-planes in an $n$-dimensional
vector space $\CC^n$. 
An element of
$Gr_{k,n}$ can be viewed as a 
$k\times n$ matrix of rank $k$, modulo left
multiplication by invertible $k\times k$ matrices.  
That is, two $k\times n$ matrices of rank $k$ represent the same point in $Gr_{k,n}$ if and only if they
can be obtained from each other by invertible row operations.

For a positive integer $a$ and $w \in W$, let $[a]:=[1, a]$ and $w[a]:=\{w(1), \dots, w(a)\}$. Let $\binom{[n]}{k}$ be the set of all $k$-element 
subsets of $[n]$. 

Given $V\in Gr_{k,n}$ represented by a $k\times n$ matrix $A$, for $I\in \binom{[n]}{k}$ we let $\Delta_I(V)$ be the maximal minor of $A$ located in the column set $I$. The $\Delta_I(V)$ do not depend on our choice of matrix $A$ (up to simultaneous rescaling by a nonzero constant), and are called the {\itshape Pl\"{u}cker coordinates} of $V$.
The Pl\"ucker coordinates give an embedding of $Gr_{k,n}$ into projective space of dimension
${n \choose k} - 1$.

We have the usual projection $\pi_k$ from the complete flag variety $\Fl_n$ to the 
Grassmannian $Gr_{k,n}$.
Let
$W^K_{\max}$ denote the set of
maximal-length coset representatives for $W_K \setminus W$. 
%;we also let
%%$^KW$ 
%$^{K}W$ (or $^{K}_{\min}W$)
%denote the set of 
%minimal-length coset representatives for $W/W_K$. Such a permutation $\sigma \in S_n$ is called 
%a \emph{Grassmannian permutation} of type $(k,n)$; it has the property that it has at most one descent, and when present, that descent must be in position $k$, i.e.
%$\sigma(k)>\sigma(k+1)$.  

Rietsch studied the projections 
of the open Richardson varieties in the complete flag variety to 
partial flag varieties \cite{RietschThesis}.  In particular,
when  $v\in W^K_{\max}$, 
the projection $\pi_k$ is an isomorphism from $\mathcal{R}_{v,w}$ to 
 $\pi_k(\mathcal{R}_{v,w})$.  
We obtain a stratification 
$$Gr_{k,n}=\bigsqcup_{v\leq w} \pi_k(\mathcal{R}_{v,w})$$
where $(v,w)$ range over all $v\in W^K_{\max}$, $w\in W$, such that 
$v\leq w$.
 Following work of Postnikov \cite{Postnikov, KLS},
 the strata $\pi_k(\mathcal{R}_{v,w})$ are sometimes called 
 \emph{open positroid varieties}, while their closures
 are called \emph{positroid varieties}. It follows from the definitions (see e.g. \cite[Section 6]{KLS}) that 
positroid varieties include Schubert varieties
in the Grassmannians, which we now define. 


\begin{definition}
Let $I\in \binom{[n]}{k}$.
The \emph{Schubert cell} $\Omega_{I}$  is defined to be the set
\begin{multline*}
\{A \in Gr_{k,n}\ \vert \ \text{the lexicographically minimal nonvanishing
Pl\"ucker coordinate} \\ \text{of }A\text{ is }\Delta_{I}(A) \}.
\end{multline*}
	The \emph{Schubert variety} $X_{I}$ is the closure
	$\overline{\Omega_I}$ of $\Omega_I$.

%	Meanwhile the \emph{opposite Schubert cell} $\Omega^{I}$  is defined to be 
%$$\Omega^{I} = \{A \in Gr_{k,n}\ \vert \ \text{the lexicographically maximal 
%nonvanishing
%Plucker coordinate of }A\text{ is }\Delta_{I}(A) \}.$$
%	The \emph{opposite Schubert variety} $X^{I}$ is defined to be the 
%	closure $\overline{\Omega^I}$ of $\Omega^I$.
\end{definition}

%It's easy to see 
%that elements $v$ of $W^K_{\max}$ 
%and elements $w$ of $W^K_{\min}$
%are also in bijection with $k$-element subsets of $[n]$.
%When $w\in W^K_{\min}$, 
%$\overline{\pi_k(\mathcal{R}_{e,w})}$  
%%\Comment{Kh: we should be consistent with notation $\pi_K$ vs $\pi_k$ that appears above}
%is isomorphic to the opposite Schubert variety $X^{w^{-1}[k]}$ in the Grassmannian, which has dimension 
%$\ell(w)$.  
%Similarly, 
When $v\in W^K_{\max}$,
$\overline{\pi_k(\mathcal{R}_{v,w_0})}$ is isomorphic to the 
Schubert variety $X_{v^{-1}[k]}$ in the Grassmannian, 
which has dimension 
$\ell(w_0)-\ell(v)$. We therefore refer to $\pi_k(\mathcal{R}_{v, w_0})$ as an \emph{open Schubert variety}.
More generally, if $v\in W^K_{max}$ and $w\in W$ 
has a factorization of the form $w=xv$ which is \emph{length-additive}, i.e. where 
$\ell(w) = \ell(x)+\ell(v)$, then we refer to 
$\overline{\pi_k(\mathcal{R}_{v,w})}$ (respectively, $\pi_k(\mathcal{R}_{v,w})$) as a \emph{skew Schubert variety} (respectively, open skew Schubert variety).
%\Comment{I think these are switched. With the current definitions, $\overline{\pi_k(\mathcal{R}_{e,w})}$ is isomorphic to the opposite Schubert variety $S^{I(w)}$ and $\overline{\pi_k(\mathcal{R}_{v,w_0})}$ is isomorphic to $S_{I(v)}$}

Let $\lambda$
%= (\lambda_1,\dots,\lambda_l)$ with 
%$n-k \geq \lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_l \geq 0$ and $l \leq k$
 denote a Young diagram contained in a $k \times (n-k)$ rectangle.  
%Such a Young diagram
%indexes both a \emph{Schubert variety} $S_{\lambda}$ and 
%an \emph{opposite Schubert variety} $S^{\lambda}$ in $Gr_{k,n}$ as follows.
We can identify $\lambda$ with its southeast boundary; we think of the boundary as a lattice path $\pathsw{\lambda}$ in the rectangle from the northeast corner to the southwest corner taking steps west 
and south%($\swarrow$ indicates the path goes southwest)
.
Labeling the steps of $\pathsw{\lambda}$ from $1$ to $n$, the labels of the 
south steps give a $k$-element subset of $[n]$.
Conversely, each $I \in \binom{[n]}{k}$ can be identified with a 
Young diagram, denoted $\partsw{I}$. 
(Later we will also need an analogous partition $\partne{I}$ obtained by reading the boundary of $\lambda$ from 
southwest to northeast.)
%Since this gives a bijection between 
%Young diagrams contained in a $k \times (n-k)$ rectangle 
%and $k$-element subsets  of $[n]$, 
The map $\partsw$  allows us to index open and closed Schubert 
%and opposite 
%Schubert 
varieties by Young diagrams, denoting them 
$X_{\lambda}$ and $X_{\lambda}^{\circ}$
respectively.  
The dimension of $X_{\lambda}$ and $X_{\lambda}^{\circ}$ is $|\lambda|$, the number of boxes of 
$\lambda$.%, while the codimension of $\Omega^{\lambda}$ and $X^{\lambda}$ is $|\lambda|$.






%\begin{remark} ``Going northeast" along the lattice path $\pathsw{\lambda}$ gives rise to an analogous bijection between Young diagrams in a $k \times (n-k)$ rectangle and $k$-element subsets of $n$. We use similar notation as above, switching each $\swarrow$ to a $\nearrow$. 
%So a Young diagram $\lambda$ is identified with the lattice path $\pathne{\lambda}$ in the rectangle taking steps east and north from the southwest corner of the rectangle to the northeast corner. If we label the path with $1$ to $n$, the labels of the north steps give the $k$-element subset $\vertne{\lambda}.$, and the Grassmannian permutation $\ppermne{\lambda}$ is obtained by reading the labels of the horizontal steps in $\pathne{\lambda}$ and then reading the labels of the vertical steps.
% After switching to \pperms from \perms, I switched the words horizontal
	%and vertical at the end of this remark.
%\end{remark}

%If $w=w_0$, then $\pi_k(\mathcal{R}_{v, w})$ is a Schubert variety\Comment{reference?}; we will see in \cref{sec:whichpositroids} which Schubert variety it is.



\subsection{The main result}

We now state the main result.  Note that 
the definitions of plabic graph and trip permutation can be found in 
\cref{sec:background}.

We associate with a Young diagram $\lambda$ a permutation
%$\permsw{\lambda}$: 
%in list notation, this permutation is obtained by first reading 
%the labels of the vertical steps of $\pathsw{\lambda}$, and then reading the labels of the 
%horizontal steps of $\pathsw{\lambda}$.
%Note that $\ell(\permsw{\lambda}) = k(n-k)-|\lambda|$.
$\ppermsw{\lambda}$: 
in list notation, this permutation is obtained by first reading 
the labels of the horizontal steps of $\pathsw{\lambda}$, and then reading the labels of the 
vertical steps of $\pathsw{\lambda}$.
(Moreover any fixed points in positions $1,2,\dots, n-k$ are ``black"
and any fixed points in positions $n-k+1,\dots, n$ are ``white.")
%\Comment{Lauren replaced the old $\permsw{\lambda}$ with 
%$\ppermsw{\lambda}$, which has the property that 
%$\ppermsw{\lambda} = \permsw{\lambda} \pi_{k,n}$, where 
%$\pi_{k,n} = (k+1,k+2,\dots,n, 1, 2, \dots, k)$ in list notation.
%}

\begin{theorem}\label{thm:main}
	Consider the open Schubert variety $X_{\lambda}^{\circ}$ of $Gr_{k,n}$. 
	%Let $\pi_{k,n} \in S_n$ be the permutation $\pi_{k,n}:i \to i+k$ (considered modulo $n$).
	Let $G$ be a reduced plabic graph (with boundary vertices
	labeled clockwise from $1$ to $n$) with trip permutation 
	%$\permsw{\lambda} \pi_{k,n}$.
	$\ppermsw{\lambda}$.
Construct the dual quiver of $G$ and label its vertices by the Pl\"ucker coordinates
given by the target labeling of $G$, see \cref{def:faces} and \cref{fig:plabic2}.
The coordinate ring of (the affine cone over) $X_{\lambda}^{\circ}$ is a 
cluster algebra, and this labeled quiver gives a seed for this cluster algebra.
\end{theorem}



%\begin{figure}[h]
%\centering
%\includegraphics[height=.4\textheight]{Schubert_seed}
	%\caption{A plabic graph $G$ for $Gr_{3,7}$ with trip permutation 
	%$\ppermsw{\lambda}=(2,4,6,7,1,3,5)$, for $\lambda=(4, 3, 2)$, with target labels. Below and to the left, the dual quiver of $G$.}
%\label{figures}
%\end{figure}


\begin{figure}[h]%[htbp]
\begin{center}
\setlength{\unitlength}{.9pt}
\begin{picture}(100,120)(-70,-70)
\thicklines
\put(15,30){\circle{4}}
\put(-18,0){\circle*{4}}
\put(15,0){\circle*{4}}
\put(47,0){\circle*{4}}
\put(13,30){\line(-31,23){25}}
\put(17,30){\line(31,23){25}}
\put(13,28){\line(-25,-23){30}}
\put(17,28){\line(25,-23){30}}
\put(15,28){\line(0,-1){29}}
\put(-18,0){\line(-1,0){28}}
\put(-18,0){\line(1,-1.1){17}}
\put(47,0){\line(-1,-1.2){16}}
\put(47,0){\line(1,0){28}}
\put(15,-5){\circle{120}}
\put(15,-65){\circle*{3}}
\put(-1,-20){\circle{3}}
\put(-12,48){\circle*{3}}
\put(31,-20){\circle{3}}
\put(42,48){\circle*{3}}
\put(-45,0){\circle*{3}}
\put(75,0){\circle*{3}}
\put(-25,-25){\circle{3}}
	\put(7,-46){\circle*{3}}
\put(-29,-46){\circle*{3}}
\put(59,-46){\circle*{3}}
\put(-29,-46){\line(5,20){5}}
	\put(-24,-25){\line(5,20){6.5}}
	\put(-24,-25){\line(10,-7){30}}
	\put(-1,-20){\line(5,-14){16}}
	\put(15,0){\line(-10,-12){16}}
	\put(15,0){\line(10,-12){16}}
\put(59,-46){\line(-20,20){26}}         
\put(-14,54){\makebox(0,0){$\mathbf{1}$}}
\put(45,54){\makebox(0,0){$\mathbf{2}$}}
\put(80,0){\makebox(0,0){$\mathbf{3}$}}
\put(64,-50){\makebox(0,0){$\mathbf{4}$}}
\put(15,-72){\makebox(0,0){$\mathbf{5}$}}
\put(-34,-50){\makebox(0,0){$\mathbf{6}$}}
\put(-50,0){\makebox(0,0){$\mathbf{7}$}}

\put(13,40){\line(0,1){5}}
\put(13,40){\line(1,0){5}}
\put(13,45){\line(1,0){5}}
\put(18,40){\line(0,1){5}}

\put(50,20){\line(0,1){5}}
\put(50,20){\line(1,0){5}}
\put(50,25){\line(1,0){5}}
\put(55,20){\line(0,1){5}}

\put(60,-20){\line(0,1){5}}
\put(60,-20){\line(1,0){5}}
\put(60,-15){\line(1,0){5}}
\put(65,-20){\line(0,1){5}}

\put(-34,-20){\line(0,1){5}}
\put(-34,-20){\line(1,0){5}}
\put(-34,-15){\line(1,0){5}}
\put(-29,-20){\line(0,1){5}}

\put(-14,-50){\line(0,1){5}}
\put(-14,-50){\line(1,0){5}}
\put(-14,-45){\line(1,0){5}}
\put(-9,-50){\line(0,1){5}}

\put(12,-27){\line(0,1){5}}
\put(12,-27){\line(1,0){5}}
\put(12,-22){\line(1,0){5}}
\put(17,-27){\line(0,1){5}}

\put(-25,20){\line(0,1){5}}
\put(-25,20){\line(1,0){5}}
\put(-25,25){\line(1,0){5}}
\put(-20,20){\line(0,1){5}}

\put(30,5){\circle{5}}
\put(0,5){\circle{5}}
\put(-12,-24){\circle{5}}
\put(32,8){{\vector(4,3){17}}}
\put(29,4){{\vector(-4,-7){15}}}
\put(2,4){{\vector(1,0){25}}}
\put(0,3){{\vector(-5,-10){12}}}
\put(-12,-26){{\vector(1,0){24}}}
\put(-14,-25){{\vector(-3,1){16}}}
\put(-12,-45){{\vector(0,1){18}}}
\put(14,-20){{\vector(-2,3){15}}}
\put(-20,20){{\vector(15,-13){17}}}
\put(60,-15){{\vector(-3,2){28}}}
\end{picture}
\qquad \qquad
\qquad \qquad
\begin{picture}(100,120)(-70,-70)
\thicklines
\put(15,30){\circle{4}}
\put(-18,0){\circle*{4}}
\put(15,0){\circle*{4}}
\put(47,0){\circle*{4}}
\put(13,30){\line(-31,23){25}}
\put(17,30){\line(31,23){25}}
\put(13,28){\line(-25,-23){30}}
\put(17,28){\line(25,-23){30}}
\put(15,28){\line(0,-1){29}}
\put(-18,0){\line(-1,0){28}}
\put(-18,0){\line(1,-1.1){17}}
\put(47,0){\line(-1,-1.2){16}}
\put(47,0){\line(1,0){28}}
\put(15,-5){\circle{120}}
\put(15,-65){\circle*{3}}
\put(-1,-20){\circle{3}}
\put(-12,48){\circle*{3}}
\put(31,-20){\circle{3}}
\put(42,48){\circle*{3}}
\put(-45,0){\circle*{3}}
\put(75,0){\circle*{3}}
\put(-25,-25){\circle{3}}
	\put(7,-46){\circle*{3}}
\put(-29,-46){\circle*{3}}
\put(59,-46){\circle*{3}}
\put(-29,-46){\line(5,20){5}}
	\put(-24,-25){\line(5,20){6.5}}
	\put(-24,-25){\line(10,-7){30}}
	\put(-1,-20){\line(5,-14){16}}
	\put(15,0){\line(-10,-12){16}}
	\put(15,0){\line(10,-12){16}}
\put(59,-46){\line(-20,20){26}}         
\put(-14,54){\makebox(0,0){$\mathbf{1}$}}
\put(44,54){\makebox(0,0){$\mathbf{2}$}}
\put(80,0){\makebox(0,0){$\mathbf{3}$}}
\put(64,-50){\makebox(0,0){$\mathbf{4}$}}
\put(15,-72){\makebox(0,0){$\mathbf{5}$}}
\put(-34,-50){\makebox(0,0){$\mathbf{6}$}}
\put(-50,0){\makebox(0,0){$\mathbf{7}$}}

\put(15,40){\makebox(0,2){$235$}}
\put(15,15){\makebox(24,-20){$356$}}
\put(15,15){\makebox(-25,-20){$357$}}
\put(0,30){\makebox(-25,-20){$135$}}
\put(50,20){\makebox(0,0){$345$}}
\put(60,-15){\makebox(0,0){$456$}}
\put(30,-45){\makebox(0,0){$567$}}
\put(-10,-48){\makebox(0,0){$167$}}
\put(-32,-15){\makebox(0,0){$137$}}
\put(-12,-22){\makebox(0,0){$157$}}
\end{picture}
\end{center}
%\vspace{-.1in} 
	\caption{A plabic graph $G$ for $Gr_{3,7}$ with trip permutation 
	$\ppermsw{\lambda}=(2,4,6,7,1,3,5)$, for $\lambda=(4, 3, 2)$, together with the dual quiver of $G$ and the target face 
	labeling.}
%\caption{A plabic graph $G$ together with
% $Q(G)$ and  its face labeling $\mathcal{F}_{\source}(G)$.
%Here $\pi_G = (3,4,5,1,2)$.}
\label{fig:plabic2}
\end{figure}




We actually prove something a bit more general than \cref{thm:main}.

\begin{theorem}\label{thm:main2}
Consider the open skew Schubert variety 
	$\pi_k(\mathcal{R}_{v,w})$,
where $v\in W^K_{max}$ and 
$w$ has a length-additive factorization $w=xv$.
Let $G$ be a reduced plabic graph
(with boundary vertices labeled clockwise from $1$ to $n$) with 
trip permutation $vw^{-1} = x^{-1}$,  such that boundary lollipops
are white if and only if they are in $[k]$. Then the coordinate
ring of (the affine cone over) the open
skew Schubert variety $\pi_k(\mathcal{R}_{v,w})$
is a cluster algebra, and $G$ gives rise to a seed as follows: apply $v^{-1}$ to the boundary vertices of $G$ and then label the dual quiver using the target labeling.
\end{theorem}

%Our theorem is that for any $w=xv$, where the lengths add, and 
%$v\in W^K_{max}$, then if we choose a plabic graph (labels are clockwise)
%with trip permutation
%$v w^{-1}$, and fixed points are white if and only if they are in $[k]$,
%\footnote{see our email correspondence of April 2-3}
%and relabel boundary vertices by 
%$v^{-1}$, then the target labeling plus dual quiver give us a seed for the
%cluster algebra.  (and in this case the coordinate ring has a cluster structure) 
In the case of Schubert varieties, \cref{thm:main} resolves
\cref{conj:vague}.
%which has been believed to be true by experts for some time,
%though it wasn't written down explicitly as a conjecture
%until recently, see \cite[Conjecture 3.4]{MullerSpeyer0}.  
Note that 
there is another version of the conjecture which uses the \emph{source
labeling} of $G$ instead of the 
target labeling \cite[Remark 3.5]{MullerSpeyer0}.
Both conjectures make sense more generally for positroid varieties
and arbitrary reduced plabic graphs (whose trip permutations can be
arbitrary decorated permutations).
However, the cluster structure that we give in \cref{thm:main2}
is different from either of the cluster structures proposed in 
\cite{MullerSpeyer0}.  

\begin{rem} When $\pi_k(\mathcal{R}_{v, w})$ is not an open skew Schubert variety, the seeds in Leclerc's cluster subalgebra 
in general do not come from generalized plabic graphs.  Indeed, for $v=(2, 5, 1, 4, 3)$ and $w=(5, 3, 4, 2, 1)$, the unique
	seed in Leclerc's cluster subalgebra for $\pi_k(\mathcal{R}_{v, w})$ consists of frozen variables and has extended cluster $\{\Delta_{13}, \Delta_{23}, \Delta_{14}, \Delta_{15}, \Delta_{45}\}$. These Pl\"ucker coordinates cannot be obtained as the set of face labels of any (generalized) plabic graph
	(note that the label $2$ occurs only once in the set of Pl\"ucker coordinates).
\end{rem}




\subsection{Outline of the proof}

While each open skew Schubert variety 
$\pi_k(\mathcal{R}_{v,w})$
(where 
$v=w_K v'\in W^K_{max}$ 
and $w\in W$ has a length-additive factorization 
$\mathbf{w}=\mathbf{xv}=\mathbf{x w_K v'}$ into reduced expressions for $x$, $w_K$, and $v'$)
corresponds to an equivalence class of plabic graphs, 
%(more generally to a collection of cluster seeds), 
there is 
one among them which is particularly nice, which we call the \emph{rectangles seed}. 
The first step of our proof is to give an explicit description of the rectangles seed for each open skew Schubert variety
$\pi_k(\mathcal{R}_{v,w})$, in terms of $v$ and a Young diagram associated to $(v,w)$.
%The quiver of the rectangles seed can be described easily in terms of $\partsw{w_0x[k]}$ and the Pl\"ucker coordinates can be obtained using $\partsw{w_0x[k]}$ and $v$.


A construction of Karpman \cite{Karpman} produces
a bridge-decomposable plabic graph associated to a pair $(y,\mathbf{z})$, where 
$y^{-1} \in W^K_{\max}$, $\mathbf{z}$ is a reduced decomposition for $z$, and $y\leq z$.
The second step of our proof is to show that if we perform her construction for the pair 
$(w_K, \mathbf{x w_K})$ and then relabel boundary vertices of the resulting plabic graph by $v^{-1}$ to obtain a graph $G$, 
the target labeling of the dual quiver of $G$ gives rise to 
 the rectangles seed 
for $\pi_k(\mathcal{R}_{v,w})$. 

 In \cite{Leclerc}, Leclerc produces a cluster seed
 associated to each pair $(v,\mathbf{w})$, where $v\in W^K_{max}$ and $v \leq w$.
 The third step of our proof is to verify that for the choice $(v, \mathbf{w} = \mathbf{x w_K v'})$,  
Leclerc's construction gives rise to the rectangles seed.
To prove \cref{thm:main2} from the previous steps, we show that mutations of the plabic graph $G$ (known as ``square moves") coincide with certain mutations of the rectangles seed. \cref{thm:main} is then deduced from \cref{thm:main2}.

%which are the 
%setting for
% \cref{thm:main2}.

\subsection{Applications of the main result}
\label{sec:applications}

In this section we sketch some applications of the main result,
including ring-theoretic properties for the coordinate rings of open
skew Schubert varieties, canonical bases, and a classification of the 
finite type cluster structures we obtain.

Combining \cref{thm:main} and \cref{thm:main2} with results of Muller and Speyer
\cite{Muller}, \cite[Theorem 3.3]{MullerSpeyer0}, 
we find that the coordinate rings of open Schubert and skew Schubert varieties (viewed as cluster algebras) are \emph{locally acyclic},
which implies that they are finitely generated, normal, locally a complete
intersection, and equal to their own upper cluster algebras.

Combining our results with results of Ford-Serhiyenko \cite[Theorem 1.2]{FordSer}, 
we find that the quivers giving
rise to the cluster structures for open Schubert and skew Schubert varieties admit
\emph{green-to-red sequences}, which by Gross-Hacking-Keel-Kontsevich \cite{GHKK} implies that the cluster algebras have
\emph{Enough Global Monomials} and hence 
each coordinate ring has a canonical basis of
\emph{theta functions}, parameterized by the lattice of $g$-vectors.



%\subsubsection{Schubert varieties whose cluster structure has finite type}

%Recall that there is a simple way to obtain a cluster seed from the 
%Young diagram indexing a Schubert variety, see \cref{PPQ}.
%
%
%\begin{figure}[h]
%\centering
%\includegraphics[height=2in]{Partition-Plabic-Quiver.pdf}
%\caption{The plabic graph and quiver associated to Young diagram.}
%\label{PPQ}
%\end{figure}

In \cite{Scott}, Scott classified the Grassmannians whose coordinate rings
have a cluster algebra of finite type.  He showed that in general the
cluster algebras have infinite type, except in the following cases:
the coordinate ring of $Gr_{2,n}$ is a cluster algebra of type $A_{n-3}$,
while the coordinate rings of $Gr_{3,6}$, $Gr_{3,7},$ and $Gr_{3,8}$ are
cluster algebras of types $D_4$, $E_6$, and $E_8$, respectively.

It is straightforward to classify for which open skew Schubert varieties $\pi_k(\mathcal{R}_{v, w})$ 
the cluster structure described here is finite type. It depends only on $wv^{-1}$.

\begin{proposition} Let $v \leq w$, where $v \in W^K_{\max}$ and $w=xv$ is length-additive. Let $\lambda=\partne{x[k]}$ 
	and let $\lambda'$ be the Young diagram obtained from $\lambda$ by removing all boxes that touch the southeast boundary of $\lambda$ either along an edge or at the southeast corner. Then the cluster structure on the coordinate ring of 
	$\pi_k(\mathcal{R}_{v, w})$ given in \cref{thm:main2} is

\begin{enumerate}
\item type $A$ if and only if $\lambda'$ does not contain a $2 \times 2$ rectangle;
\item type $D$ if and only if $\lambda'=(i, 2)$ or its transpose for $i \geq 2$;
\item type $E_6$, $E_7$, or $E_8$ if and only if $\lambda'$  or its transpose is one of $(3, 3)$, $(3, 2, 1)$, $(4, 3)$, $(4, 2, 1)$, $(3, 3, 1)$, $(5, 3)$, $(5, 2, 1)$, $(4, 4)$, $(4, 2, 2)$.
\end{enumerate}
 
In particular, the open Schubert variety $X^{\circ}_{\lambda}$ is of finite type if and only if $\lambda'$ is in the above list.
\end{proposition}




%	+ Insert lemma about reduced expressions for Grassmannian permutations (ask Lauren for reference). Check existing conventions in Karpman, Leclerc(something) to figure out "standard" reading order

%\Comment{To do: 

%\begin{itemize}
%\item lemma about reduced expressions for Grassmannian permutations from Young diagrams. Standard reading order for such reduced expressions? (If we can find one that works with all of our results)
%\end{itemize}}

\section{Background on cluster structures and plabic graphs}
\label{sec:background}
\subsection{Background on cluster structures}
Cluster algebras are a class of rings with a particular 
combinatorial structure; they were introduced by Fomin and Zelevinsky in \cite{ca1}.

\begin{definition}%[Quiver]
\label{quiver}
A \emph{quiver} $Q$ is a directed graph; we will assume that $Q$ has no 
loops or $2$-cycles.
%If there are $i$ arrows from vertex $\lambda$ to $\mu$, then 
%we will set $b_{\lambda \mu} = i$ and $b_{\mu \lambda} = -i$.
Each vertex is designated either  \emph{mutable} or \emph{frozen}.
%The skew-symmetric matrix $B = (b_{\lambda \mu})$ is called the \emph{exchange matrix} of $Q$.
\end{definition}

\begin{definition}%[Quiver Mutation]
Let $q$ be a mutable vertex of quiver $Q$.  The quiver mutation 
$\mu_q$ transforms $Q$ into a new quiver $Q' = \mu_q(Q)$ via a sequence of three steps:
\begin{enumerate}
\item For each oriented two path $r \to q \to s$, add a new arrow $r \to s$
(unless $r$ and $s$ are both frozen, in which case do nothing).
\item Reverse the direction of all arrows incident to the vertex $q$.
\item Repeatedly remove oriented $2$-cycles until unable to do so.
\end{enumerate}
\end{definition}


\begin{definition}
%[\emph{Labeled seeds}]
\label{def:seed0}
Choose $M\geq N$ positive integers.
Let $\Fcal$ be an \emph{ambient field}
of rational functions
in $N$ independent
variables
over
$\C(x_{N+1},\dots,x_M)$.
A \emph{labeled seed} in~$\Fcal$ is
a pair $(\xx, Q)$, where
$\xx = (x_1, \dots, x_M)$ forms a free generating
set for
$\Fcal$,
and
$Q$ is a quiver on vertices
$1, 2, \dots,N, N+1, \dots, M$,
whose vertices $1,2, \dots, N$ are
\emph{mutable}, and whose vertices $N+1,\dots, M$ are \emph{frozen}.

We refer to~$\xx$ as the (labeled)
\emph{extended cluster} of a labeled seed $(\xx, Q)$.
The variables $\{x_1,\dots,x_N\}$ are called \emph{cluster
variables}, and the variables $c=\{x_{N+1},\dots,x_M\}$ are called
\emph{frozen} or \emph{coefficient variables}.
We often view the labeled seed as a quiver $Q$ where each vertex $i$ is labeled by 
the corresponding variable $x_i$.
\end{definition}

\begin{definition}
%[\emph{Seed mutations}]
\label{def:seed-mutation0}
Let $(\xx, Q)$ be a labeled seed in $\Fcal$,
and let $q \in \{1,\dots,N\}$.
The \emph{seed mutation} $\mu_q$ in direction~$q$ transforms
$(\xx, Q)$ into the labeled seed
$\mu_q(\xx,  Q)=(\xx', \mu_q(Q))$, where the cluster
$\xx'=(x'_1,\dots,x'_M)$ is defined as follows:
$x_j'=x_j$ for $j\neq q$,
whereas $x'_q \in \Fcal$ is determined
by the \emph{exchange relation}
\begin{equation*}
\label{exchange relation0}
x'_q\ x_q = 
% \ \prod_{\substack{\alpha\in Q_1 \\ s(\alpha)=q}} x_{t(\alpha)}
%+ \ \prod_{\substack{\alpha\in Q_1 \\ t(\alpha)=q}} x_{s(\alpha)} \, .
\prod_{q \to r} x_r + \prod_{s \to q} x_s,
\end{equation*}
where the first product is over all arrows $q \to r$ in $Q$
which start at $q$, and the second product is over all arrows $s\to q$ which 
end at $q$.
\end{definition}


It is not hard to check that seed mutation is an involution. Note that arrows between two frozen vertices of a quiver do not
affect seed mutation (they do not affect the mutated quiver
or the exchange relation).  For that reason, one may omit
arrows between two frozen vertices. 


\begin{definition}
%[\emph{Patterns}]
\label{def:patterns0}
Consider the \emph{$N$-regular tree}~$\TT_N$
whose edges are labeled by the numbers $1, \dots, N$,
so that the $N$ edges emanating from each vertex receive
different labels.
A \emph{cluster pattern}  is an assignment
of a labeled seed $\Sigma_t=(\xx_t, Q_t)$
to every vertex $t \in \TT_N$, such that the seeds assigned to the
endpoints of any edge $t \overunder{q}{} t'$ are obtained from each
other by the seed mutation in direction~$q$.
The components of
$\xx_t$ are written as $\xx_t = (x_{1;t}\,,\dots,x_{N;t}).$
\end{definition}

Clearly, a cluster pattern  is uniquely determined
by an arbitrary  seed.


\begin{definition}
%[\emph{Cluster algebra}]
\label{def:cluster-algebra0}
Given a cluster pattern, we denote
\begin{equation*}
\label{eq:cluster-variables0}
\Xcal
= \bigcup_{t \in \TT_N} \xx_t
= \{ x_{i,t}\,:\, t \in \TT_N\,,\ 1\leq i\leq N \} \ ,
\end{equation*}
the union of clusters of all the seeds in the pattern.
The elements $x_{i,t}\in \Xcal$ are called \emph{cluster variables}.
%Let $c=\{x_{n+1},\dots,x_m\}$ be the \emph{frozen} or \emph{coefficient variables}.
The
\emph{cluster algebra} $\Acal$ associated with a
given pattern is the $\CC[x_{N+1}^{\pm 1}, \dots, x_M^{\pm 1}]$-subalgebra of the ambient field $\Fcal$
generated by all cluster variables: $\Acal = \CC[c^{\pm 1}] [\Xcal]$.
We denote $\Acal = \Acal(\xx,  Q)$, where
$(\xx,Q)$
is any seed in the underlying cluster pattern.
In this generality,
$\Acal$ is called a \emph{cluster algebra from a quiver}, or a
\emph{skew-symmetric cluster algebra of geometric type.}
\end{definition}


\subsection{Background on plabic graphs}

In this section 
we review Postnikov's notion of \emph{plabic graphs} \cite{Postnikov}.


\begin{definition}
A {\it plabic (or planar bicolored) graph\/}
is an undirected graph $G$ drawn inside a disk
(considered modulo homotopy)
with $n$ {\it boundary vertices\/} on the boundary of the disk,
labeled $1,\dots,n$ in clockwise order, as well as some
colored {\it internal vertices\/}.
These internal vertices
are strictly inside the disk and are
colored in black and white. 
An internal vertex of degree one adjacent to a boundary vertex is a \emph{lollipop}.
We will always assume that no vertices of the same color are adjacent, and that 
each boundary vertex $i$ is adjacent to a single internal vertex.
	%\Comment{Melissa changed this convention in order to talk about lollipops}

\end{definition}

See \cref{fig:plabic2} for an example of a plabic graph.
%\begin{figure}[h]
%\centering
%\includegraphics[height=1in]{G25}
%\caption{A plabic graph}
%\label{G25}
%\end{figure}


There is a natural set of local transformations (moves) of plabic graphs, which we now describe.
Note that we will always assume that a plabic graph $G$ has no isolated 
components (i.e. every connected component contains at least
one boundary vertex).  We will also assume that $G$ is \emph{leafless}, 
i.e.\ if $G$ has an 
internal vertex of degree $1$, then that vertex must be adjacent to a boundary
vertex.

(M1) SQUARE MOVE (Urban renewal).  If a plabic graph has a square formed by
four trivalent vertices whose colors alternate,
then we can switch the
colors of these four vertices (and add some degree $2$ vertices to preserve
the property that no vertices of the same color are adjacent).

(M2) CONTRACTING/EXPANDING A VERTEX.
Any degree $2$ internal vertex not adjacent to the boundary can be deleted,
and the two adjacent vertices merged.
This operation can also be reversed.  Note that this operation can always be used
to change an arbitrary
 square face of $G$ into a square face whose four vertices are all trivalent.


(M3) MIDDLE VERTEX INSERTION/REMOVAL.
We can always remove or add degree $2$ vertices at will, subject to the 
  condition that the graph remains bipartite.

See \cref{M1} for depictions of these three moves.


\begin{figure}[h]
\centering
\includegraphics[height=.5in]{squaremove}
\hspace{.5in}
\raisebox{6pt}{\includegraphics[height=.4in]{contractmove}}
\hspace{.5in}
\raisebox{16pt}{\includegraphics[height=.07in]{M3}}
\caption{%
	Moves (M1), (M2), (M3).}
\label{M1}
\end{figure}


(R1) PARALLEL EDGE REDUCTION.  If a plabic graph contains
two trivalent vertices of different colors connected
by a pair of parallel edges, then we can remove these
vertices and edges, and glue the remaining pair of edges together.

\begin{figure}[h]
\centering
\includegraphics[height=.25in]{R1}
\caption{Parallel edge reduction}
\label{R1}
\end{figure}


\begin{definition}
Two plabic graphs are called \emph{move-equivalent} if they can be obtained
from each other by moves (M1)-(M3).  The \emph{move-equivalence class}
of a given plabic graph $G$ is the set of all plabic graphs which are move-equivalent
to $G$.
A leafless plabic graph without isolated components
is called \emph{reduced} if there is no graph in its move-equivalence
class to which we can apply (R1).
\end{definition}


\begin{definition} A \emph{decorated permutation} $\pi^:$ is a permutation $\pi \in S_n$ together with a coloring $\set{i \ \vert \ \pi(i)=i} \to \{\text{black, white}\}$. 
%We say $\pi^:$ is of \emph{type (k, n)}, where $k$ is the cardinality of the set $\set{i \in [n]\ \vert \ \pi^{-1}(i)>i \text{ or } i \text{is a white fixed point}}$.
\end{definition}

\begin{definition}\label{def:rules}
Given a reduced plabic graph $G$,
a  \emph{trip} $T$ is a directed path which starts at
some boundary vertex
$i$, and follows the ``rules of the road": it turns (maximally) right at a
black vertex,  and (maximally) left at a white vertex.
 Note that $T$ will also
end at a boundary vertex $j$; we then refer to this trip as
$T_{i \to j}$. Setting $\pi(i)=j$ for each such trip,
 we associate a (decorated) \emph{trip permutation}
$\pi_G=(\pi(1),\dots,\pi(n))$ to each reduced plabic graph $G$, where a fixed point $\pi(i)=i$ is colored white (black) if there is a white (black) lollipop at boundary vertex $i$.
%We say that $G$ has \emph{type $\pi_G$}.
\end{definition}

For example, the trip permutation of the
reduced plabic graph in \cref{fig:plabic2} is \linebreak $(2, 4, 6, 7, 1, 3, 5)$.

\begin{remark}\label{rem:moves}
%Let $\pi_{k,n} = 
%(n-k+1, n-k+2,\dots, n, 1, 2, \dots, n-k)$.  
%In this paper we will 
%be particularly concerned with reduced plabic graphs whose trip permutation
%is $\pi_{k,n}$.  
Note that the trip permutation of a plabic graph is preserved 
by the local moves (M1)-(M3), but not by (R1). For reduced plabic graphs the converse holds, namely 
it follows from \cite[Theorem 13.4]{Postnikov} 
that any two reduced plabic graphs with the same trip permutation are 
move-equivalent.
\end{remark}

%by a partition.

%\begin{definition}\label{def:facelabels}
%Let $G$ be a reduced plabic graph.  Note that 
%each trip $T_{i\to j}$ partitions the disk containing $G$ into two parts:
%the part on the left of $T_{i\to j}$, and the part on the right.  Place
%an $i$ in each face of $G$ which is to the left of $T_i$.  After doing
%this for all $1 \leq i \leq n$, each face will contain an $(n-k)$-element
%subset of $\{1,2,\dots,n\}$.  Finally we realise that
%$(n-k)$-element subset as the south steps of a corresponding Young diagram 
%in $\Shkn$. We let $\widetilde{\mathcal P}_G$ denote the set of Young diagrams inside $\Shkn$ associated in this way to $G$.   Note that $\widetilde{\mathcal P}_G$ always contains $\emptyset$ as the partition labeling a boundary region. We therefore set 
%${\mathcal P}_G:=\widetilde{\mathcal P}_G\setminus\{\emptyset\}$.
%Each reduced plabic graph $G$ of type $\pi_{k,n}$ will have 
%precisely $N+1$ faces, where $N=k(n-k)$ \cite{Postnikov}.
%\end{definition}



%\begin{figure}[h]%[htbp]
%\begin{center}
%\setlength{\unitlength}{.8pt}
%\begin{picture}(100,120)(-30,-70)
%\thicklines
%\multiput(1,0)(1,30){2}{\line(1,0){27.5}}
%\multiput(0,1)(30,1){2}{\line(0,1){27.5}}
%
%\put(15,15){\circle{5}}
%\put(15,-15){\circle{5}}
%
%\put(12,40){\line(0,1){5}}
%\put(12,40){\line(1,0){5}}
%\put(12,45){\line(1,0){5}}
%\put(17,40){\line(0,1){5}}
%
%\put(45,0){\line(0,1){5}}
%\put(45,0){\line(1,0){5}}
%\put(45,5){\line(1,0){5}}
%\put(50,0){\line(0,1){5}}
%
%\put(-25,0){\line(0,1){5}}
%\put(-25,0){\line(1,0){5}}
%\put(-25,5){\line(1,0){5}}
%\put(-20,0){\line(0,1){5}}
%
%\put(25,-50){\line(0,1){5}}
%\put(25,-50){\line(1,0){5}}
%\put(25,-45){\line(1,0){5}}
%\put(30,-50){\line(0,1){5}}
%
%\put(0,-50){\line(0,1){5}}
%\put(0,-50){\line(1,0){5}}
%\put(0,-45){\line(1,0){5}}
%\put(5,-50){\line(0,1){5}}
%
%\put(15,17){{\vector(0,1){22}}}
%\put(15,13){{\vector(0,-1){24}}}
%\put(-20,3){{\vector(2,.8){31}}}
%\put(43,3){{\vector(-2,.8){27}}}
%\put(13,-15){{\vector(-4,2){31}}}
%\put(16,-17){{\vector(1,-2.3){11}}}
%\put(5,-43){{\vector(1,2.5){10}}}
%
%\put(0,30){\circle{4}}
%\put(30,30){\circle*{4}}
%\put(30,0){\circle{4}}
%\put(0,0){\circle*{4}}
%\put(-10,-25){\circle{4}}
%\put(15,-40){\circle*{4}}
%%\put(40,-25){\circle{4}}           !!!
%\put(0,0){\line(-10,-25){9}}
%%\put(30,-1.5){\line(10,-25){9}}
%\put(15,-40){\line(-25,15){23}}
%%\put(15,-40){\line(25,15){23}}      !!!
%\put(15,-40){\line(20,50){15}}        %!!!
%\put(15,-5){\circle{120}}
%\put(15,-65){\circle*{3}}
%\put(15,-40){\line(0,-1){24}}
%\put(-12,48){\circle*{3}}
%\put(42,48){\circle*{3}}
%\put(-12,48){\line(12,-18){11}}
%\put(42,48){\line(-12,-18){11}}
%\put(-29,-46){\circle*{3}}
%\put(59,-46){\circle*{3}}
%\put(-29,-46){\line(19,21){18}}
%\put(59,-46){\line(-19,29){29}}         
%\put(-14,53){\makebox(0,0){$\mathbf{1}$}}
%\put(44,53){\makebox(0,0){$\mathbf{2}$}}
%\put(64,-50){\makebox(0,0){$\mathbf{3}$}}
%\put(15,-72){\makebox(0,0){$\mathbf{4}$}}
%\put(-33,-50){\makebox(0,0){$\mathbf{5}$}}
%\end{picture}
%\qquad \qquad
%\begin{picture}(100,120)(-70,-70)
%\thicklines
%\multiput(1,0)(1,30){2}{\line(1,0){27.5}}
%\multiput(0,1)(30,1){2}{\line(0,1){27.5}}
%\put(0,30){\circle{4}}
%\put(30,30){\circle*{4}}
%\put(30,0){\circle{4}}
%\put(0,0){\circle*{4}}
%\put(-10,-25){\circle{4}}
%\put(15,-40){\circle*{4}}
%%\put(40,-25){\circle{4}}
%\put(0,0){\line(-10,-25){9}}
%%\put(30,-1.5){\line(10,-25){9}}
%\put(15,-40){\line(-25,15){23}}
%%\put(15,-40){\line(25,15){23}}
%\put(15,-40){\line(20,50){15}}        %!!!
%\put(15,-5){\circle{120}}
%\put(15,-65){\circle*{3}}
%\put(15,-40){\line(0,-1){24}}
%\put(-12,48){\circle*{3}}
%\put(42,48){\circle*{3}}
%\put(-12,48){\line(12,-18){11}}
%\put(42,48){\line(-12,-18){11}}
%\put(-29,-46){\circle*{3}}
%\put(59,-46){\circle*{3}}
%\put(-29,-46){\line(19,21){18}}
%%\put(59,-46){\line(-19,21){18}}
%\put(59,-46){\line(-19,29){29}}         
%\put(-14,53){\makebox(0,0){$\mathbf{1}$}}
%\put(44,53){\makebox(0,0){$\mathbf{2}$}}
%\put(64,-50){\makebox(0,0){$\mathbf{3}$}}
%\put(15,-72){\makebox(0,0){$\mathbf{4}$}}
%\put(-33,-50){\makebox(0,0){$\mathbf{5}$}}
%
%\put(15,40){\makebox(0,0){$\mathbf{15}$}}
%\put(15,15){\makebox(0,0){$\mathbf{25}$}}
%\put(11,-15){\makebox(0,0){$\mathbf{24}$}}
%\put(60,0){\makebox(0,0){$\mathbf{12}$}}
%\put(30,-45){\makebox(0,0){$\mathbf{23}$}}
%\put(-5,-45){\makebox(0,0){$\mathbf{34}$}}
%\put(-25,0){\makebox(0,0){$\mathbf{45}$}}
%\end{picture}
%\end{center}
%%\vspace{-.1in} 
%\caption{A plabic graph $G$ together with
% $Q(G)$ and  its face labeling $\mathcal{F}_{\source}(G)$.
%Here $\pi_G = (3,4,5,1,2)$.}
%\label{fig:plabic2}
%\end{figure}
Now we use the notion of trips to label each face of $G$
by a Pl\"ucker coordinate.
Towards this end, note that every trip
will partition the faces of a plabic graph into
two parts: those on the left of the trip, and those on the right
of the trip.

\begin{definition}\label{def:faces}
Let $G$ be a reduced plabic graph with $b$ boundary vertices.
For each one-way trip $T_{i\to j}$ with $i \neq j$, we place the label $j$
 in every face which is to the left of $T_{i\to j}$. If $i=j$ (that is, $i$ is adjacent to a lollipop), we place the label $i$ 
in all faces if the lollipop is white and in no faces if the lollipop is black.
We then obtain a labeling $\mathcal{F}(G)$
of faces of $G$ by subsets of $[b]$ which
we call the \emph{target}
\emph{labeling} of $G$.  We identify each $a$-element subset of $[b]$
with the corresponding Pl\"ucker coordinate.
\end{definition}

%The right-hand side of
%\cref{fig:plabic2}
%shows
%a plabic graph with the face labeling
% $\mathcal{F}_{\source}(G)$.


%The left of Figure \ref{G25-partitions} shows the labeling
%of each face
%of our running example by a Young diagram in $\Shkn$
%(here $k=3$ and $n=5$).
%\begin{figure}[h]
%\centering
%\includegraphics[height=1in]{G25-partitions}
%\caption{A plabic graph $G$ with trip permutation $\pi_{3,5}$, with 
%faces labeled by Young diagrams in $\Sh_{3,5}$, and the corresponding quiver $Q(G)$.  Here $\mathcal P_G=\left\{\ydiagram{3,3},\ydiagram{2,2},\ydiagram{1,1},\ydiagram{3},\ydiagram{2},\ydiagram{1}\right\}$.}
%\label{G25-partitions}
%\end{figure}

The following statements relate quivers to plabic graphs.


\begin{definition}
Let $G$ be a reduced plabic graph.  The dual quiver $Q(G)$ of $G$ is defined as follows.  The vertices of 
$Q(G)$ are labeled by the faces of $G$.  We say that a vertex of $Q(G)$ is \emph{frozen}
if the 
corresponding face is incident to the boundary of the disk, and is \emph{mutable} otherwise.
For each edge $e$ in $G$ which separates two faces, at least one of which is mutable, 
we introduce an arrow connecting the faces;
 this arrow is oriented so that it ``sees the white endpoint of $e$ to the left and the 
black endpoint to the right'' as it crosses over $e$.  We then remove oriented $2$-cycles
from the resulting quiver, one by one, to get $Q(G)$. See 
\cref{fig:plabic2}.
\end{definition}


%The following lemma is straightforward, and is implicit in \cite{Scott}.

\begin{lemma}\label{lem:mutG}
If $G$ and $G'$ are related via a square move at a face,
then $Q(G)$ and $Q(G')$ are related via mutation at the corresponding vertex.
\end{lemma}

%Because of \cref{lem:mutG}, we sometimes refer to 
%``mutating" at a nonboundary face of $G$, meaning that we mutate
%at the corresponding vertex of quiver $Q(G)$.
%Note that in general the quiver $Q(G)$ admits mutations at vertices
%which do not correspond to moves of plabic graphs.  For example, $G$ might have a 
%hexagonal face, all of whose vertices are trivalent; 
%in that case, $Q(G)$ admits a mutation at the corresponding
%vertex, but there is no move of plabic graphs which corresponds 
%to this mutation.  


%\begin{remark}
%The open positroid varieties $\pi_k(\mathcal{R}_{v,w}) \subseteq Gr_{k, n}$ are in bijection 
%with a variety of combinatorial objects introduced by Postnikov in \cite{Postnikov}, including the 
%	decorated permutations on $n$ letters with $k$ \emph{antiexcedances}.  Here we say that 
%	$i\in [n]$ is an \emph{antiexcedance} of a decorated permutation $\pi$ if 
%	 $\pi^{-1}(i)>\pi(i)$ or $i$ is a white lollipop.
%
%As pointed out in \cite{shelling}, the decorated permutation of $\pi_k(\mathcal{R}_{v,w})$ is $\pi_{v, w}:=v^{-1}w$ with all white fixed points lying in $v^{-1}[k]$ 
%(see \cite[Section 2.4, Equation 2.27]{Karpman} for phrasing that is closer to ours). 
% The set of antiexcedances is exactly $v^{-1}[k]$.
%	Clearly one can recover the pair $(v,w)$ from $\pi_{v,w}$ since $v \in W^K_{\max}$.
%\end{remark}




%\subsection{A fact about permutations}
% 
%We will need the following lemma on reduced expressions for permutations in $^K W$ and $W^K$. 
%It is illustrated in \cref{fig:redexpression}.
%%\Comment{Reference for \cref{lem:redexpression}? \cite{Stem} at least mentions this...}
%
%\begin{lemma} \cite{Stem} \label{lem:redexpression}
%Let $x \in {^KW}$ and let $\lambda:=\partne{x([k])}$. 
%%Grassmannian permutations are \emph{fully commutative}, meaning that all reduced expressions for $x \in {^KW}$ can be obtained from one another using commutation moves $s_i s_j \to s_j s_i$ for $|i-j|\geq 2$.  
%Choose a ``reading order" for the boxes of $\lambda$ such that each box is read before the box immediately below it and the box immediately to its right (that is, choose a standard Young tableaux of shape $\lambda$). 
%Fill each box with a simple transposition; the box in row $r$ and column $c$ is filled with $s_{k-c+r}$.
%Then reading the fillings of the boxes according to the reading order gives a reduced expression for $x$ (written  from right to left).
%\end{lemma}
%
%\begin{figure}
%\setlength{\unitlength}{0.7mm}
%\begin{center}
% \begin{picture}(50,35)
%% Young Diagram
%% horizontal lines
%  \put(5,32){\line(1,0){36}}
%  \put(5,23){\line(1,0){36}}
%  \put(5,14){\line(1,0){36}}
%  \put(5,5){\line(1,0){18}}
%  \put(5,-4){\line(1,0){9}}
%% vertical lines
%  \put(5,-4){\line(0,1){36}}
%  \put(14,-4){\line(0,1){36}}
%  \put(23,5){\line(0,1){27}}
%  \put(32,14){\line(0,1){18}}
%  \put(41,14){\line(0,1){18}}
%% first row
%  \put(8,26){$1$}
%  \put(17,26){$5$}
%  \put(26,26){$8$}
%  \put(35,26){$10$}
%% second row
%  \put(8,17){$2$}
%  \put(17,17){$6$}
%  \put(26,17){$9$}
%  \put(35,17){$11$}
%% third row
%  \put(8,8){$3$}
%  \put(17,8){$7$}
% % fourth row
%  \put(8,-1){$4$}
% \end{picture}
%    \qquad
%	\begin{picture}(50,35)
%% Young Diagram
%% horizontal lines
%  \put(5,32){\line(1,0){36}}
%  \put(5,23){\line(1,0){36}}
%  \put(5,14){\line(1,0){36}}
%  \put(5,5){\line(1,0){18}}
%  \put(5,-4){\line(1,0){9}}
%% vertical lines
%  \put(5,-4){\line(0,1){36}}
%  \put(14,-4){\line(0,1){36}}
%  \put(23,5){\line(0,1){27}}
%  \put(32,14){\line(0,1){18}}
%  \put(41,14){\line(0,1){18}}
%% first row
%  \put(7,26){$s_4$}
%  \put(16,26){$s_5$}
%  \put(25,26){$s_6$}
%  \put(34,26){$s_7$}
%% second row
%  \put(7,17){$s_3$}
%  \put(16,17){$s_4$}
%  \put(25,17){$s_5$}
%  \put(34,17){$s_6$}
%% third row
%  \put(7,8){$s_2$}
%  \put(16,8){$s_3$}
%% fourth row
%		\put(7,-1){$s_1$}
%  \end{picture}
%\end{center}
%\caption{\label{fig:redexpression} Here $x=(2, 4, 7, 8, 1, 3, 5, 6)$ and $\partne{x([k])}=(4, 4, 2, 1)$. On the left, a reading order for the boxes of $\partne{x([k])}$; on the right, the filling of $\partne{x([k])}$ with simple transpositions. This reading order produces the reduced expression $\textbf{x}=s_6 s_7 s_5 s_6 s_3 s_4 s_5 s_1 s_2 s_3 s_4$. }
%\end{figure}
%
%
%%\begin{figure}
%%\centering
%%\includegraphics[height=0.15\textheight]{redexpression}
%%\end{figure}
%
%
%Note that one can also obtain reduced expressions for $y \in W^K$ by the process described in \cref{lem:redexpression}, using the partition $\partne{y^{-1}([k])}$. The only difference is the resulting reduced expression for $y$ is written down from left to right. 
%
%\begin{remark}\label{rem:columnar} For simplicity, we will always use the \emph{columnar} reading order, which reads the columns of $\lambda$ from top to bottom, moving left to right (see \cref{fig:redexpression}). We will call the resulting reduced expressions \emph{columnar expressions}.
%\end{remark}
%
%We will be particularly concerned with pairs 
%$(v,w)$ where 
%$v \in W^K_{\max}$ and $w$ has a \emph{length-additive factorization}
%$w = xv$, i.e. $\ell(w)=\ell(x)+\ell(v)$.  We will often use reduced expressions for such permutations $w$ that reflect their length-additive factorizations.
% 
% \begin{defn} \label{def:stdredexpression} Let $v \leq w$, with $v \in W^K_{\max}$ and $w=xv$ length-additive. Let $v=w_K v'$ be length-additive, where $v'$ is necessarily in $W^K_{\min}$. Then a \emph{standard reduced expression} for $w$ is a reduced expression $\textbf{w}=\textbf{x}\textbf{w}_K \textbf{v'}$, where $\textbf{x}$ and $\textbf{v'}$ are the columnar expressions for $x$ and $v'$, respectively, and $\textbf{w}_K$ is an arbitrary reduced expression for $w_K$.
% \end{defn}






\acknowledgements{We are grateful to Bernard Leclerc for numerous helpful discussions.
K.S. and M.S.B. acknowledge support from National Science Foundation Postdoctoral Fellowship MSPRF-1502881 and NSF Graduate Research Fellowship
No. DGE-1752814, respectively. 
L. W. was partially supported by 
the NSF grant DMS-1600447.
Any opinions, findings
and conclusions or recommendations expressed in this material are those of 
the authors and do not necessarily reflect the views of the National
Science Foundation. }

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