--- author: - Cameron Marcott title: Combinatorics of the Deodhar decomposition of the Grassmannian --- Introduction {#sec:intro} ============ The Deodhar decomposition of a flag manifold was introduced in @deodhar:geometric_aspects with the purpose of computing Kazhdan-Lusztig $R$-polynomials. Associated to each pair of permutations $u \leq v$ in Bruhat order is a Richardson cell in the flag manifold. Components in the Deodhar decomposition are indexed by certain subexpressions ${\mathbf{u}}$ for $u$ of an expression ${\mathbf{v}}$ for $v$ in the Coxeter generators. The Deodhar decomposition refines the Richardson decomposition, with the Richardson cell indexed by $u \leq v$ being the disjoint union of Deodhar components indexed by ${\mathbf{u}} \prec {\mathbf{v}}$. Deodhar components are homeomorphic to products of tori and affine spaces, and an explicit parameterization of Deodhar components is given in @marsh:parametrizations. A Deodhar component in the Grassmannian is the projection of Deodhar component from the flag manifold to the Grassmannian. A positroid in the Grassmannian is the projection of a Richardson cell from the flag manifold to the Grassmannian. So, the Deodhar decomposition refines the positroid decomposition. In fact, @marsh:parametrizations shows that the Deodhar decomposition agrees with the positroid decomposition when restricted to the positive part of the Grassmannian and refines it away from the positive Grassmannian. From any point in $A$ the Grassmannian, one may construct a soliton solution $u_A(t,x,y)$ to the KP differential equation. One may construct a contour plot of this soliton, and @kodama:deodhar_decomposition shows that when $t \ll 0$ this contour plot depends only on which Deodhar component $A$ lies in. In developing this theory, Kodama and Williams introduce Go-diagrams, certain fillings of a Ferrers shape with black stones, white stones, and pluses which index Deodhar components in the Grassmannian. When a Deodhar component intersects the positive Grassmannian, its Go-diagram is exactly the -diagram indexing the positroid cell it agrees with. In @lam:total_positivity, a set of "-moves" is given which may be used to transform any reduced diagram into a -diagram. In this paper, we address the problems: - Provide a set of local moves which may be used to transform any, not necessarily reduced, diagram into a Go-diagram. - Describe the boundary structure of Deodhar components in the Grassmannian. - Given an arbitrary filling of a Ferrers shape with black stones, white stones, and pluses, provide a test for whether this diagram is a Go-diagram. Section \[sec:corrective\_flips\] answers question (1), describing a set of <span>*corrective flips*</span> which may be used to transform any diagram into a Go-diagram. Unlike the -moves of @lam:total_positivity, it is possible to obtain more than one Go-diagram for a fixed starting diagram via corrective flips. Section \[sec:boundaries\] addresses question (2). In general, one does not expect questions of this form to have a reasonable answer. The Deodhar decomposition is known to not even be a stratification of the flag manifold, @dudas:not_a_stratification. However, Theorem \[thm:diagrammatic\_boundaries\] provides an intriguing class of boundaries, showing there is a containment of closures of Deodhar components $\overline{{\mathcal{D}}'} \subset \overline{{\mathcal{D}}}$ when the associated Go-diagrams $D'$ and $D$ are related by degenerating certain stones to pluses, then performing corrective flips. We conjecture that this theorem in fact provides a complete characterization of when there is a containment of closures of Deodhar components within a Schubert cell. Other aspects of the boundary structure of Deodhar components are explored in @agarwala:nonorientable. Section \[sec:classification\] addresses question (3). Ideally, one would like a description of Go-diagrams in terms of forbidden subdiagrams, analogous to the description of -diagrams. We show that a reasonable description of this form cannot exist, by providing an injection from the set of valid Go-diagrams to the set of "minimal forbidden subdiagrams" in Theorem \[thm:sad\_injection\]. So, the task of providing a list of forbidden subdiagrams for the class of Go-diagrams is at least as hard as providing a list of all valid Go-diagrams. In lieu of such a description, Theorem \[thm:characterization\] provides an inductive characterization of Go-diagrams. Background and notation {#sec:background} ======================= The symmetric group ------------------- Let $s_i$ denote the adjacent transposition $(i,i+1)$ in the symmetric group $\mathfrak{S}_n$. Italicized lowercase letters, $v$, will denote permutations and bold faced letters, ${\mathbf{v}}$, will denote specific expressions of permutations in the $s_i$'s. A <span>*subexpression*</span> of $\mathbf{v}$ is a permutation obtained by replacing some of the factors in ${\mathbf{v}}$ by $\varepsilon$, the identity permutation in $\mathfrak{S}_n$. The terms "expression" and "word" will be used interchangeably. Given an expression ${\mathbf{v}} = v_1 v_2 \cdots v_m$, let $v_{(i)} = v_1 v_2 \cdots v_{i}$ denote the product of the initial $i$ factors of ${\mathbf{v}}$. So, $v_{(0)} = \varepsilon$ and $v_{(m)} = v$. The <span>*length*</span> of a permutation, $\ell(v)$, is the minimum number of letters in an expression of $v$. A word is <span>*reduced*</span> if $\ell(v_{(i+1)}) = \ell(v_{(i)}) + 1$ for every $i$. All reduced words for a permutation contain the same number of factors. The <span>*Bruhat order*</span> on permutations is the order given by setting $u \leq v$ if and only if some reduced word for $u$ is a subword of some reduced word for $v$. A subexpression $\textbf{u}$ of $\textbf{v}$ is <span>*distinguished*</span> if whenever $\ell(u_{(i)}v_{i+1}) < \ell(u_{(i)})$ , one also has $u_{i+1} = v_{i+1}$, (i.e. $u_{i+1} \neq \varepsilon$). Write $\textbf{u} \prec \textbf{v}$ if $\textbf{u}$ is a distinguished subexpression of $\textbf{v}$. The subexpression ${\textbf{u}}$ of ${\textbf{v}}$ is <span>*positive*</span> if $\ell(u_{(i+1)}) \geq \ell(u_{(i)})$ for all $i$. Let ${\mathbf{v}} = s_1 s_2 s_1 s_3 s_2 s_1$. Then, $$\varepsilon \varepsilon \varepsilon \varepsilon \varepsilon \varepsilon, \mbox{ } s_1 \varepsilon s_1 \varepsilon \varepsilon \varepsilon, \mbox{ and } s_1 \varepsilon \varepsilon \varepsilon \varepsilon s_1$$ are three subexpressions for the identity permutation in ${\mathbf{v}}$. The first is positive and distinguished, the second is distinguished but not positive, and the third is neither positive nor distinguished. \[Lemma 3.5 in @marsh:parametrizations\] \[lem:unique\_positive\_expression\] Let $u \leq v$ be permutations and $\textbf{v}$ be a reduced expression for $v$. Then, there is a unique positive distinguished subexpression for $u$ in $\textbf{v}$. The Young subgroup $\mathfrak{S}_k \times \mathfrak{S}_{n-k} \subset \mathfrak{S}_n$ acts on a permutation $(v(1), v(2), \dots, v(n))$ by letting $\mathfrak{S}_k$ act on $(v(1), v(2), \dots, v(k))$ and $\mathfrak{S}_{n-k}$ act on $(v(k+1), v(k+2), \dots, v(n))$. Any coset in the quotient $\mathfrak{S}_n / (\mathfrak{S}_k \times \mathfrak{S}_{n-k})$ has a unique representative of the form $(i_1, i_2, \dots, i_k, j_1, j_2, \dots, j_{n-k})$ where $i_1 < i_2 < \cdots < i_k$ and $j_1 < j_2 < \cdots < j_{n-k}$. These representatives are called <span>*Grassmannian permutations*</span>. Grassmannian permutations are in bijection with subsets in $\binom{[n]}{k}$ sending $(i_1, i_2, \dots, i_k, j_1, j_2, \dots, j_{n-k})$ to $\{i_1, i_2, \dots, i_k\}$. Often, we will suppress curly braces and commas when writing sets to avoid unwieldy notation, writing $i_1 i_2 \dots i_k$ to mean $\{i_1, i_2, \dots, i_k\}$. The Bruhat order on $\mathfrak{S}_n$ induces an order on the quotient $\mathfrak{S}_n / (\mathfrak{S}_k \times \mathfrak{S}_{n-k})$ and thus a partial order on $\binom{[n]}{k}$. Concretely, if $I = \{i_1, i_2, \dots, i_k\}$ and $J = \{j_1, j_2, \dots, j_k\}$ with $i_1 < i_2 < \cdots < i_k$ and $j_1 < j_2 < \cdots < j_k$, then $I \leq J$ if and only if $i_m \leq j_m$ for all $m$. A <span>*Ferrers shape*</span> is a collection of boxes obtained by taking a lattice path from the Northeast to Southwest corner of a $(n-k) \times k$ rectangle, then taking all boxes Northwest of this lattice path. The steps of the lattice path are labelled $1$ to $n$ starting at the Northeast corner. A box $b$ has coordinates $(i,j)$ if the vertical step of the boundary in the same row as $b$ is labelled $i$ and the horizontal step of the boundary in the same column as $b$ is labelled $j$. Ferrers shapes contained in an $(n-k) \times k$ box are in bijection with subsets $\binom{[n]}{k}$ sending the Ferrers shape $\lambda$ to the set $I_\lambda$ of labels of the vertical steps in its boundary path. Composing bijections, to the Ferrers shape $\lambda$ we also associate a Grassmannian permutation $v_{\lambda}$. Pictorially, the partial order on $\binom{[n]}{k}$ translates to containment of Ferrers shapes. Given a box $b$ in a Ferrers diagram $D$, $b^{in}$ is the set of boxes weakly to the right and weakly below $b$. Additionally, set $b^{out} = D \setminus b^{in}$. We introduce a partial order on the boxes in a diagram, saying $c \preccurlyeq b$ if and only if $c \in b^{in}$. A <span>*pipe dream*</span> is a filling of a Ferrers shape with crossing tiles and elbow pieces, $$\begin{tikzpicture} \begin{scope}[scale=.75] \draw (0,0) -- (1,0) -- (1,1) -- (0,1) -- (0,0); \draw[thick] (0.5,0.2) -- (0.5,0.8); \draw[thick] (0.2,0.5) -- (0.8,0.5); \draw (2,.5) node {and}; \draw (3,0) -- (4,0) -- (4,1) -- (3,1) -- (3,0); \draw[thick] (3.5,.1) arc (0:90:.4cm); \draw[thick] (3.5,.9) arc (180:270:.4cm); \draw (4.2,.1) node {$.$}; \end{scope} \end{tikzpicture}$$ Think of this filling as a collection of pipes flowing from the Southeast boundary to the Northwest boundary. From a pipe dream, we read off a permutation by labelling the edges along the North and West boundaries of the Ferrers shape such that for each pipe in the diagram, both ends of the pipe have the same label, then writing down the labels that appear along the Northwest boundary in order starting from the Northeast corner. We say that two squares $b$ and $c$ in a pipe dream are a <span>*crossing/uncrossing pair*</span> if two pipes cross in $b$, flow to the Northwest, then next uncross in $c$. A pipe dream is <span>*reduced*</span> if it has no crossing/uncrossing pairs. Note that a crossing tile is a crossing if the label of the pipe entering from the bottom is larger than the label of the pipe entering from the right, and is an uncrossing otherwise. Pipe dreams were originally defined by Bergeron and Billey in @bergeron:rc-graphs, where they were called RC-graphs for "reduced word, compatible sequence." They were later renamed pipe dreams by Knutson; we choose this terminology since the pipe dreams we consider will not in general be reduced. \[ex:pipe\_dream\] The pipe dream $$\begin{tikzpicture} \begin{scope}[scale=.75] \draw[step=1] (0,0) grid (3,3); \draw[step=1] (3,2) grid (4,3); \draw[thick] (0.5,0.2) -- (0.5,0.8); \draw[thick] (0.2,0.5) -- (0.8,0.5); \draw[thick] (1.5,.1) arc (0:90:.4cm); \draw[thick] (1.5,.9) arc (180:270:.4cm); \draw[thick] (2.5,0.2) -- (2.5,0.8); \draw[thick] (2.2,0.5) -- (2.8,0.5); \draw[thick] (.5,1.1) arc (0:90:.4cm); \draw[thick] (.5,1.9) arc (180:270:.4cm); \draw[thick] (1.5,1.1) arc (0:90:.4cm); \draw[thick] (1.5,1.9) arc (180:270:.4cm); \draw[thick] (2.5,1.1) arc (0:90:.4cm); \draw[thick] (2.5,1.9) arc (180:270:.4cm); \draw[thick] (0.5,2.2) -- (0.5,2.8); \draw[thick] (0.2,2.5) -- (0.8,2.5); \draw[thick] (1.5,2.1) arc (0:90:.4cm); \draw[thick] (1.5,2.9) arc (180:270:.4cm); \draw[thick] (2.5,2.1) arc (0:90:.4cm); \draw[thick] (2.5,2.9) arc (180:270:.4cm); \draw[thick] (3.5,2.2) -- (3.5,2.8); \draw[thick] (3.2,2.5) -- (3.8,2.5); \draw (4.25,2.5) node {$1$}; \draw (3.6,1.75) node {$2$}; \draw (3.25,1.35) node {$3$}; \draw (3.25,.5) node {$4$}; \draw (2.5,-.25) node {$5$}; \draw (1.5,-.25) node {$6$}; \draw (.5,-.25) node {$7$}; \draw (3.5,3.25) node {$2$}; \draw (2.5,3.25) node {$1$}; \draw (1.5,3.25) node {$3$}; \draw (.5,3.25) node {$4$}; \draw (-.25,2.5) node {$5$}; \draw (-.25,1.5) node {$7$}; \draw (-.25,.5) node {$6$}; \end{scope} \end{tikzpicture}$$ gives the permutation $(2,1,3,4,5,7,6)$. The squares $(4,5)$ and $(1,7)$ form a crossing/uncrossing pair. A <span>*$\circ/+$-diagram*</span> is a filling of a Ferrers shape with white stones and pluses, $$\begin{tikzpicture} \begin{scope}[scale=.75] \draw (0,0) -- (1,0) -- (1,1) -- (0,1) -- (0,0); \draw[fill = white] (0.5,0.5) circle (.25); \draw (2,.5) node {and}; \draw (3,0) -- (4,0) -- (4,1) -- (3,1) -- (3,0); \draw[thick] (3.5,0.2) -- (3.5,0.8); \draw[thick] (3.2,0.5) -- (3.8,0.5); \draw (4.2,.1) node {$.$}; \end{scope} \end{tikzpicture}$$ $\circ/+$-diagrams are in bijection with pipe dreams by replacing the circles with crossing tiles and the pluses with elbow pieces. This bijection is unfortunate, but is the standard convention in the literature. A $\bullet/\circ/+$-diagram is a filling of filling of a Ferrers shape with black stones, white stones, and pluses, $$\begin{tikzpicture} \begin{scope}[scale=.75] \begin{scope}[xshift=-2cm] \draw (0,0) -- (1,0) -- (1,1) -- (0,1) -- (0,0); \draw[fill = black] (0.5,0.5) circle (.25); \draw (1.2,.1) node {$,$}; \end{scope} \draw (0,0) -- (1,0) -- (1,1) -- (0,1) -- (0,0); \draw[fill = white] (0.5,0.5) circle (.25); \draw (1.2,.1) node {$,$}; \draw (2,.5) node {and}; \draw (3,0) -- (4,0) -- (4,1) -- (3,1) -- (3,0); \draw[thick] (3.5,0.2) -- (3.5,0.8); \draw[thick] (3.2,0.5) -- (3.8,0.5); \draw (4.2,.1) node {$.$};\end{scope} \end{tikzpicture}$$ $\bullet/\circ/+$-diagrams are mapped to pipe dreams by sending both the black and white stones to crossing tiles, and sending the pluses to elbow tiles. So, $\bullet/\circ/+$-diagrams may be viewed as $\circ / +$-diagrams where the stones have been decorated to have two colors. Often, but not always, we will require that stones be colored black if and only if they are mapped to uncrossing tiles in the pipe dream. We state whether or not we make this assumption at the start of each section. Label the top left box of a Ferrers shape contained in a $k \times (n-k)$ box with the simple transposition $s_{n-k}$. If the box to the left of $b$ is labelled with the transpositions $s_i$, label $b$ with $s_{i-1}$ and if the box above $b$ is labelled with $s_i$ label $b$ with $s_{i+1}$. Observe that for any box $b$, the permutation corresponding to the $\circ/+$ diagram where $b$ is filled with a white stone and all other boxes are filled with pluses is exactly the transposition labelling $b$. We use $s_b$ to denote the simple transposition labelling the box $b$. A <span>*reading order*</span> on a Ferrers shape of shape $\lambda$ containing $m$ boxes is a filling of the boxes with the integers from $1$ to $m$ which is increasing upward and to the left. Reading the transpositions decorating the boxes of the Ferrers diagram in any reading order yields a reduced expression $\textbf{v}$ for $v_\lambda$. Reading only the transpositions decorating boxes containing stones in either a $\circ/+$ or a $\bullet/\circ/+$-diagram diagram in the same reading order gives a subexpression ${\mathbf{u}}$ of ${\mathbf{v}}$ for the permutation given by the associated pipe dream. \[Proposition 4.5 in @lam:total_positivity\] \[thm:reading\_order\_doesnt\_matter\] Let $D$ be a $\circ/+$ or $\bullet/\circ/+$-diagram giving the subword, word pair $\textbf{u}, \textbf{v}$ in some reading order. - The permutations $v$, coming from the Ferrers shape, and $u$, coming from the pipe dream depend only on $D$, not the choice of reading order. - Whether $\textbf{u}$ is a distinguished subexpression of $\textbf{v}$ depends only on $D$, not the choice of reading order. - Whether $\textbf{u}$ is a positive subexpression of $\textbf{v}$ depends only $D$, not on the choice of reading order. This theorem is proved by noting that if the expressions $\textbf{u}$ and $\textbf{u}'$ are obtained by altering the reading order on the same diagram, then they are related by commutations of the Coxeter generators, and thus $u = u'$. Let $b$ be a box in the $\circ/+$ or $\bullet/\circ/+$-diagram $D$. Define $u_{b^{in}}^{D}$ to be the permutation obtained by multiplying the transpositions labelling all boxes containing stones in $b^{in}$ in $D$ some valid reading order. As a corollary of Theorem \[thm:reading\_order\_doesnt\_matter\], $u_{b^{in}}^{D}$ does not depend on the choice of reading order. If the diagram is clear from context, we will simply write $u_{b^{in}}$ instead of $u_{b^{in}}^D$. Let $$u_b^D = \begin{cases} s_b & \mbox{if $b$ contains a stone in $D$,} \\ \varepsilon & \mbox{if $b$ contains a plus in $D$.} \end{cases}$$ We will simply write $u_b$ instead of $u_b^D$ if the diagram is clear from context. \[def:go-diagram\] Let $D$ be a $\bullet/\circ/+$-diagram. Then, $D$ is a <span>*Go-diagram*</span> if and only if a box $b$ contains a black stone if and only if $\ell(u_{b^{in}} u_b s_b) < \ell(u_{b^{in}} u_b)$. Let ${\mathbf{u}}, {\mathbf{v}}$ be the subword, word pair associated to the diagram $D$ in some reading order. Theorem \[thm:reading\_order\_doesnt\_matter\] implies that if $D$ is a Go-diagram, then ${\mathbf{u}}$ is a distinguished subexpression of ${\mathbf{v}}$, and that this is independent of the choice of reading order. If a box $b$ has the property that $\ell(u_{b^{in}} u_b s_b ) < \ell(u_{b^{in}} u_b)$, but $b$ is not filled with a black stone, we say that $b$ <span>*violates the distinguished property*</span>. \[def:le-diagram\] Let $D$ be a $\bullet/\circ/+$-diagram. Then, $D$ is a <span>*-diagram*</span> is any of the following equivalent criterion hold: - $D$ is an Go-diagram and contains no black stones. - Let ${\mathbf{u}}, {\mathbf{v}}$ be the subword, word pair associated to $D$. Then, ${\mathbf{u}}$ is a positive distinguished subexpression of ${\mathbf{v}}$ - $D$ contains no black stones, and there is no box $b$ in $D$ containing a white stone such that there is a plus to the left of $b$ in its column and above $b$ in its row. The equivalence between points (i) and (ii) is immediate. The equivalence between points (ii) and (iii) is Theorem 5.1 in @lam:total_positivity. The condition in point (iii) is called the <span>*-property*</span>. The symbol "" is pronounced "le," the backward spelling of the letter "el." Consider the diagrams $$\begin{tikzpicture} \begin{scope}[scale=.75] \draw[step=1] (0,0) grid (3,2); \draw[thick] (.5,.2) -- (.5,.8); \draw[thick] (.2,.5) -- (.8,.5); \draw[thick] (1.5,.2) -- (1.5,.8); \draw[thick] (1.2,.5) -- (1.8,.5); \draw[fill = white] (2.5,0.5) circle (.25); \draw[fill = white] (.5,1.5) circle (.25); \draw[thick] (1.5,1.2) -- (1.5,1.8); \draw[thick] (1.2,1.5) -- (1.8,1.5); \draw[thick] (2.5,1.2) -- (2.5,1.8); \draw[thick] (2.2,1.5) -- (2.8,1.5); \draw (4,1) node {and}; \begin{scope}[shift={(5,0)}] \draw[step=1] (0,0) grid (3,2); \draw[thick] (.5,.2) -- (.5,.8); \draw[thick] (.2,.5) -- (.8,.5); \draw[thick] (1.5,.2) -- (1.5,.8); \draw[thick] (1.2,.5) -- (1.8,.5); \draw[thick] (2.5,.2) -- (2.5,.8); \draw[thick] (2.2,.5) -- (2.8,.5); \draw[fill = white] (.5,1.5) circle (.25); \draw[fill = white] (1.5,1.5) circle (.25); \draw[thick] (2.5,1.2) -- (2.5,1.8); \draw[thick] (2.2,1.5) -- (2.8,1.5); \draw (3.2,0) node {$.$}; \end{scope} \end{scope} \end{tikzpicture}$$ The diagram on the left corresponds to the subexpression $s_2 \varepsilon \varepsilon \varepsilon \varepsilon s_3$ of $s_2 s_3 s_4 s_1 s_2 s_3$ and the diagram on the right corresponds to the subexpression $\varepsilon \varepsilon \varepsilon \varepsilon s_2 s_3$. The diagram on the left is not a -diagram, which can be seen by noting that its subexpression is not distinguished or by noting that the box $(2,3)$ contains a white stone, but has a plus both above it and to its left. The locations of only the white stones or of only the pluses are enough to uniquely determine a Go-diagram. Given a Ferrers shape filled with white stones, we complete the filling in increasing order in the partial order on boxes. If $c$ is some box in the diagram and all boxes in $c^{in} \setminus c$ have been filled, we may compute the permutation $u_{c^{in}}u_c$, which does not depend on the filling of $c$. Then, fill $c$ with a plus if $\ell(u_{c^{in}} u_cs_c) > \ell(u_{c^{in}} u_c)$ and fill $c$ with a black stone otherwise. Given a Ferrers shape filled with pluses, construct a pipe dream by placing elbow tiles in the squares containing pluses and crossing tiles in all other squares. Then, for each square not containing a plus in the Ferrers shape, fill it with a white stone if the square is a crossing in the pipe dream and a black stone if it is an uncrossing. The following propositions follows directly from the definitions. \[prop:length\_from\_filling\] Let $D$ be the Deodhar component associated to the distinguished subexpression ${\mathbf{u}} \prec {\mathbf{v}}$. Then, $$\begin{split} \ell(u) & = \#(\mbox{of $\circ$'s in $D$}) - \#(\mbox{of $\bullet$'s in $D$}) \\ & = \ell(v) - \#(\mbox{of $+$'s in $D$}) - 2 \cdot \#(\mbox{of $\bullet$'s in $D$}). \end{split}$$ The Deodhar decomposition of the Grassmannian --------------------------------------------- Let $Gr(k,n)$ be the Grassmannian of $k$ dimensional subspaces of ${\mathbb{R}}^n$. For $I \in \binom{[n]}{k}$, let $\Delta_I$ be the $I^{th}$ Plücker coordinate on $Gr(k,n)$. That is, choosing a basis on ${\mathbb{R}}^n$, if $V \in Gr(k,n)$ is presented as the row span of a $k \times n$ matrix, then $\Delta_I(V)$ is the maximal minor of this matrix using columns labelled by $I$. The Plücker coordinates give an embedding of $Gr(k,n)$ into the projective space $\mathbb{P}^{\binom{n}{k} - 1}$. The Plücker embedding of the Grassmannian is the subvariety of $\mathbb{P}^{\binom{n}{k} - 1}$ defined by the Plücker relations $$\label{eqn:plucker_relation} \Delta_I \Delta_J = \sum_{j \in J} \pm \Delta_{I \setminus i \cup j} \Delta_{J \setminus j \cup i},$$ for each pair of sets $I, J \in \binom{[n]}{k}$ and each element $i \in I$. The signs in the sum on the right hand side are obtained by ordering the indices of $I$ and $J$ in increasing order, placing $j$ in $i$'s old position in $I$ and $i$ in $j$'s old position in $J$, then taking $-1$ times the product of the signs of the two permutations need to rearrange to new sets so that their elements are in increasing order. For example, $$\Delta_{123} \Delta_{245} = \Delta_{234} \Delta_{125} - \Delta_{235} \Delta_{124}$$ is a Plücker relation. The positive part of the Grassmannian, $Gr_{\geq 0}(k,n)$, is the subset of $Gr(k,n)$ where all Plücker coordinates have the same sign. Deodhar components in the Grassmannian are semialgebraic subsets obtained by setting some Plücker coordinates equal to zero and demanding other Plücker coordinates do not vanish. This description of Deodhar components appears as Theorem 7.8 in @talaska:network_parameterizations. Deodhar components were originally defined in @deodhar:geometric_aspects. \[def:set\_I\_b\] Let $b$ be a box in the Go-diagram $D$ associated to the distinguished subword pair ${\mathbf{u}} \prec {\mathbf{v}}$. Define $$\label{eqn:I_b} I_b = u_{b^{in}} u_b (v_{b^{in}})^{-1} v \{n, n-1, \dots, n-k+1\}.$$ Diagrammatically, $I_b$ may be computed by: - Changing the filling of all boxes in $b^{out}$ to white stones, - Changing the filling of $b$ to a plus, - Computing the pipe dream associated to this diagram, - Setting $I_b$ to be the labels of the pipes appearing along the left boundary of this pipe dream. A description of the set $I_b$ is given in @agarwala:nonorientable using a network associated to the Go-diagram defined in @talaska:network_parameterizations. Proposition \[prop:I\_b\_again\] tells how to recover the sets $I_b$ given the Deodhar component. \[ex:sets\_from\_boxes\] A Go-diagram $D$ is pictured on the left. In the Ferrers shape on the right, each box $b$ is labelled with the set $I_b$ from $D$. $$\begin{tikzpicture} \begin{scope}[scale=.75] \draw[step = 1] (0,0) grid (3,3); \draw[thick] (0.5,0.2) -- (0.5,0.8); \draw[thick] (0.2,0.5) -- (0.8,.5); \draw[fill = white] (1.5,0.5) circle (.25); \draw[thick] (2.5,0.2) -- (2.5,0.8); \draw[thick] (2.2,0.5) -- (2.8,0.5); \draw[fill = black] (0.5,1.5) circle (.25); \draw[thick] (1.5,1.2) -- (1.5,1.8); \draw[thick] (1.2,1.5) -- (1.8,1.5); \draw[fill = white] (2.5,1.5) circle (.25); \draw[thick] (0.5,2.2) -- (0.5,2.8); \draw[thick] (0.2,2.5) -- (0.8,2.5); \draw[fill = black] (1.5,2.5) circle (.25); \draw[thick] (2.5,2.2) -- (2.5,2.8); \draw[thick] (2.2,2.5) -- (2.8,2.5); \end{scope} \begin{scope}[xshift=3.5cm,yshift=-.375cm] \draw[step=1] (0,0) grid (3,3); \draw (2.5,.5) node {124}; \draw (1.5,.5) node {125}; \draw (.5,.5) node {126}; \draw (2.5,1.5) node {134}; \draw (1.5,1.5) node {145}; \draw (.5,1.5) node {146}; \draw (2.5,2.5) node {234}; \draw (1.5,2.5) node {245}; \draw (.5,2.5) node {456}; \end{scope} \end{tikzpicture}$$ \[Theorem 7.8 in @talaska:network_parameterizations\] \[thm:plucker\_coordinates\] Let $D$ be a Go-diagram of shape $\lambda$. Then, the <span>*Deodhar component*</span> ${\mathcal{D}}$ associated to $D$ is the subset in $Gr(k,n)$ defined by: - $\Delta_{I_b} = 0$ for all boxes $b \in D$ containing white stones. - $\Delta_{I_b} \neq 0$ for all boxes $b \in D$ containing pluses. - $\Delta_{I_\lambda} \neq 0$. - $\Delta_{S} = 0$ for all $S \ngeq I_\lambda$. In general, we will use upper case letters to refer to Go-diagrams and calligraphic letters to refer to Deodhar components. When we want to make explicit reference to the distinguished subword pair associated to a Go-diagram, we will use the notation ${\mathcal{D}}_{{\mathbf{u}},{\mathbf{v}}}$. The Deodhar component associated to the Go-diagram in Example \[ex:sets\_from\_boxes\] is the subset of $Gr(3,6)$ where $$\begin{split} & \Delta_{134}, \Delta_{125} = 0, \mbox{and} \\ & \Delta_{123}, \Delta_{124}, \Delta_{126}, \Delta_{145}, \Delta_{234}, \Delta_{456} \neq 0. \end{split}$$ \[Theorem 1.1 in @deodhar:geometric_aspects\] \[thm:parameterization\_of\_deodhar\] Let ${\mathcal{D}}$ be the Deodhar component labelled by the Go-diagram $D$. Then, ${\mathcal{D}}$ is homeomorphic to $${\mathbb{R}}^{\#\left(\bullet\mathit{'s} \ \mathit{in} \ D \right)} \times \left( {\mathbb{R}}\setminus \{0\}\right)^{\#\left(+\mathit{'s} \ \mathit{in} \ D \right)}.$$ The following interpretation of the sets $I_b$ is given in Theorem 1.17 in @agarwala:nonorientable. \[prop:I\_b\_again\] Suppose the vertical steps of the boundary of the Ferrers shape $\lambda$ are $i_1 < i_2 < \cdots < i_k$ and the horizontal steps are $j_1 < j_2 < \cdots < j_{n-k}$. Let $b = (i_\ell,j_m)$ be a box in the Go-diagram $D$ of shape $\lambda$ indexing the Deodhar component ${\mathcal{D}}$. Let $I'_b = I_b \setminus j_m \cup i_\ell$. Then, $I'_b$ is the maximal set such that $i_1, i_2, \dots i_\ell \in I'_b$, $j_n, j_{n-1}, \dots, j_{m} \notin I'_b$, and $\Delta_{I'_b}$ is not uniformly vanishing on ${\mathcal{D}}$. The following proposition is an immediate consequence of Corollary 3.16 in @agarwala:nonorientable, together with the fact that the Deodhar decomposition refines the Richardson decomposition, Theorem \[thm:deodhar\_decomposes\_richardson\] below. \[prop:large\_sets\_vanish\] Suppose the vertical steps of the boundary of the Ferrers shape $\lambda$ are $i_1 < i_2 < \cdots < i_k$ and the horizontal steps are $j_1 < j_2 < \cdots < j_{n-k}$. Let $b = (i_\ell,j_m)$ be a box in the Go-diagram $D$ of shape $\lambda$ indexing the Deodhar component ${\mathcal{D}}$. Let $$\label{eqn:J_b} J_b = u_{b^{in}} (v_{b^{in}})^{-1} v \{n, n-1, \dots, n-k+1\}.$$ If $S \in \binom{[n]}{k}$ is such that $i_1, i_2, \dots, i_{\ell -1} \in S$, $j_n, j_{n-1}, \dots, j_{m+1} \notin S$, and $S > J_b$, then $\Delta_S$ vanishes uniformly on ${\mathcal{D}}$. Suppose that boxes $b$ and $c$ in a Go-diagram $D$ share an edge. Then, $I_b$ and $I_c$ differ by a single element. Let $i_1 < i_2 < \cdots < i_k$ be the labels of the vertical steps of the boundary of $D$ and $j_1< j_2 < \dots < j_{n-k}$ be the labels of the horizontal steps of the boundary of $D$ and suppose $b = (i_\ell,j_m)$. Let $p$ be the label of the pipe entering $b$ from the bottom and $q$ be the label of the pipe entering $b$ from the left in the pipe dream associated to $D$. If $c = (i_{\ell}, j_{m+1})$, then $I_c = I_b \setminus p \cup j_{m+1}$. If $c = (i_{\ell - 1}, j_m)$, then $I_c = I_b \setminus i_{\ell - 1} \cup q$. Other decompositions of the Grassmannian ---------------------------------------- This section briefly remarks about how the Deodhar decomposition is related to other common decompositions of the Grassmannian. Let $v \in \mathfrak{S}_n$ be the Grassmannian permutation associated to Ferrers shape $\lambda$. Associated to pairs of permutations $u, v$ with various constraints imposed on $u$, there are several decompositions of the Grassmannian $Gr(k,n)$. The stricter the constraint imposed on $u$, the coarser the decomposition of the Grassmannian. Below are the common decompositions of $G(k,n)$ and the associated constraints on $u$ arranged from coarsest to finest. $$\begin{array}{|c|c|c|} \hline \mbox{Decomposition} & \mbox{Notation} & \mbox{Constraints on $u$} \\\hline\hline \mbox{Schubert} & {\mathcal{S}}_{v} & u = \varepsilon \\\hline \mbox{Richardson} & {\mathcal{R}}_{u,v} & u \mbox{ is Grassmannian}, u \leq v \\\hline \mbox{Positroid} & {\mathcal{P}}_{u,v} & u \leq v \\\hline \mbox{Deodhar} & {\mathcal{D}}_{{\mathbf{u}},{\mathbf{v}}} & {\mathbf{u}} \prec {\mathbf{v}} \\\hline \end{array}$$ The Deodhar decomposition differs from the other decompositions in this list in that it doesn't just care that $u \leq v$, but how $\mathbf{u}$ is presented as a subword of $\mathbf{v}$. All of the components in these decompositions have the feature that they can be described as subsets of the Grassmannian by setting certain Plücker coordinates to zero, demanding certain other Plücker coordinates be non-zero, and leaving the remaining Plücker coordinates unspecified. The coarser the decomposition, the more Plücker coordinates are left unspecified. From a combinatorial standpoint, all of the decompositions can be described as introducing decorations to the Ferrers shape $\lambda$. - The Schubert stratification remembers only $\lambda$. This should be viewed coming from the fact that the $\circ/+$-diagram corresponding to the positive distinguished subexpression of identity permutation in $\mathbf{v}$ is $\lambda$ with every square with a plus. Let $I_{\lambda} \in \binom{[n]}{k}$ be the set associated to $v$. The Schubert cell ${\mathcal{S}}_v$ is defined by $\Delta_{I_\lambda} \neq 0$ and $\Delta_{S} = 0$ for all $S \ngeq I_\lambda$. - The Richardson stratification introduces another Ferrers shape $\mu$ contained inside $\lambda$; the pair is often called a skew shape. This should be viewed coming from the fact that the $\circ/+$-diagram corresponding to the positive distinguished subexpression $u$ in $\mathbf{v}$ can be drawn by first drawing the shape $\mu$ associated $u$ inside $\lambda$, then filling all squares in the skew diagram $\lambda/\mu$ with pluses and filling all other squares with white stones. The Richardson cell ${\mathcal{R}}_{u,v}$ is defined by $\Delta_{I_\mu}, \Delta_{I_\lambda} \neq 0$ and $\Delta_{S} = 0$ for all $S \nleq I_\mu$ and all $S \ngeq I_\lambda$. - The positroid stratification[^1] introduces the filling of $\lambda$ with pluses and white stones corresponding to the unique positive distinguished subexpression for $u$ in $\mathbf{v}$. That is, positroid cells are indexed by -diagrams. We will not need an explicit description of the positroid cell ${\mathcal{P}}_{u,v}$. These cells have been studied extensively and a description may be found in @postnikov:total_positivity. - The Deodhar decomposition is associated to the Go-diagram built from the pair $\mathbf{u} \prec \mathbf{v}$, as we saw in the previous section. As a word of caution, we remark that while -diagrams are in general Go-diagrams, the positroid cell and Deodhar component associated to the same diagram are in general different. For example, consider the following -diagram. $$\begin{tikzpicture} \begin{scope}[scale = .75] \draw[step=1] (0,0) grid (2,2); \draw (2,1) -- (3,1) -- (3,2) -- (2,2); \draw[thick] (.5,.2) -- (.5,.8); \draw[thick] (.2,.5) -- (.8,.5); \draw[thick] (1.5,.2) -- (1.5,.8); \draw[thick] (1.2,.5) -- (1.8,.5); \draw[thick] (.5,1.2) -- (.5,1.8); \draw[thick] (.2,1.5) -- (.8,1.5); \draw[thick] (1.5,1.2) -- (1.5,1.8); \draw[thick] (1.2,1.5) -- (1.8,1.5); \draw[thick] (2.5,1.2) -- (2.5,1.8); \draw[thick] (2.2,1.5) -- (2.8,1.5); \end{scope} \end{tikzpicture}$$ The positroid starta associated to this diagram is determined by $$\Delta_{13}, \Delta_{23}, \Delta_{34}, \Delta_{45}, \Delta_{51} \neq 0; \quad \Delta_{12} = 0,$$ while the Deodhar component additionally requires that $\Delta_{14} \neq 0$. This -diagram indexes the pair of permutations $\varepsilon, (2,3,4,1,3)$. So, it may additionally be seen as determining either a Schubert cell or a Richardson cell. The Schubert cell associated to this pair of permutations is determined by $$\Delta_{13} \neq 0; \quad \Delta_{12} = 0,$$ and the Richardson cell is determined by $$\Delta_{13}, \Delta_{45} \neq 0; \quad \Delta_{12} = 0.$$ In general, if a diagram could serve as an index for two decompositions, the set of vanishing Plücker coordinates will be the same in both decompositions. The set of nonvanishing Plücker coordinates in the coarser decomposition will be a subset of the set of nonvanishing Plücker coordinates in the finer decomposition. Deodhar components were originally introduced to refine the Richardson stratification. \[Corollary 1.2 in @deodhar:geometric_aspects\] \[thm:deodhar\_decomposes\_richardson\] Let ${\mathcal{R}}_{u,v}$ be a Richardson cell. Then, $${\mathcal{R}}_{u,v} = \bigsqcup_{u' \sim u} \bigsqcup_{{\mathbf{u'}} \prec {\mathbf{v}}} {\mathcal{D}}_{{\mathbf{u'}},{\mathbf{v}}},$$ where the first union is across all $u'$ in the same equivalence class as $u$ in $\mathfrak{S}_n / (\mathfrak{S}_{k} \times \mathfrak{S}_{n - k})$ and the second union is across all distinguished subexpressions for $u'$ in ${\mathbf{v}}$. Since the Grassmannian is the disjoint union of its Richardson cells, the Grassmannian is then the disjoint union of its Deodhar components. Though Deodhar components predate Lusztig's notion of positivity in flag varieties, @lusztig:total_positivity, and Postnikov's concrete description of positroid cells in $Gr_{\geq 0}(k,n)$, @postnikov:total_positivity, the Deodhard decomposition does refine the positroid stratification and in fact agrees with it when restricted to the positive part of the Grassmannian. \[Lemma 11.6 in @marsh:parametrizations\] \[thm:positive\_deodhar\_components\] Let ${\mathcal{D}}$ be the Deodhar component in $Gr(k,n)$ labelled by the Go-diagram $D$. Then, ${\mathcal{D}}\cap Gr_{\geq 0}(k,n)$ is nonempty if and only if $D$ is a -diagram. In this case, let ${\mathcal{P}}$ be the positroid cell labelled by $D$. Then, $${\mathcal{D}}\cap Gr_{\geq 0}(k,n) = {\mathcal{P}}\cap Gr_{\geq 0}(k,n).$$ Further, $${\mathcal{P}}_{u,v} = \bigsqcup_{{\mathbf{u}} \prec {\mathbf{v}}} {\mathcal{D}}_{{\mathbf{u}}, {\mathbf{v}}},$$ where the union is across all distinguished subexpressions for $u$ in ${\mathbf{v}}$. If one wants, they may take Theorem \[thm:positive\_deodhar\_components\] as the definition of the positroid strata ${\mathcal{P}}_{u,v}$, since we did not explicitly provide this definition. Corrective flips {#sec:corrective_flips} ================ Throughout this section, stones in diagrams will be colored black if and only if they are uncrossings. In @lam:total_positivity, Lam and Williams address the problem of giving a series of local moves on $\circ/+$-diagrams which may be used to transform any reduced diagram into the -diagram corresponding to the same pair of permutations. Such moves are called -moves. They solve this problem in all cominuscule types. In type A, the only case we consider in this paper, -moves are moves of the following form. $$\label{eqn:le-move} \begin{tikzpicture} \begin{scope}[scale=.75] \draw (0,0) -- (4,0) -- (4,3) -- (0,3) -- (0,0); \draw (1,0) -- (1,1) -- (0,1); \draw (1,3) -- (1,2) -- (0,2); \draw (3,3) -- (3,2) -- (4,2); \draw (3,0) -- (3,1) -- (4,1); \draw[thick] (0.5,0.2) -- (0.5,0.8); \draw[thick] (0.2,0.5) -- (0.8,0.5); \draw[thick] (0.5,2.2) -- (0.5,2.8); \draw[thick] (0.2,2.5) -- (0.8,2.5); \draw[thick] (3.5,2.2) -- (3.5,2.8); \draw[thick] (3.2,2.5) -- (3.8,2.5); \draw[fill = white] (3.5,.5) circle (.25); \draw (2,1.5) node {white stones}; \draw[thick, ->] plot [smooth, tension=.5] coordinates {(4.5,1.5) (4.75,1.65) (5,1.7) (5.25,1.65) (5.5,1.5)}; \begin{scope}[xshift=6cm] \draw (0,0) -- (4,0) -- (4,3) -- (0,3) -- (0,0); \draw (1,0) -- (1,1) -- (0,1); \draw (1,3) -- (1,2) -- (0,2); \draw (3,3) -- (3,2) -- (4,2); \draw (3,0) -- (3,1) -- (4,1); \draw[thick] (0.5,0.2) -- (0.5,0.8); \draw[thick] (0.2,0.5) -- (0.8,0.5); \draw[thick] (3.5,0.2) -- (3.5,0.8); \draw[thick] (3.2,0.5) -- (3.8,0.5); \draw[thick] (3.5,2.2) -- (3.5,2.8); \draw[thick] (3.2,2.5) -- (3.8,2.5); \draw[fill = white] (.5,2.5) circle (.25); \draw (2,1.5) node {white stones}; \end{scope} \end{scope} \end{tikzpicture}$$ The following theorem collects Lemma 4.13, Proposition 4.14, and Theorem 5.3 from @lam:total_positivity. \[thm:positroids\_via\_le\_moves\] Let $D$ be a reduced $\circ/+$-diagram. - If $D'$ is obtained from $D$ via -moves, the associated permutations associated to $D$ and $D'$ are identical. - $D$ is a -diagram if and only if no -moves may be applied to it. - Any sequence of -moves applied to $D$ terminates in the unique -diagram associated to the same pair of permutations. The goal of this section is to provide an analogous set of moves to transform any $\bullet/\circ/+$-diagram into a Go-diagram. The following example shows that -moves are not sufficient to transform any reduced diagram into a Go-diagram, so additional moves really are needed. Consider the following diagram. $$\begin{tikzpicture} \begin{scope}[scale=.75] \draw[step=1] (0,0) grid (3,3); \draw[thick] (.5,.2) -- (.5,.8); \draw[thick] (.2,.5) -- (.8,.5); \draw[fill = white] (1.5,.5) circle (.25); \draw[fill = white] (2.5,.5) circle (.25); \draw[fill = black] (.5,1.5) circle (.25); \draw[thick] (1.5,1.2) -- (1.5,1.8); \draw[thick] (1.2,1.5) -- (1.8,1.5); \draw[fill = white] (2.5,1.5) circle (.25); \draw[thick] (.5,2.2) -- (.5,2.8); \draw[thick] (.2,2.5) -- (.8,2.5); \draw[fill = black] (1.5,2.5) circle (.25); \draw[thick] (2.5,2.2) -- (2.5,2.8); \draw[thick] (2.2,2.5) -- (2.8,2.5); \end{scope} \end{tikzpicture}$$ This diagram is not a Go-diagram; the square in the top left corner violates the distinguished property since it should be an uncrossing with the square in the bottom right corner. Further, there are no -moves which may be applied to this diagram. \[def:corrective\_flip\] Let $D$ be a $\bullet/\circ/+$-diagram. Given a plus which violates the distinguished property, a <span>*corrective flip*</span>: - switches the plus with either the white stone with which it violates the distinguished property or that stone's uncrossing partner if it exists, then - relabels the stones in the diagram so that a stone is black if and only if it is an uncrossing. In @lam:total_positivity, one of the defining features of -moves is that only two squares change filling during the -move, one from a white stone to a plus and the other from a plus to a white stone. In the case of a $\bullet/\circ/+$-diagram, the coloring of stones white or black should be thought of purely as a pneumonic for which stones correspond to crossings and uncrossings in the pipe dream. When performing a corrective flip, in the pipe dream only two tiles change, one from an elbow piece to a crossing and the other from a crossing to an elbow. The possible change in coloring of other stones in the diagram is a necessary side effect of this two square swap. \[prop:corrective\_flip\_observations\] Let $D$ be a $\bullet/\circ/+$-diagram. - $D$ is a Go-diagram if and only if there are no available corrective flips. - Corrective flips preserve the pair of permutations associated to a diagram. - Corrective flips preserve number of black stones, white stones, and pluses in a diagram. - Suppose pipes $i$ and $j$ cross at the crossing tile involved in a corrective flip. Then, the only stones which change color when preforming a corrective flip are along pipes $i$ and $j$ on the segments between the plus and crossing tile involved in the flip. - $D$ can be transformed into a Go-diagram via corrective flips. Points (i), (ii), and (iv) are obvious looking at the pipe dream associated to a diagram. Point (iii) is a consequence of Proposition \[prop:length\_from\_filling\] and the fact that a corrective flip preserves the number of pluses in a diagram. For point (v), observe that if we only preform corrective flips switching pluses and white stones, the pluses only move downward. We may preform such flips until no more corrective flips are available, at which point point (i) implies the end result is a Go-diagram. \[lem:corrective\_flips\_decrease\_length\] Let $D$ be a $\bullet/\circ/+$-diagram and let $D'$ be obtained from $D$ by performing a corrective flip. Then, $u_{b^{in}}^{D} \geq u_{b^{in}}^{D'}$ for all $b \in D$. Let $c$ and $d$ be the boxes participating in the corrective flip and suppose that $c \prec d$. If $c \notin b^{in}$ or $d \in b^{in}$, then $u_{b^{in}}^{D} = u_{b^{in}}^{D'}$. If $c \in b^{in}$ and $d \notin b^{in}$, then $u_{b^{in}}^{D} < u_{b^{in}}^{D'}$. In fact, a converse to Lemma \[lem:corrective\_flips\_decrease\_length\] holds as well. \[prop:only\_corrective\_flips\_decrease\_length\] Let $D$ and $D'$ be $\bullet/\circ/+$-diagrams with the same associated pair of permutations and suppose that $D'$ is obtained from $D$ by exchanging a single elbow piece and crossing tile in the associated pipe dreams. If $u_{b^{in}}^{D} \geq u_{b^{in}}^{D'}$ for all $b \in D$, then $D'$ was obtained from $D$ by performing a corrective flip. If $D$ and $D'$ give the same pair of permutations and differ by exchanging a single elbow piece and crossing tile in their pipe dreams, the elbow piece and crossing tile exchanged must involve the same pair of pipes. Say the exchanged crossing tile is in box $c$ and the elbow piece is in box $d$. If $c$ contained a white stone in $D$, we must have $c \prec d$, otherwise $u_{b^{in}}^{D} < u_{b^{in}}^{D'}$ for any box $d \prec b \prec c$. If there were some box $c \prec e \prec d$ which was an uncrossing pair with $c$ in $D$, then $u_{b^{in}}^{D} < u_{b^{in}}^{D'}$ for any box $e \prec b \prec d$. So, in this case $D'$ is obtained from $D$ via a corrective flip. If $c$ contained a black stone in $D$, we must have $d \prec c$, otherwise $u_{b^{in}}^{D} < u_{b^{in}}^{D'}$ for any box $c \prec b \prec d$. In this case, if $d$ had a crossing pair $e$ with $d \prec e \prec c$, then $u_{b^{in}}^{D} < u_{b^{in}}^{D'}$ for any box $c \prec b \prec e$. \[thm:corrective\_flips\_terminate\] Every sequence of corrective flips terminates in a Go-diagram. To a diagram $D$, we associate the tuple $$\tau(D) = \bigoplus_{b \in D} u_{b^{in}}^{D} \in \bigoplus_{b \in D} \mathfrak{S}_n.$$ We endow $\bigoplus_{b \in D} \mathfrak{S}_n$ with the product partial order obtained from the Bruhat orders on each copy of $\mathfrak{S}_n$. Let $D'$ be obtained from $D$ by performing a corrective flip. Lemma \[lem:corrective\_flips\_decrease\_length\] implies $\tau(D') < \tau(D)$. So, any sequence of corrective flips must terminate. Then, point (ii) in Proposition \[prop:corrective\_flip\_observations\] implies any sequence of corrective flips terminates in a Go-diagram. Unlike point (iii) in Theorem \[thm:positroids\_via\_le\_moves\], there might be more than one Go-diagram obtainable from a $\bullet/\circ/+$-diagram via corrective flips. Consider the $\bullet/\circ/+$-diagram $$\label{eqn:boundary_example_after_flip} \begin{tikzpicture} \begin{scope}[scale=.75] \draw[step = 1] (0,0) grid (3,3); \draw[thick] (.5,.2) -- (.5,.8); \draw[thick] (.2,.5) -- (.8,.5); \draw[thick] (1.5,.2) -- (1.5,.8); \draw[thick] (1.2,.5) -- (1.8,.5); \draw[fill = white] (2.5,.5) circle (.25); \draw[thick] (.5,1.2) -- (.5,1.8); \draw[thick] (.2,1.5) -- (.8,1.5); \draw[thick] (1.5,1.2) -- (1.5,1.8); \draw[thick] (1.2,1.5) -- (1.8,1.5); \draw[thick] (2.5,1.2) -- (2.5,1.8); \draw[thick] (2.2,1.5) -- (2.8,1.5); \draw[fill = black] (.5,2.5) circle (.25); \draw[thick] (1.5,2.2) -- (1.5,2.8); \draw[thick] (1.2,2.5) -- (1.8,2.5); \draw[thick] (2.5,2.2) -- (2.5,2.8); \draw[thick] (2.2,2.5) -- (2.8,2.5); \draw (3.2,.1) node {,}; \end{scope} \end{tikzpicture}$$ which is not a Go-diagram. Using corrective flips, it may be transformed into either $$\label{eqn:boundary_example_after_correcting} \begin{tikzpicture} \begin{scope}[scale=.75] \draw[step = 1] (0,0) grid (3,3); \draw[thick] (.5,.2) -- (.5,.8); \draw[thick] (.2,.5) -- (.8,.5); \draw[thick] (1.5,.2) -- (1.5,.8); \draw[thick] (1.2,.5) -- (1.8,.5); \draw[fill = white] (2.5,.5) circle (.25); \draw[thick] (.5,1.2) -- (.5,1.8); \draw[thick] (.2,1.5) -- (.8,1.5); \draw[fill = black] (1.5,1.5) circle (.25); \draw[thick] (2.5,1.2) -- (2.5,1.8); \draw[thick] (2.2,1.5) -- (2.8,1.5); \draw[thick] (.5,2.2) -- (.5,2.8); \draw[thick] (.2,2.5) -- (.8,2.5); \draw[thick] (1.5,2.2) -- (1.5,2.8); \draw[thick] (1.2,2.5) -- (1.8,2.5); \draw[thick] (2.5,2.2) -- (2.5,2.8); \draw[thick] (2.2,2.5) -- (2.8,2.5); \draw (4,1.5) node {or}; \begin{scope}[xshift=5cm] \draw[step = 1] (0,0) grid (3,3); \draw[thick] (.5,.2) -- (.5,.8); \draw[thick] (.2,.5) -- (.8,.5); \draw[thick] (1.5,.2) -- (1.5,.8); \draw[thick] (1.2,.5) -- (1.8,.5); \draw[thick] (2.5,.2) -- (2.5,.8); \draw[thick] (2.2,.5) -- (2.8,.5); \draw[thick] (.5,1.2) -- (.5,1.8); \draw[thick] (.2,1.5) -- (.8,1.5); \draw[fill = white] (1.5,1.5) circle (.25); \draw[thick] (2.5,1.2) -- (2.5,1.8); \draw[thick] (2.2,1.5) -- (2.8,1.5); \draw[fill = black] (.5,2.5) circle (.25); \draw[thick] (1.5,2.2) -- (1.5,2.8); \draw[thick] (1.2,2.5) -- (1.8,2.5); \draw[thick] (2.5,2.2) -- (2.5,2.8); \draw[thick] (2.2,2.5) -- (2.8,2.5); \draw (3.2,.1) node {.}; \end{scope} \end{scope} \end{tikzpicture}$$ One could remove this aspect of free will from the definition of corrective flip, for instance by defining corrective flips to only switch pluses and white stones. However, we find Definition \[def:corrective\_flip\] is the correct choice of definition given Proposition \[prop:only\_corrective\_flips\_decrease\_length\] and the role corrective flips play in the boundary structure of Deodhar components, described in Section \[sec:boundaries\]. The set of corrective flips as described is not a minimal set of moves with the properties described in Proposition \[prop:corrective\_flip\_observations\] and Theorem \[thm:corrective\_flips\_terminate\]. If one wanted a smaller set of moves with these properties, they could consider only corrective flips such that the elbow and crossing pieces being switched in the pipe dream have no other elbow pieces between them involving the same pair of pipes. However, even this set of moves isn't minimal: restricted to reduced diagrams, it is a strictly larger set of moves than the set of -moves. It might be interesting to describe a set of corrective flips which is minimal and whose specialization to reduced diagrams is exactly the set of -moves. Boundaries {#sec:boundaries} ========== Throughout this section, stones in diagrams will be colored black if and only if they are uncrossings. The main theorem of this section describes a particular instance of when there is a containment of closures of Deodhar components, $\overline{{\mathcal{D}}'} \subset \overline{{\mathcal{D}}}$, within a Schubert cell. \[thm:diagrammatic\_boundaries\] Let $D$ and $D'$ be Go-diagrams with the same Ferrers shape indexing Deodhar components ${\mathcal{D}}$ and ${\mathcal{D}}'$. Then, $\overline{{\mathcal{D}}'} \subset \overline{{\mathcal{D}}}$ with $\dim({\mathcal{D}}) = \dim({\mathcal{D}}') + 1$ if $D$ is obtained by $D'$ by: - Choosing a crossing/uncrossing pair in $D'$, - replacing the two stones in this pair with pluses and relabelling the other stones in the diagram such that stone is colored black if and only if it is an uncrossing, then - performing corrective flips. or by: - Choosing a white stone without an uncrossing pair in $D'$ such that replacing this stone with a plus decreases the length of the diagram's permutation by exactly one, - replacing this white stone with a plus and relabelling the other stones in the diagram such that stone is colored black if and only if it is an uncrossing, then - performing corrective flips. For an example of the first set of moves, consider the Go-diagram $$\begin{tikzpicture} \begin{scope}[scale=.75] \draw (-1,1.5) node {$D' = $}; \draw[step = 1] (0,0) grid (3,3); \draw[thick] (.5,.2) -- (.5,.8); \draw[thick] (.2,.5) -- (.8,.5); \draw[thick] (1.5,.2) -- (1.5,.8); \draw[thick] (1.2,.5) -- (1.8,.5); \draw[fill = white] (2.5,.5) circle (.25); \draw[thick] (.5,1.2) -- (.5,1.8); \draw[thick] (.2,1.5) -- (.8,1.5); \draw[thick] (1.5,1.2) -- (1.5,1.8); \draw[thick] (1.2,1.5) -- (1.8,1.5); \draw[fill = white] (2.5,1.5) circle (.25); \draw[fill = black] (.5,2.5) circle (.25); \draw[fill = black] (1.5,2.5) circle (.25); \draw[thick] (2.5,2.2) -- (2.5,2.8); \draw[thick] (2.2,2.5) -- (2.8,2.5); \draw (3.2,.1) node {.}; \end{scope} \end{tikzpicture}$$ The white stone at $(2,4)$ and the black stone at $(1,5)$ form a crossing/uncrossing pair. Replacing the stones in these squares with pluses yields the diagram (\[eqn:boundary\_example\_after\_flip\]) from the previous section. We saw that this diagram could be transformed into either of the Go-diagrams (\[eqn:boundary\_example\_after\_correcting\]) via corrective flips. So, ${\mathcal{D}}'$ is a codimension one boundary of both of the two Deodhar components labelled by the Go-diagrams (\[eqn:boundary\_example\_after\_correcting\]). For an example of the second set of moves, consider the Go-diagram $$\begin{tikzpicture} \begin{scope}[scale=.75] \draw (-1,1) node {$D' = $}; \draw[step = 1] (0,0) grid (4,2); \draw[thick] (.5,.2) -- (.5,.8); \draw[thick] (.2,.5) -- (.8,.5); \draw[fill = white] (1.5,.5) circle (.25); \draw[thick] (2.5,.2) -- (2.5,.8); \draw[thick] (2.2,.5) -- (2.8,.5); \draw[thick] (3.5,.2) -- (3.5,.8); \draw[thick] (3.2,.5) -- (3.8,.5); \draw[thick] (.5,1.2) -- (.5,1.8); \draw[thick] (.2,1.5) -- (.8,1.5); \draw[fill = white] (1.5,1.5) circle (.25); \draw[fill = white] (2.5,1.5) circle (.25); \draw[thick] (3.5,1.2) -- (3.5,1.8); \draw[thick] (3.2,1.5) -- (3.8,1.5); \draw (4.2,.1) node {.}; \end{scope} \end{tikzpicture}$$ Replacing the white stone at $(1,5)$ with a plus decreases the length of the permutation by exactly one, so this replacement is valid. After, performing this replacement we obtain the diagram $$\begin{tikzpicture} \begin{scope}[scale=.75] \draw[step = 1] (0,0) grid (4,2); \draw[thick] (.5,.2) -- (.5,.8); \draw[thick] (.2,.5) -- (.8,.5); \draw[fill = white] (1.5,.5) circle (.25); \draw[thick] (2.5,.2) -- (2.5,.8); \draw[thick] (2.2,.5) -- (2.8,.5); \draw[thick] (3.5,.2) -- (3.5,.8); \draw[thick] (3.2,.5) -- (3.8,.5); \draw[thick] (.5,1.2) -- (.5,1.8); \draw[thick] (.2,1.5) -- (.8,1.5); \draw[thick] (1.5,1.2) -- (1.5,1.8); \draw[thick] (1.2,1.5) -- (1.8,1.5); \draw[fill = white] (2.5,1.5) circle (.25); \draw[thick] (3.5,1.2) -- (3.5,1.8); \draw[thick] (3.2,1.5) -- (3.8,1.5); \draw (4.2,.1) node {,}; \end{scope} \end{tikzpicture}$$ which is not a Go-diagram. Performing corrective flips, which in this case are simply -moves, we arrive at the diagram $$\begin{tikzpicture} \begin{scope}[scale=.75] \draw (-1,1) node {$D = $}; \draw[step = 1] (0,0) grid (4,2); \draw[thick] (.5,.2) -- (.5,.8); \draw[thick] (.2,.5) -- (.8,.5); \draw[thick] (1.5,.2) -- (1.5,.8); \draw[thick] (1.2,.5) -- (1.8,.5); \draw[thick] (2.5,.2) -- (2.5,.8); \draw[thick] (2.2,.5) -- (2.8,.5); \draw[thick] (3.5,.2) -- (3.5,.8); \draw[thick] (3.2,.5) -- (3.8,.5); \draw[fill = white] (.5,1.5) circle (.25); \draw[thick] (1.5,1.2) -- (1.5,1.8); \draw[thick] (1.2,1.5) -- (1.8,1.5); \draw[fill = white] (2.5,1.5) circle (.25); \draw[thick] (3.5,1.2) -- (3.5,1.8); \draw[thick] (3.2,1.5) -- (3.8,1.5); \draw (4.2,.1) node {.}; \end{scope} \end{tikzpicture}$$ So, the Deodhar component ${\mathcal{D}}'$ is a codimension one boundary of ${\mathcal{D}}$. The diagrams $D$ and $D'$ are also -diagrams and thus index positroid cells ${\mathcal{P}}$ and ${\mathcal{P}}'$. One also has that ${\mathcal{P}}'$ is a codimension one boundary of ${\mathcal{P}}$. To prove Theorem \[thm:diagrammatic\_boundaries\], we will need a technical lemma. \[lem:technical\_for\_boundaries\] Let $D$ and $D'$ be $\bullet/\circ/+$-diagrams and suppose $D$ is obtained from $D'$ by performing a corrective flip. If $b$ contains a white stone in $D$, but not in $D'$, then $I_b^{D} > I_b^{D'}$. Moreover, let $J_b^{D'}$ be the set (\[eqn:J\_b\]) from Proposition \[prop:large\_sets\_vanish\]. In the case above, $I_b^{D} > J_b^{D'}$. Let $D$ be obtained from $D'$ by performing a corrective flip involving the pipes $i$ and $j$ with $i < j$. Let $b$ contain a white stone in $D$ but not in $D'$. From point (iv) in Proposition \[prop:corrective\_flip\_observations\], $b$ must be along either the pipe $i$ or $j$ between the two squares involved in the corrective flip. If $b$ contains a plus in $D'$, it must be the plus that was involved in the corrective flip. Then, $I_b^{D'} = I_b^{D} \setminus j \cup i$, so $I_b^{D} > I_b^{D'}$. In this case, $J_b^{D'} = I_b^{D'}$. So, $I_b^{D} > J_b^{D'}$ as well. Suppose $b$ contains a black stone in $D'$. Then, the pipes coming into $b$ in pipe dream associated to $D'$ look like one of the four following cases. $$\begin{tikzpicture} \begin{scope}[scale=.75] \draw[step=1] (0,0) grid (1,1); \draw[fill = black] (.5,.5) circle (.25); \draw[very thick] (.5,-.4) -- (.5,-.05); \draw (.5,-.7) node {$i$}; \draw[very thick] (1.05,.5) -- (1.4,.5); \draw (1.7,.5) node {$k$}; \draw (-1,.5) node {(i)}; \begin{scope}[xshift = 5cm] \draw[step=1] (0,0) grid (1,1); \draw[fill = black] (.5,.5) circle (.25); \draw[very thick] (.5,-.4) -- (.5,-.05); \draw (.5,-.7) node {$k$}; \draw[very thick] (1.05,.5) -- (1.4,.5); \draw (1.7,.5) node {$i$}; \draw (-1,.5) node {(ii)}; \end{scope} \begin{scope}[xshift = 10cm] \draw[step=1] (0,0) grid (1,1); \draw[fill = black] (.5,.5) circle (.25); \draw[very thick] (.5,-.4) -- (.5,-.05); \draw (.5,-.7) node {$j$}; \draw[very thick] (1.05,.5) -- (1.4,.5); \draw (1.7,.5) node {$k$}; \draw (-1,.5) node {(iii)}; \end{scope} \begin{scope}[xshift = 15cm] \draw[step=1] (0,0) grid (1,1); \draw[fill = black] (.5,.5) circle (.25); \draw[very thick] (.5,-.4) -- (.5,-.05); \draw (.5,-.7) node {$k$}; \draw[very thick] (1.05,.5) -- (1.4,.5); \draw (1.7,.5) node {$j$}; \draw (-1,.5) node {(iv)}; \end{scope} \end{scope} \end{tikzpicture}$$ In case (ii), $k < i$. So, $k < j$ and $b$ would still be filled with a black stone when the corrective flip switches the pipes $i$ and $j$. Similarly, in case (iii), $j < k$ and $b$ would still be filled with a black stone in $D$. In case (i), $b$ contains a white stone in $D$ if and only if $i < k < j$. The set $I_b^{D'}$ contains $i$ and $I_b^{D}$ contains $j$, since the square $b$ is temporarily filled with an elbow piece when determining $I_b$. So, $I_b^{D'} = I_b^{D} \setminus j \cup i$, and $I_b^{D} > I_b^{D'}$. In this case, $J_b^{D'} = I_b^{D} \setminus j \cup k$, and since $k < j$, $I_b^{D} > J_b^{D'}$. Finally, in case (iv) note that since $b$ is along the segment of pipe between the two boxes in the corrective flip, the pipe $i$ appears somewhere below the box $b$ in its column. If $k = i$, then $b$ must be the uncrossing tile paired with the crossing which caused the corrective flip. In this case, $b$ will not be filled with a white stone after performing the corrective flip to reach $D$. Since the pipe $i$ appears somewhere below $b$ in its column and is not involved in the crossing at $b$, $i \in I_b^{D'}$. Since $b$ is temporarily filled with an elbow piece when determining $I_b^{D'}$, $j \notin I_b^{D'}$. So, again $I_b^{D'} = I_b^{D} \setminus j \cup i$, and $I_b^{D} > I_b^{D'}$. In this case, $J_b^{D'} = I_b^{D} \setminus j \cup k$, and since $i < k < j$, $I_b^{D} > J_b^{D'}$. \[Proof of Theorem \[thm:diagrammatic\_boundaries\]\] Let $D$ and $D'$ be Go-diagrams of shape $\lambda$ and suppose that $D$ is obtained from $D'$ by either of the two procedures in the theorem statement. Let ${\mathcal{D}}$ and ${\mathcal{D}}'$ be the
{'source': 'arXiv_out/1807'}