\documentclass[finalversion]{FPSAC2018} %[submission]
\articlenumber{44}

% Theorems-like Format and Numbering:
\newtheorem*{maintheorem*}{Main Theorem}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
%\figure[theorem]
\numberwithin{equation}{section}

% Personalized Commands:
\newcommand{\rr}{\mathbb{R}}
\newcommand{\zz}{\mathbb{Z}}

\newcommand{\twopf}[4]
{
	\left\{
	\begin{array}{ll}
		#1 & \mbox{if } #2 \\
		#3 & \mbox{if } #4
	\end{array}
	\right.
}

\newcommand{\fivepf}[9]
{
	\left\{
	\begin{array}{ll}
		#1 & \mbox{if } #2 \\
		#3 & \mbox{if } #4 \\
		#5 & \mbox{if $i=1$} \\
		#6 & \mbox{if } #7 \\
		#8 & \mbox{if } #9
	\end{array}
	\right.
}

\usepackage{lipsum}

\title{On positroids induced by rational Dyck paths}

\author{Felix
Gotti\thanks{\href{mailto:felixgotti@berkeley.edu}{felixgotti@berkeley.edu}.
The author was partially supported by the NSF-AGEP
Fellowship.}\addressmark{1}}

\address{\addressmark{1}Department of Mathematics, UC Berkeley}

\received{\today}

\abstract{A rational Dyck path of type $(m,d)$ is an increasing unit-step lattice path from $(0,0)$ to $(m,d) \in \zz^2$ that never goes above the diagonal line $y = (d/m)x$. On the other hand, a positroid of rank $d$ on the ground set $[d+m]$ is a special type of matroid coming from the totally nonnegative Grassmannian. In this paper we describe how to naturally assign a rank $d$ positroid on the ground set $[d+m]$, which we name \emph{rational Dyck positroid}, to each rational Dyck path of type $(m,d)$. Positroids can be parameterized by several families of combinatorial objects. Here we characterize some of these families for the positroids we produce, namely, decorated permutations, \reflectbox{L}-diagrams, and move-equivalence classes of plabic graphs. Finally, we describe the matroid polytope of a given rational Dyck positroid.}

\keywords{Rational Dyck path, positroid, Grassmannian, plabic graph, \reflectbox{L}-diagram}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{44-Gotti.bib}

\begin{document}

\maketitle

\section{Introduction} \label{sec:intro}

For each pair of nonnegative integers $(m,d)$, a \emph{rational Dyck path} of type $(m,d)$ is a lattice path from $(0,0)$ to $(m,d)$ whose steps are either horizontal or vertical subject to the restriction that it never goes above the line $y = (d/m)x$. Figure~\ref{fig:rational Dyck path} below depicts a rational Dyck path of type $(8,5)$. Note that a rational Dyck path of type $(m,m)$ is just an ordinary Dyck path of length $2m$. The number $\text{Cat}(m,d)$ of rational Dyck paths of type $(m,d)$ is the \emph{rational Catalan number} associated to the pair $(m,d)$. It is known that
\[
	\text{Cat}(m,d) = \frac{1}{d+m} \binom{d+m}{d}
\]
when $\gcd(d,m) = 1$. Rational Catalan numbers also appear in the context of partitions. An $(m,d)$-\emph{core} is a partition having no hook lengths equal to $d$ or $m$. A bijection from the set of rational Dyck paths of type $(m,d)$ to the set of $(m,d)$-cores has been established by Anderson in \cite{jA02}.

\begin{figure}[h]
	\centering
	\includegraphics[width = 7.3cm]{images/RationalDyckPath.png}
	\caption{A rational Dyck path of type $(8,5)$.} \label{fig:rational Dyck path}
\end{figure}

Motivated by the work of Lusztig~\cite{gL98} and the work of Fomin and Zelevinsky~\cite{FZ99}, in~\cite{aP06} Postnikov introduced positroids as matroids represented by elements of $(\text{Gr}_{d,n})_{\ge 0}$, the totally nonnegative Grassmannian. He also showed that positroids are in bijection with various families of elegant combinatorial objects, including Grassmann necklaces, decorated permutations, \reflectbox{L}-diagrams, and certain equivalence classes of plabic graphs (all of them to be formally defined later). Positroids and the totally nonnegative Grassmannian have been the focus of much attention lately as they are connected to many mathematical subjects under active investigation including free probability~\cite{ARW16}, soliton solutions to the KP~equation~\cite{KW14}, mirror symmetry~\cite{MR13}, and cluster algebras~\cite{jS06}.

We call a $d \times m$ binary matrix a \emph{rational Dyck matrix} if its zero entries are separated from its one entries by a vertically-reflected rational Dyck path of type $(m,d)$. We let $\mathcal{D}_{d,m}$ denote the set of $d \times m$ rational Dyck matrices. If $D = (a_{i,j})$ is a rational Dyck matrix, we shall see in Section~\ref{sec:rational Dyck positroids} that the matrix
\begin{equation*} \label{UIP generic matrix}
	\bar{D} =\begin{pmatrix}
		1  	  		&\dots   &  0        &   0  	 & (-1)^{d-1} a_{d,1} & \dots	& (-1)^{d-1} a_{d,m}  \\
		\vdots  &\ddots  &\vdots & \vdots & \vdots 	      			& \ddots & \vdots         			\\
		0  	  		&\dots   &  1        &   0  	 & -a_{2,1}  			& \dots   & -a_{2,m}    		     \\
		0  	  		&\dots   &  0        &   1  	 & a_{1,1}        			& \dots   & a_{1,m}   
	\end{pmatrix}
\end{equation*}
has all its maximal minors nonnegative. We call the positroids represented by matrices like $\bar{D}$ \emph{rational Dyck positroids}. In this paper we study rational Dyck positroids by establishing combinatorial descriptions for some of the families of objects parametrizing them. For a version including the proofs of all the results we present here, see \cite{fG17}.

\section{Rational Dyck Positroids} \label{sec:rational Dyck positroids}

If $X$ is an $n \times n$ real matrix and $I,J \subseteq [n] := \{1,\dots,n\}$ satisfy $|I| = |J|$, then we let $\Delta_{I,J}(X)$ denote the minor of $X$ determined by the rows indexed by $I$ and the columns indexed by $J$. Besides, if $Y$ is a $k \times n$ matrix and $K \subseteq [n]$ satisfies $|K| = k$, then we let $\Delta_K(Y)$ denote the maximal minor of $Y$ determined by the set of columns indexed by $K$.

Let $\text{Mat}_{d,m}(\rr)$ denote the set of all $d \times m$ real matrices, and let $\text{Mat}^+_{d,m}(\rr)$ denote the subset of $\text{Mat}_{d,m}(\rr)$ consisting of all full-rank matrices with nonnegative maximal minors. Consider the assignment $\phi_{d,m} \colon \text{Mat}_{d,m}(\rr) \to \text{Mat}_{d,d+m}(\rr)$ defined by
\[
	\begin{pmatrix}
		a_{1,1} 		& \dots		 & a_{1,m}     \\
		\vdots 	      & \ddots	   & \vdots     \\
		a_{d-1,1}    & \dots       & a_{d-1,m} \\
		a_{d,1}        & \dots      & a_{d,m}    
	\end{pmatrix} \
	\stackrel{\phi_{d,m}}{\longmapsto} \
	\begin{pmatrix}
		1  	  	 	 &\dots    &  0        &   0  	   & (-1)^{d-1} a_{d,1}   & \dots	& (-1)^{d-1} a_{d,m} \\
		\vdots   &\ddots  &\vdots   & \vdots & \vdots 	      			& \ddots & \vdots \\
		0  	  		&\dots    &  1         &   0  	   & -a_{2,1}  			      & \dots   & -a_{2,m} \\
		0  	  		&\dots    &  0        &   1  	   & a_{1,1}        		   & \dots   & a_{1,m}   
	\end{pmatrix}.\! \!
\]

%As the next lemma reveals, $\phi_{d,m}$ somehow respects the minors of a given matrix.

\begin{lemma}[{\cite[Lemma~3.9]{aP06}}] \label{lem:correspondence between totally nonnegative square and rectangular matrix}\!\footnote{There is a typo in the entries of the matrix $B$ in \cite[Lemma~3.9]{aP06}.}
	If $A \in \emph{Mat}_{d,m}(\rr)$ and $B = \phi_{d,m}(A)$, then
	\[
		\Delta_{I,J}(A) = \Delta_{(d+1 - [d]\setminus I) \cup (d + J)}(B)
	\]
	for all $I \subseteq [d]$ and $J \subseteq [m]$ satisfying $|I| = |J|$.
\end{lemma}

By using Lemma~\ref{lem:correspondence between totally nonnegative square and rectangular matrix}, we can prove the following result.

\begin{prop} \label{prop:image of rational Dyck matrices are totally nonnegative}
	$\phi_{d,m}(\mathcal{D}_{d,m}) \subseteq \emph{Mat}_{d,d+m}^+(\rr)$.
\end{prop}

Let $E$ be a finite set, and let $\mathcal{B}$ be a nonempty collection of subsets of $E$. The pair $M = (E, \mathcal{B})$ is a \emph{matroid} if for all $B,B' \in \mathcal{B}$ and $b \in B \setminus B'$, there exists $b' \in B' \setminus B$ such that $(B \setminus \{b\}) \cup \{b'\} \in \mathcal{B}$. The set $E$ is called the \emph{ground set} of $M$, while the elements of $\mathcal{B}$ are called \emph{bases}. Any two bases of $M$ have the same size, which we call the \emph{rank} of $M$.

\begin{definition}
	A rank $d$ matroid $([m], \mathcal{B})$ is called a \emph{positroid} if there exists $A \in \text{Mat}_{d,m}^+(\rr)$ with columns $A_1, \dots, A_m$ such that $\mathcal{B} = \big\{B \subseteq [m] \mid \{ A_b \mid b \in B \} \  \text{is a basis for} \ \mathbb{R}^d \big\}$. In this case, we say that the matrix $A$ \emph{represents} the positroid $([m], \mathcal{B})$.
\end{definition}

By Proposition~\ref{prop:image of rational Dyck matrices are totally nonnegative} each matrix in $\phi_{d,m}(\mathcal{D}_{d,m})$ represents a rank $d$ positroid on $[d+m]$.

\begin{definition}
	We call a positroid represented by a matrix in $\phi_{d,m}(\mathcal{D}_{d,m})$ a \emph{rational Dyck positroid}, and we denote by $\mathcal{P}_{d,m}$ the set of rank $d$ rational Dyck positroids on $[d+m]$.
\end{definition}

\section{Grassmann Necklaces and Decorated Permutations} \label{sec:decorated permutation} \label{sec:grassmann necklace}

Let us start by introducing the concept of Grassmann necklaces. %Then we will describe the Grassmann necklaces corresponding to rational Dyck positroids.

\begin{definition}
	An $n$-tuple $(I_1, \dots, I_n)$ of ordered $d$-subsets of $[n]$ is called a \emph{Grassmann necklace} of type $(d,n)$ if for every $i \in [n]$ the following two conditions hold:
	\begin{itemize}
		\item $i \in I_i$ implies $I_{i+1} = (I_i \setminus \{i\}) \cup \{j\}$ for some $j \in [n]$;
		\item $i \notin I_i$ implies $I_{i+1} = I_i$.
	\end{itemize}
\end{definition}

For $i \in [n]$, the total order $([n], \le_i)$ is defined by $i \le_i \dots \le_i n \le_i 1 \le_i \dots \le_i i-1$. Given a matroid $M = ([n], \mathcal{B})$ of rank $d$, the sequence $\mathcal{I}(M) = (I_1, \dots, I_n)$, where $I_i$ is the lexicographically minimal ordered basis of $M$ with respect to $\le_i$, is a Grassmann necklace of type $(d,n)$ (see \cite{aP06}). Also, for $i \in [n]$ and subsets $S = \{s_1 \le_i \dots \le_i s_d\}$ and $T = \{t_1 \le_i \dots \le_i t_d\}$ of $[n]$, we write $S \preceq_i T$ if $s_j \le_i t_j$ for each $j \in [d]$. Finally, we let $\binom{[n]}{d}$ denote the collection of all $d$-subsets of $[n]$.

\begin{theorem}[{\cite[Theorem~6]{sO11}}] \label{thm:bijection between Grassmann necklaces and positroids}
	If $\mathcal{I} = (I_1, \dots, I_n)$ is a Grassmann necklace of type $(d,n)$, then $\mathcal{B}(\mathcal{I}) = \big\{B \in \binom{[n]}{d} \mid I_j \preceq_j B \ \text{for each} \ j \in [n] \big\}$ is the collection of bases of a positroid $M(\mathcal{I}) = ([n], \mathcal{B}(\mathcal{I}))$. Moreover, $M(\mathcal{I}(M)) = M$ for all positroids $M$.
\end{theorem}

By Theorem~\ref{thm:bijection between Grassmann necklaces and positroids}, the map $P \mapsto \mathcal{I}(P)$ is a one-to-one correspondence between the set of rank $d$ positroids on the ground set $[n]$ and the set of Grassmann necklaces of type $(d,n)$. For a positroid $P$, we call $\mathcal{I}(P)$ its \emph{corresponding} Grassmann necklace.
\vspace{6pt}

We can also parameterize positroids using decorated permutations, which offer a more compact parameterization than Grassmann necklaces do.

\begin{definition}
	A \emph{decorated permutation} on $n$ letters is an element $\pi
	\in S_n$ with its fixed points $j$ marked either ``clockwise''
	(denoted by $\pi(j)=\underline{j}$) or ``counterclockwise'' (denoted by $\pi(j) = \overline{j}$). A position $j \in [n]$ is a \emph{weak excedance} of $\pi$ if $j < \pi(j)$ or $\pi(j) = \overline{j}$.
\end{definition}

Following the next recipe, one can assign a decorated permutation $\pi_{\mathcal{I}}$ to each Grassmann necklace $\mathcal{I} = (I_1, \dots, I_n)$:
\begin{enumerate}
	\item if $I_{i+1} = (I_i \setminus \{i\}) \cup \{j\}$ for $i \neq j$, then $\pi_{\mathcal{I}}(j) = i$;
	\item if $I_{i+1} = I_i$ and $i \notin I_i$, then $\pi_\mathcal{I}(i) = \underline{i}$;
	\item if $I_{i+1} = I_i$ and $i \in I_i$, then $\pi_\mathcal{I}(i) = \overline{i}$.
\end{enumerate}
Moreover, the map $\mathcal{I} \mapsto \pi_{\mathcal{I}}$ is a bijection from the set of Grassmann necklaces of type $(d,n)$ to the set of decorated permutations of $n$ letters having $d$ weak excedances, whose inverse is given by $\pi \mapsto (I_1, \dots, I_n)$, where $I_i = \{j \in [n] \mid j \le_i \pi^{-1}(j) \text{ or } \pi(j) = \bar{j}\}$.


%In the following theorem we generalize \cite[Theorem~4.4]{CG17}.

\begin{theorem} \label{thm:decorated permutation of rational Dyck positroids}
	The decorated permutation $\pi$ of a rank $d$ rational Dyck positroid on $[d+m]$ is a $(d+m)$-cycle. Moreover, the set of weak excedances of $\pi$ is $[d]$.
\end{theorem}

\begin{cor}
	Every rational Dyck positroid $(E, \mathcal{B})$ is connected, i.e., for every $b, b' \in E$ there exist $B,B' \in \mathcal{B}$ such that $B' = (B \setminus \{b\}) \cup \{b'\}$.
\end{cor}

The explicit description of the decorated permutation of a rational Dyck path given in Theorem~\ref{thm:decorated permutation of rational Dyck positroids} allows us to establish the following theorem.

\begin{theorem}
	There is a bijection between the set of rational Dyck paths of type $(m,d)$ and the set of rank $d$ rational Dyck positroids on the ground set $[d+m]$.
\end{theorem}

\begin{cor}
	The number of rank $d$ rational Dyck positroids on $[d+m]$ equals $\emph{Cat}(m,d)$. If $\gcd(d,m) = 1$ there are $\frac 1{d+m} \binom{d+m}{d}$ rank $d$ rational Dyck positroids on $[d+m]$.
\end{cor}

Here is a simple way to find the decorated permutation of a rational Dyck positroid.

\begin{prop}[cf. {\cite[Proposition~5.1]{CG17}}] \label{prop:decoding decorated permutation}
	Let $\mathsf{d}$ be a rational Dyck path of type $(m,d)$. Labeling the $d$ vertical steps of $\mathsf{d}$ from top to bottom by $1, \dots, d$ and the $m$ horizontal steps from left to right by $d+1, \dots, d+m$, we obtain the decorated permutation of the rational Dyck positroid induced by $\mathsf{d}$ once we read the step labels of $\mathsf{d}$ in southwest direction.
\end{prop}

\begin{example}
	Let $P$ be the rational Dyck positroid induced by the rational Dyck path $\mathsf{d}$ shown below. The path $\mathsf{d}$ is labeled as in Proposition~\ref{prop:decoding decorated permutation}. The decorated permutation $(1 \ 2 \ 1\!3 \ 1\!2 \ 3 \ 1\!1 \ 1\!0 \ 4 \ 9 \ 5 \ 8 \ 7 \ 6)$ is obtained by reading the labels of $\mathsf{d}$ in southwest direction.
	\begin{figure}[h]
		\centering
		\includegraphics[width = 5.7cm]{images/PermutationFromDyckPath.png}
		\caption{Rational Dyck path encoding the decorated permutation of $P$.}
		\label{fig:permutation from rational Dyck path}
	\end{figure}
\end{example}

\section{Le-diagrams} \label{sec:Le-diagram}

In this section we characterize the \reflectbox{L}-diagrams corresponding to rational Dyck positroids.

\begin{definition}
	Let $d$ and $m$ be positive integers, and let $Y_\lambda$ be the Young diagram associated to a given partition $\lambda$ contained in a $d \times m$ rectangle. A \emph{\reflectbox{\emph{L}}-diagram} (or \emph{Le-diagram}) $L$ of shape $\lambda$ and type $(d,d+m)$ is obtained by filling the boxes of $Y_\lambda$ with zeros and pluses so that no zero entry has simultaneously a plus entry above it in the same column and a plus entry to its left in the same row.
\end{definition}

With notation as in the above definition, the southeast border of $Y_\lambda$ determines a path of length $d+m$ from the northeast to the southwest corner of the $d \times m$ rectangle; we call such a path the \emph{boundary path} of $L$.

There is a natural bijection $\Phi \colon L \mapsto \pi$ from the set of \reflectbox{L}-diagrams of type $(d,d+m)$ to the set of decorated permutations on $[d+m]$ having exactly $d$ excedances (see \cite[Section~20]{aP06}).

\begin{example} \label{ex:Le-diagram}
	Figure~\ref{fig:Le-diagram} shows a \reflectbox{L}-diagram $L$ of type $(5,12)$ with its boundary path highlighted. The decorated permutation $\Phi(L)$ is $(1 \ 1\!2 \ 9 \ 2)(3 \ 1\!0 \ 1\!1 \ 7)(4 \ 5)(6 \ 8)$.
	\begin{figure}[h]
		\centering
		\includegraphics[width = 5.0cm]{images/LeDiagramGeneralWithPath.png}
		\caption{A Le-diagram of type $(5,12)$ and shape $\lambda = (7,6,6,5,2)$.}
		\label{fig:Le-diagram}
	\end{figure}
\end{example}

Let $\lambda$ be a partition, and let $Y_\lambda$ be the Young diagram with shape $\lambda$. A \emph{pipe dream} of shape $\lambda$ is a tiling of $Y_\lambda$ by elbow joints $\,\raisebox{-0.1 \height}{\includegraphics[width=0.5cm]{images/LeDiagramElbow.png}}$ and crosses $\,\raisebox{-0.1 \height}{\includegraphics[width=0.5cm]{images/LeDiagramPlus.png}}$. Here is a method (see Figure~\ref{fig:Le-diagram and pipe diagram}) to decode the decorated permutation $\pi = \Phi(L)$ from its \reflectbox{L}-diagram $L$.

\begin{lemma}[{\cite[Lemma~4.8]{ARW16}}] \label{lem:decorated permutation from Le-diagram}
	Let $L$ be the \reflectbox{\emph{L}}-diagram corresponding to a rank $d$ positroid $P$ on $[d+m]$. We can compute the decorated permutation $\pi$ of $P$ as follows.
	\begin{enumerate}
		\item Replace the pluses in $L$ with elbow joints $\,\raisebox{-0.1 \height}{\includegraphics[width=0.5cm]{images/LeDiagramElbow.png}}$ and the zeros in $L$ with crosses $\,\raisebox{-0.1 \height}{\includegraphics[width=0.5cm]{images/LeDiagramPlus.png}}$ to obtain a pipe dream.
		\item Label the steps of the boundary path with $1, \dots, d+m$ in southwest direction, and then label the edges of the north and west border of $Y_\lambda$ also with $1,\dots, d+m$ in such a way that labels of opposite border steps coincide.
		\item Set $\pi(i) = j$ if the pipe starting at the step labeled by $i$ in the northwest border ends at the step labeled by $j$ in the boundary path. If $\pi$ fixes $j$ write $\pi(j) = \underline{j}$ (resp., $\pi(j) = \overline{j}$) if $j$ labels a horizontal (resp., vertical) step of the boundary path.
	\end{enumerate}
\end{lemma}

If we label the steps of the boundary path of $L$ in southwest direction, then $i \in [d+m]$ labels a vertical step if and only if $i$ is a weak excedance of $\pi$ (see \cite[Lemma~5]{SW07}). By Theorem~\ref{thm:decorated permutation of rational Dyck positroids}, the \reflectbox{L}-diagram of a rational Dyck positroid is rectangular.

\begin{prop} \label{prop:Le-Diagrams of rational Dyck positroids}
	A \reflectbox{\emph{L}}-diagram $L$ of type $(d,d+m)$ corresponds to a rank $d$ rational Dyck positroid on the ground set $[d+m]$ if and only if its shape $\lambda$ is the full $d \times m$ rectangle and $L$ satisfies the following two conditions:
	\begin{enumerate}
		\item every column has exactly on plus except the last one that has $d$ pluses;
		\vspace{3pt}
		\item the horizontal unit steps right below the bottom-most plus of each column are the horizontal steps of a horizontally-reflected rational Dyck path of type $(m,d)$ (see Figure~\ref{fig:Le-diagram and pipe diagram}).
	\end{enumerate}
\end{prop}

\begin{example}
	Let $P$ be the rank $5$ rational Dyck positroid on $[13]$ with decorated permutation $(1 \ 2 \ 1\!3 \ 1\!2 \ 3 \ 1\!1 \ 1\!0 \ 4 \ 9 \ 5 \ 8 \ 7 \ 6)$. Figure~\ref{fig:Le-diagram and pipe diagram} shows the \reflectbox{L}-diagram corresponding to $P$ along with its associated pipe dream, illustrating the recipe described in Lemma~\ref{lem:decorated permutation from Le-diagram}.
	
	\begin{figure}[h]
		\centering
		\raisebox{0.13 \height}{\includegraphics[width = 5.5cm]{images/LeDiagram.png}} \hspace{2cm}
		\includegraphics[width = 5.8cm]{images/PermutationFromLeDiagram.png}
		\caption{Le-diagram of $P$ on the left and pipe dream giving rise to $\pi$ on the right.}
		\label{fig:Le-diagram and pipe diagram}
	\end{figure}
	
\end{example}

For $d \le n$, the \emph{real Grassmannian} $\text{Gr}_{d,n}$ is the set of $d$-dimensional subspaces of $\rr^n$. We can think of $\text{Gr}_{d,n}$ as the quotient of the set comprising all full-rank $d \times n$ real matrices under the left action of $\text{GL}_d(\rr)$. For $[A] \in \text{Gr}_{d,n}$, let $M_{[A]}$ denote the rank $d$ matroid represented by $A$ (it can be easily argued that $M_{[A]}$ does not depend on the matrix $A$ representing $[A]$). Every rank $d$ representable matroid $M$ determines a \emph{matroid stratum} $S_M := \{[A] \in \text{Gr}_{d,n} \mid M_A = M \}$. The \emph{totally nonnegative Grassmannian} is defined by
\[
	(\text{Gr}_{d,n})_{\ge 0} := \text{GL}^+_d(\rr) \! \setminus \! \text{Mat}^+_{d,n}(\rr),
\]
where $\text{GL}_d^+(\rr)$ is the set of all $d \times d$ real matrices having positive determinant. Each rank $d$ positroid $P$ on the ground set $[n]$ determines a \emph{positroid cell} $S^+_P = S_P \cap (\text{Gr}_{d,n})_{\ge 0}$ inside $(\text{Gr}_{d,n})_{\ge 0}$. Positroid cells are, therefore, naturally indexed by \reflectbox{L}-diagrams. It is well known that the number of pluses inside each indexing \reflectbox{L}-diagram equals the dimension of its positroid cell (see \cite{gL98} and \cite{aP06}). The next corollary follows from Proposition~\ref{prop:Le-Diagrams of rational Dyck positroids}.

\begin{cor}
	The positroid cell parameterized by a rank $d$ rational Dyck positroid on the ground set $[d+m]$ inside the corresponding Grassmannian cell complex has dimension $d+m-1$.
\end{cor}

\section{Plabic Graphs} \label{sec:plabic graph}

In this section we study the move-equivalence classes of plabic graphs (up to homotopy) corresponding to rational Dyck positroids.

\begin{definition}
	A \emph{plabic graph} is an undirected graph $G$ drawn inside a disk $D$ (up to homotopy) which has a finite number of vertices on the boundary of $D$. Each of the remaining vertices of $G$ is strictly inside the disk and colored either black or white. Each vertex on the boundary of $D$ is incident to exactly one edge.
\end{definition}

The vertices in the interior of $D$ are called \emph{internal vertices}, while the vertices on the boundary of $D$ are called \emph{boundary vertices}. Here we always label the boundary vertices of $G$ clockwise starting by $1$. Also, all the plabic graphs in this paper are assumed to be \emph{leafless} (there are no internal vertices of degree one) and without isolated components. For the rest of this section, let $G$ denote a plabic graph with $n$ boundary vertices.

A \emph{perfect orientation} $\mathcal{O}$ of $G$ is a choice of directions for every edge of $G$ in such a way that black vertices have outdegree one and white vertices have indegree one. If $G$ admits a perfect orientation $\mathcal{O}$, we call $G$ \emph{perfectly orientable} and let $G_{\mathcal{O}}$ denote the directed graph on $G$ determined by $\mathcal{O}$. %A boundary vertex $v$ of an oriented plabic graph $G_{\mathcal{O}}$ is a \emph{source} (resp., \emph{sink}) if $v$ has indegree (resp., outdegree) zero.
The set of boundary vertices that are sources (resp., sinks) of $G_{\mathcal{O}}$ is denoted by $I_{\mathcal{O}}$ (resp., $\bar{I}_{\mathcal{O}}$). It is known that
\begin{equation*}
	|I_{\mathcal{O}}| := d := \frac 12 \bigg(n + \sum_{v \text{ black}} \big(\deg(v) - 2\big) + \sum_{v \text{ white}}\big(2 - \deg(v)\big)\bigg)
\end{equation*}
for any perfect orientation of $G$ (see~\cite{aP06} for details). The \emph{type} of $G$ is defined to be $(d,n)$.

The next moves partition the set of plabic graphs into equivalence classes. %We will see that this set of equivalence classes is in bijection with the set of positroids.

(M1) {\bf Square move:} If $G$ has a square consisting of four trivalent vertices whose colors alternate, then the colors of these four vertices can be simultaneously switched.
\begin{figure}[h]
	\centering
	\includegraphics[width = 5.5cm]{images/M1.png}
\end{figure}

(M2) {\bf Unicolored edge contraction/uncontraction:} If $G$ contains two adjacent vertices of the same color, then the edge joining these two vertices can be contracted into a single vertex with the same color of the two initial vertices. Conversely, a given vertex of $G$ can be uncontracted into an edge joining vertices of the same color as the given vertex.
\begin{figure}[h]
	\centering
	\includegraphics[width = 5.6cm]{images/M2.png}
\end{figure}

(M3) {\bf Middle vertex insertion/removal:} If $G$ contains a vertex of degree $2$, then this vertex can be removed and its incident edges can be glued together. Conversely, a vertex (of any color) can be inserted in the middle of any edge of $G$.
\begin{figure}[h]
	\centering
	\hspace{0.2cm} \includegraphics[width = 6cm]{images/M3.png}
\end{figure}

(R1) {\bf Parallel edge reduction:} If $G$ contains two trivalent vertices of different colors connected by a pair of parallel edges, then these vertices and edges can be deleted, and the remaining two edges can be glued together.
\begin{figure}[h]
	\centering
	\includegraphics[width = 6.5cm]{images/R1.png}
\end{figure}
\newpage

Two plabic graphs are \emph{move-equivalent} if they can be obtained from each other by applying (M1), (M2), and (M3). A leafless plabic graph without isolated components is said to be \emph{reduced} if (R1) cannot be applied to any member of its move-equivalence class.

We define $\pi_G$ by setting $\pi_G(i) = j$ if there is a path in $G$ from the boundary vertex $i$ to the boundary vertex $j$ that turns left (resp., right) at any internal black (resp., white) vertex. If $i$ is fixed by $\pi_G$, then we mark $i$ clockwise (resp., counterclockwise) whenever the internal vertex of $G$ adjacent to $i$ is black (resp., white). For a plabic graph $G$, the trip $\pi_G$ described above is called the \emph{decorated trip permutation} of $G$.

\begin{theorem}[{\cite[Theorem~13.4]{aP06}}]
	Two reduced plabic graphs are move-equivalent if and only if they have the same decorated trip permutation.
\end{theorem}

%Plabic graphs of type $(d,n)$ also parameterize rank $d$ positroids on the ground set $[n]$.

\begin{prop}[{\cite[Section~11]{aP06}}]
	For each pair of positive integers $d$ and $n$ with $d \le n$ the assignment $G \mapsto P_G = ([n], \mathcal{B}_G)$, where
	\[
		\mathcal{B}_G = \{I_{\mathcal{O}} \mid \mathcal{O} \ \text{is a perfect orientation of} \ G\},
	\]
	is a one-to-one correspondence between move-equivalence classes of perfectly orientable plabic graphs of type $(d,n)$ and rank $d$ positroids on the ground set $[n]$.
\end{prop}

\begin{example}
	Let $P$ be the rank $5$ positroid on the ground set $[12]$ with decorated permutation $\pi = (1 \ 1\!2 \ 9 \ 2)(3 \ 1\!0 \ 1\!1 \ 7)(4 \ 5)(6 \ 8)$. Figure~\ref{fig:plabic graph} shows an oriented plabic graph $G_{\mathcal{O}}$ of $P$. The perfect orientation $\mathcal{O}$ gives the basis $I_{\mathcal{O}} = \{1,5,6,8,10\}$ of $P$. In particular, $\pi(3) = 10$, as the highlighted directed path from $3$ to $10$ indicates. %; observe that such a path follows the rules of the road.
	\begin{figure}[h]
		\centering
		\includegraphics[width = 4.7cm]{images/PlabicGraphGeneral.png}
		\caption{A plabic graph with a perfect orientation.}
		\label{fig:plabic graph}
	\end{figure}
\end{example}

Now we characterize the plabic graphs corresponding to rational Dyck positroids.

\begin{prop} \label{prop:the plabic graph of a rational Dyck positroid}
	A rational Dyck path $\mathsf{d}$ of type $(m,d)$ induces a reduced plabic graph $G_{\mathsf{d}}$ of type $(d,d+m)$ as follows:
	\begin{enumerate}
		\item Draw a circle with $(0,0)$ and $(m,d)$ diametrically opposed, and draw a black (resp., white) vertex in the middle of each vertical (resp., horizontal) step of $\mathsf{d}$.
		\item Draw a horizontal segment from each black vertex to the circle (going east) and label the intersections by $1, \dots, d$ (clockwise). Similarly, draw a vertical segment from each white vertex to the circle (going north) and label the intersections by $d+1, \dots, d+m$ (clockwise).
		\item Finally, join consecutive internal vertices in $\mathsf{d}$ by segments and ignore the initial rational Dyck path $\mathsf{d}$ (see Figure~\ref{fig:plabic graph of a rational Dyck positroid and its reduced representative.}).
	\end{enumerate}
\end{prop}

\begin{theorem} \label{thm:main theorem on plabic graphs}
	A rank $d$ positroid on the ground set $[d+m]$ is a rational Dyck positroid if and only if it can be represented by one of the plabic graphs $G_\mathsf{d}$ described in Proposition~\ref{prop:the plabic graph of a rational Dyck positroid}.
\end{theorem}

\begin{example} \label{ex:reducing RD plabic graph to the smallest bipartite}
	Let $P$ be the positroid induced by the rational Dyck path in Figure~\ref{fig:rational Dyck path}. Figure~\ref{fig:plabic graph of a rational Dyck positroid and its reduced representative.} shows the plabic graph $G_{\mathsf{d}}$ corresponding to $P$ described in Proposition~\ref{prop:the plabic graph of a rational Dyck positroid} (on the left) and a minimal bipartite graph in the move-equivalence class of $G_{\mathsf{d}}$ (on the right). 
	\begin{figure}[h]
		\centering
		\includegraphics[width = 4.7cm]{images/PlabicGraph.png} \hspace{1.6cm}
		\includegraphics[width = 4.7cm]{images/PlabicGraphBipartite.png}
		\caption{Plabic graphs of a rank $5$ rational Dyck positroid on the ground set $[13]$.}
		\label{fig:plabic graph of a rational Dyck positroid and its reduced representative.}
	\end{figure}
\end{example}

\section{The Positroid Polytope} \label{sec:positroid polytope}

Matroid polytopes have been extensively studied (see~\cite{ABD10} and references therein). In this section we characterize the matroid polytope of a rational Dyck positroid.

The \emph{indicator vector} of a subset $B$ of $[n]$ is defined to be $e_B := \sum_{j \in B} e_j$, where $e_1, \dots, e_n$ are the standard basic vectors of $\rr^n$. Also, $\text{conv} (S)$ denotes the convex hull of $S \subseteq \rr$.

\begin{definition}
	The \emph{matroid polytope} $\Gamma_M$ of the matroid $M = ([n], \mathcal{B})$ is defined to be $\Gamma_M = \text{conv}\big(\{e_B \mid B \in \mathcal{B}\}\big)$. When $M$ is a positroid, we call $\Gamma_M$ the \emph{positroid polytope} of~$M$.
\end{definition}

\begin{theorem}[{\cite[Theorem~4.1]{GGMS87}}]
	Let $\mathcal{B}$ be a collection of subsets of $[n]$, and let $\Gamma_{\mathcal{B}}$ denote $\emph{conv}\big(\{e_B \mid B \in \mathcal{B}\}\big) \subset \rr^n$. Then $\mathcal{B}$ is the collection of bases of a matroid if and only if every edge of $\Gamma_{\mathcal{B}}$ is a parallel translate of $e_i - e_j$ for some $i, j \in [n]$.
\end{theorem}

The positroid polytope can be described using $O(n^2)$ inequalities.

\begin{prop}[{\cite[Proposition~5.5]{ARW16}}] \label{prop:positroid polytope}
	Let $\mathcal{I} = (I_1, \dots, I_n)$ be a Grassmann necklace of type $(d,n)$, and let $M$ be its corresponding positroid. For any $j \in [n]$, suppose that the elements of $I_j$ are $a_1^j \le_j  \dots \le_j a_d^j$. Then the positroid polytope $\Gamma_M$ can be described by the inequalities
	\begin{align*}
		x_1 + x_2 + \dots + x_n &= d, \hspace{1cm}& \\
		x_j &\ge 0 &\text{for each} \ j \in [n], \\
		x_j + x_{j+1} + \dots + x_{a_k^j - 1} &\le k-1 &\text{for each} \ j \in [n] \ \text{and} \ k \in [d],
	\end{align*}
	where all the subindices are taken modulo $n$.
\end{prop}

Let $D$ be a $d \times m$ rational Dyck matrix, and set $A = (a_{i,j}) = \phi_{d,m}(D)$. Then we define the \emph{set of principal indices} $I_A$ of $A$ to be $I_A = \{i \in \{d+1, \dots, d+m\} \mid A_i \neq A_{i-1}\}$, where $A_i$ denotes the $i$-th column of $A$. We conclude this paper refining Proposition~\ref{prop:positroid polytope} for rational Dyck positroids.

\begin{prop} \label{prop:rational Dyck positroid polytope}
	Let $P$ be a rational Dyck positroid represented by the real $d \times (d+m)$ matrix $A \in \phi_{d,m}(\mathcal{D}_{d,m})$, and let $I_A = \{p_1 < \dots < p_t\}$ be the set of principal indices of $A$. Then the positroid polytope $\Gamma_P$ is described by the inequalities
	\begin{align*}
		x_1 + \dots + x_{d+m}              &= d,		& \\
		x_i     									  &\ge 0	  &\text{for} \ i \in [d+m], \\
		x_i 		     							  &\le 1        &\text{for} \ i \in [d], \\
		x_{p_i} + \dots + x_{p_{i+1}-1}  &\le 1        &\text{for} \ i \in [t], \\
		x_i + \dots + x_{p_{m(i)} - 1} 	  &\le (d-i)+ m(i) &\text{for} \ i \in [d], \\
		x_{p_i} + \dots + x_{\omega_A(p_i)} & \le \omega_A(p_i)   &\text{ for} \ i \in [t] \! \setminus \! \{1\},%\ \text{ and } \ s = \min\{r \in [d] \mid \omega_A(p_i) > r\}
	\end{align*}
	where $m(i) = \max\{r \in [t] \mid \omega_A(p_r) \ge i \ \text{and} \ r < i\}$.
\end{prop}

\begin{remark}
	Although the description of the rational Dyck positroid in Proposition~\ref{prop:rational Dyck positroid polytope} is not as simple as the one in Proposition~\ref{prop:positroid polytope}, the reader should observe that the number of inequalities in Proposition~\ref{prop:rational Dyck positroid polytope} is $O(d+m)$ while in Proposition~\ref{prop:positroid polytope} is $O(d^2 + dm)$.
\end{remark}

\acknowledgements{I want to thank Bruno Benedetti and Maria Gillespie for suggesting me to look at the connection between rational Dyck paths and positroids, and my advisor, Lauren Williams, for many helpful conversations and for encouraging me to work on this project.}

\printbibliography

\end{document}
