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

\articlenumber{43}
\addbibresource{43.bib}

\usepackage{amsfonts}
%\usepackage[margin=1in]{geometry}
%\usepackage{setspace}
%\usepackage{graphicx}
\usepackage{mathtools}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

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

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}
\newcommand{\newword}[1]{\textbf{\emph{#1}}}
\newtheorem{problem}{Problem}
\def\Z{\mathcal{Z}}
\def\C{\mathcal{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}

\DeclarePairedDelimiter\parentheses{\lparen}{\rparen}
\newcommand{\rk}[1]{\operatorname{rk} \parentheses*{#1}}
\newcommand{\nbd}[1]{\operatorname{nbd} \parentheses*{#1}}
\newcommand{\minn}[1]{\operatorname{min} \parentheses*{#1}}
\newcommand{\maxx}[1]{\operatorname{max} \parentheses*{#1}}
\newcommand{\cw}[1]{\operatorname{cw} \parentheses*{#1}}
\newcommand{\ccw}[1]{\operatorname{ccw} \parentheses*{#1}}
\newcommand{\minelts}[1]{\operatorname{minelts} \parentheses*{#1}}

\usepackage{lipsum}

%% define your title in the usual way
\title[Flats of a positroid]{Flats of a positroid from its decorated permutation}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Robert Mcalmon, Suho Oh, \and David Xiang}

%% then use \addressmark to match authors to institutions here
\address{Department of Mathematics, Texas State University, USA\\}

%% 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{A positroid is a special case of a realizable matroid, that arose from the study of totally nonnegative part of the Grassmannian by Postnikov. Postnikov demonstrated that positroids are in bijection with certain interesting classes of combinatorial objects, such as Grassmann necklaces and decorated permutations. The bases of a positroid can be described directly in terms of the Grassmann necklace and decorated permutation. In this extended abstract, we show how to describe the flats, bases and independent sets directly from the decorated permutation, bypassing the use of the Grassmann necklace.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Positroids, flats, bases, flacets, permutation, matroids, non-crossing partitions}

%% 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]{biblatex}
%\addbibresource{bibliography.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

%\allowdisplaybreaks

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above


\section{Introduction}


A matrix is totally positive (respectively totally nonnegative) if all its minors are positive (respectively nonnegative) real numbers. These matrices have a number of remarkable properties: for example, an $n \times n$ totally positive matrix has $n$ distinct positive eigenvalues. The space of these matrices can be grouped up into topological cells, with each cell completely parametrized by a certain planar network \cite{fomin}. The idea of total positivity found numerous applications and was studied from many different angles, including oscillations in mechanical systems, stochastic processes and approximation theory, and planar resistor networks \cite{fomin}.

Now, instead of considering $n \times n$ matrices with nonnegative minors, consider a full-rank $k \times n$ matrix with all maximal minors nonnegative. This arose from the study of the totally nonnegative part of the Grassmannian by Postnikov \cite{Postnikov}. The set of nonzero maximal minors of such matrices forms a positroid, which is a matroid used to encode the topological cells inside the nonnegative part of the Grassmannian. Positroids have a number of nice combinatorial properties. In particular, Postnikov demonstrated that positroids are in bijection with certain interesting classes of combinatorial objects, such as Grassmann necklaces and decorated permutations. Recently, positroids have seen increased applications in physics, with use in the study of scattering amplitudes \cite{arkani} and the study of shallow water waves \cite{kodama}.

The set of bases of a positroid can be described nicely from the Grassmann necklace \cite{Oh}, and the polytope coming from the bases can be described using the cyclic intervals \cite{LP,ARW}. Non-crossing partitions were used to construct positroids from their connected components in \cite{ARW}. They were also used in \cite{EP} as an analogue of the bases for electroids. In this extended abstract, we go over the result in \cite{OM} providing yet another usage of cyclic intervals and non-crossing partition for positroids.

Given an arbitrary set, the rank (the size of the biggest intersection with a basis) can be obtained by going through all the bases. In this extended abstract, we show a method of obtaining the rank of an arbitrary set directly from the associated decorated permutation without having to go through the bases. In particular, we get a collection of upper bounds of the rank coming from non-crossing partitions, and one of them will be shown to be tight. 

Using that result, we can describe the bases without relying on the Grassmann necklace. We also describe the facets of the independent set polytope (the inseparable flats) of the positroid, using the decorated permutation. This gives a way to describe all the independents sets, again without relying on the Grassmann necklace.

This is an extended abstract, combining the results of \cite{OM} and \cite{OX}. The structure of the extended abstract is as follows. In \cref{sec:background materials}, we go over the background materials needed for this paper, including the basics of matroids, positroids, Grassmann necklaces and decorated permutations. In \cref{sec:computing the rank}, we show that the rank of an arbitrary set in a positroid can be obtained directly from the decorated permutation by using non-crossing partitions. In \cref{sec:flats from the} we state our main result.


%\section*{Acknowledgement}
%The authors would also like to thank Lillian Bu, Wini Taylor-Williams and David Xiang for useful discussions.



\section{Background materials}\label{sec:background materials}

\subsection{Matroids}

In this section we review the basics of matroids that we will need. We refer the reader to \cite{Oxley} for a more in-depth introduction to matroid theory.

\begin{definition}
A \newword{matroid} is a pair $(E,\B)$ consisting of a finite set $E$, called the \newword{ground set} of the matroid, and a nonempty collection of subsets $\B = \B(\M)$ of $E$, called the \newword{bases} of $\M$, which satisfy the \newword{basis exchange axiom}:

If $B_1,B_2 \in \B$ and $b_1 \in B_1 \setminus B_2$, then there exists $b_2 \in B_2 \setminus B_1$ such that $B_1 \setminus \{b_1\} \union \{b_2\} \in \B$. 
\end{definition}

A subset $F \subseteq E$ is called \newword{independent} if it is contained in some basis. All maximal independent sets contained in a given set $A \subseteq E$ have the same size, called the \newword{rank} $\rk{A}$ of $A$. The rank of the matroid $\M$, denoted as $\rk{\M}$, is given by $\rk{E}$. A set $E$ is called \newword{separable} in a matroid if one can partition $E$ into $E_1$ and $E_2$ such that $\rk{E} = \rk{E_1} + \rk{E_2}$.


An element $e \in E$ is a \newword{loop} if it is not contained in any basis. An element $e \in E$ is a \newword{coloop} if it is contained in all bases. A matroid $\M$ is \newword{loopless} if it does not contain any loops. The \newword{dual} of $\M$ is a matroid $\M^{*} = (E,\B')$ where $\B' = \{E \setminus B | B \in \B(\M)\}$. By using the basis exchange axiom on the dual matroid, we get the following \newword{dual basis exchange axiom}:

If $B_1,B_2 \in \B$ and $b_2 \in B_2 \setminus B_1$, then there exists $b_1 \in B_1 \setminus B_2$ such that $B_1 \setminus \{b_1\} \union \{b_2\} \in \B$. 

\begin{remark}
In this paper, we will always use $[n] := \{1,\ldots,n\}$ as our ground set, reserving the usage of $E$ for subsets of the ground set we analyze. A matroid of rank $d$ will have bases in the set ${[n] \choose d}$ which stands for all cardinality $d$-subsets of $[n]$.
\end{remark}

Let $E$ be an arbitrary subset of the ground set $[n]$. For a basis $J$, if $|J \intersect E|$ is maximal among $|B \intersect E|$ for all bases $B$ of the matroid $\M$, we say that $J$ \newword{maximizes} $E$, or $J$ is \newword{maximal} in $E$. Similarly, if $|J \intersect E|$ is minimal among $|B \intersect E|$ for all bases $B$ of $\M$, we say that $J$ \newword{minimizes} $E$, or $J$ is \newword{minimal} in $E$.


The following property of the rank function will be crucial:

\begin{theorem} \cite{Oxley}
The rank function is \textit{semimodular}, meaning that $\rk{A\cup B}+\rk{A\cap B}\leq \rk{A}+\rk{B}$ for any subset $A$ and $B$ of the ground set.
\end{theorem}


Consider a matrix with entries in $\RR$ that has $n$ columns and $r$ rows, with $r \leq n$. Column sets that forms a $r$-by-$r$ submatrix with nonzero determinant forms (the set of bases of) a matroid. Such matroids are called \newword{realizable} matroids. For example, consider the following matrix:
\[ A = \left( \begin{array}{cccc}
1 & 0 & -3 & -1 \\
0 & 1 & 4 & 0\\
\end{array} \right)\] 

The column sets $\{1,2\}, \{1,3\},\{2,3\},\{2,4\},\{3,4\}$ give two-by-two submatrices that has nonzero determinant. So the collection $\{\{1,2\}, \{1,3\},\{2,3\},\{2,4\},\{3,4\}\}$ is a realizable matroid.

%\begin{proposition}
%\label{prop:exch}
%Let $\M$ be a realizable matroid over the ground set $[n]$, and let $B$ be a basis of $\M$. Pick an arbitrary subset $E$ of $[n]$ such that $B$ maximizes $E$ and some $J \subseteq E$ such that $|J|= \rk{J} = \rk{E}$. Then $B \setminus (B \intersect E) \union J$ is another basis of $\M$.
%\end{proposition}
%\begin{proof}
%From the condition $|J| = \rk{J} = \rk{E}$, the span of the vectors indexed by the set $J$ is exactly same as the span of the vectors indexed by the set $E$. Since $B$ maximizes $E$, the span of the vectors indexed by the set $B \intersect E$ is the same vector space. Hence starting from a set of basis vectors indexed by the set $B$, if we replace the set of vectors indexed by $B \intersect E$ with the set of vectors indexed by $J$, we still get a set of basis vectors.
%\end{proof}




We now go over polytopes related to matroids.

\begin{definition}
Given a matroid $\M = ([n],\B)$, the (basis) matroid polytope $\Gamma_{\M}$ of $\M$ is the convex hull of the indicator vectors of the bases of $\M$:
$$\Gamma_{\M} = convex\{e_B|B \in \B\} \subset \RR^n,$$
where $e_B := \sum_{i \in B} e_i$ and $\{e_1,\ldots,e_n\}$ is the standard basis of $\RR^n$.
\end{definition}

\begin{definition}
Given a matroid $\M = ([n],\B)$, the independent set polytope $P_{\M}$ of $\M$ is the convex hull of the indicator vectors of the independent sets of $\M$:
$$P_{\M} = convex\{e_I|I \subset B \in \B\} \subset \RR^n,$$
where $e_I := \sum_{i \in I} e_i$ and $\{e_1,\ldots,e_n\}$ is the standard basis of $\RR^n$.
\end{definition}


There is a nice description for the facets of these polytopes.

\begin{theorem}[Proposition 2.6. of \cite{Feichtner2005}]
\label{thm:matpoly}
The following is a minimal system for the matroid polytope of $\M$:
\begin{itemize}
\item $x_e \geq 0$, $e \in E$,
\item $x_F := \sum_{e \in F} x_e \leq \rk{F}$, $F$ is a \newword{flacet} : $F$ is a flat of $\M$ where $F$ is inseparable in $\M$ and $F^c$ is inseparable in the dual of $\M$.
\end{itemize}
\end{theorem}

\begin{theorem}[Theorem 40.5. of \cite{Schrijver}]
\label{thm:indpoly}
If $\M$ is loopless, the following is a minimal system for the independent set polytope of $\M$:
\begin{itemize}
\item $x_e \geq 0$, $e \in E$,
\item $x_F := \sum_{e \in F} x_e \leq \rk{F}$, $F$ is a nonempty inseparable flat of $\M$,
\end{itemize}
\end{theorem}

We will show a method from \cite{OX} to read off $F$'s and their ranks for both of those polytopes for positroids, directly from the associated decorated permutation.




\subsection{Positroids}

In this section we go over the basics of positroids. Positroids were originally defined in \cite{Postnikov} as the column sets coming from nonzero maximal minors in a matrix such that all maximal minors are nonnegative. For example, the matrix we saw in the previous section has nonnegative maximal minors:
\[ A = \left( \begin{array}{cccc}
1 & 0 & -3 & -1 \\
0 & 1 & 4 & 0\\
\end{array} \right)\] 

The nonzero maximal minors come from column sets $\{1,2\}, \{1,3\},\{2,3\},\{2,4\},\{3,4\}$. This collection forms a positroid. However in this paper, we will use an equivalent definition using Grassmann necklace and Gale orderings.

\begin{definition}
Let $d \leq n$ be positive integers. A \newword{Grassmann necklace} of type $(d,n)$ is a sequence $(I_1,\ldots,I_n)$ of $d$-subsets $I_k \in {[n] \choose d}$ such that for any $i \in [n]$,
\begin{itemize}
\item if $i \in I_i$ then $I_{i+1} = I_i \setminus \{i\} \union \{j\}$ for some $j \in [n]$,
\item if $i \not \in I_i$ then $I_{i+1} = I_i$,
\end{itemize}
where $I_{n+1} = I_1$. 
\end{definition}

The \newword{cyclically shifted order} $<_i$ on the set $[n]$ is the total order
$$i <_i i+1 <_i \cdots <_i n <_i 1 <_i \cdots <_i i-1. $$

For any rank $d$ matroid $\M$ with ground set $[n]$, let $I_k$ be the lexicographically minimal basis of $\M$ with respect to $<_k$, and denote
$$\I(\M) := (I_1,\ldots,I_n),$$
which forms a Grassmann necklace \cite{Postnikov}.

The \newword{Gale order} on ${[n] \choose d}$ (with respect to $<_i$) is the partial order $<_i$ defined as follows: for any two $d$-subsets $S = \{s_1 <_i \cdots <_i s_d\}$ and $T = \{t_1 <_i \cdots <_i t_d\}$ of $[n]$, we have $S \leq_i T$ if and only if $s_j \leq_i t_j$ for all $j \in [d]$ \cite{Gale}.


\begin{theorem}[\cite{Postnikov},\cite{Oh}]
\label{thm:oh}
Let $\I = (I_1,\ldots,I_n)$ be a Grassmann necklace of type $(d,n)$. Then the collection
$$\B(\I) := \{B \in {[n] \choose d} | B \geq_j I_j, \text{ for all } j \in [n] \}$$
is the collection of bases of a rank $d$ positroid $\M(\I) := ([n],\B(\I))$. Moreover, for any positroid $\M$, we have $\M(\I(\M)) = \M$. 
\end{theorem}

In order to check if a set is a basis of a positroid or not, we do not have to check for all the cyclic orderings.

\begin{corollary}
\label{cor:selected}
Let $\M \subseteq {[n] \choose d}$ be a positroid and $\I$ the associated Grassmann necklace. A set $B \in {[n] \choose d}$ is a basis of $\M$ if and only if $B \geq_b I_b$ for all $b \in B$.
\end{corollary}
\begin{proof}
For arbitrary $q \in [n]$, denote the elements of $B$ as $b_1 <_q b_2 <_q \cdots <_q b_d$. If we had $B \geq_{b_1} I_{b_1}$, we would also have $B \geq_q I_{b_1} \geq_q I_q$.
\end{proof}


%It is worth noting that the class of positroids is closed under taking restriction, contraction and the dual \cite{ARW}. 

\begin{definition}
A \newword{decorated permutation} of the set $[n]$ is a bijection $\pi$ of $[n]$ whose fixed points are colored either white or black. A \newword{weak $i$-exceedance} of a decorated permutation $\pi$ is an element $j \in [n]$ such that either $j <_i \pi^{-1}(j)$ or $j$ is a fixed point colored black. 
\end{definition}

Given a decorated permutation $\pi$ of $[n]$ we can construct a Grassmann necklace $\I = (I_1,\ldots,I_n)$ by letting $I_k$ be the set of weak $k$-exceedances of $\pi$. A graphical way to see this is to cut the circle off between $k-1$ and $k$ to get a horizontal straight line with leftmost endpoint being $k$ and rightmost endpoint being $k-1$. Redraw the arrows of the permutation accordingly so that it stays within the line. Endpoints of the leftward arrows are exactly the weak $k$-exceedances of $\pi$, hence the elements of $I_k$. There is a bijection between Grassmann necklaces and decorated permutations \cite{Postnikov}.


\begin{figure}
\begin{center}
\includegraphics[scale = 0.7]{permutation.pdf}


    \caption{A decorated permutation.}
		\label{fig:permutation}

\end{center}
\end{figure}

For example, take a look at the decorated permutation (since it has no fixed points, it is the usual permutation) in \cref{fig:permutation}. It is the permutation $[2,8,6,7,9,4,5,14,13,3,10,$ $11,1,12]$ under the usual bracket notation. The weak $1$-exceedances of the permutation is given by the set $\{1,3,4,5,10,11,12\}$, and this is $I_1$ of the associated Grassmann necklace.



\begin{remark}
When we are dealing with positroids, we will always envision the ground set $[n]$ to be drawn on a circle. We will say that $a_1,\ldots,a_t \in [n]$ are \newword{cyclically ordered} if there exists some $i \in [n]$ such that $a_1 <_i \cdots <_i a_t$.
\end{remark}




Given $a,b \in [n]$, we define the cyclic interval $[a,b]$ to be the set $\{x| x \leq_a b\}$. These cyclic intervals play an important role in the structure of a positroid \cite{Knutson},\cite{LP},\cite{ARW}. All intervals mentioned in this paper will actually be referring to cyclic intervals.

\begin{remark}
\label{rem:nofixed}
If a positroid $\M$ has loops or coloops, it is enough to study the positroid $\M'$ obtained by deleting the loops and the coloops to study the structural properties of $\M$. So throughout this paper, we will assume that our positroid has neither loops nor coloops. This means that the associated decorated permutation has no fixed points.
\end{remark}

\begin{remark}
\label{rem:E}
When $E$ is a subset of the ground set $[n]$ and we are trying to write $E$ as a disjoint union of cyclic intervals so that $E = [a_1,b_1] \union \cdots \union [a_s,b_s]$, we will arrange the $a_i$'s such that $a_1 < a_2 < \cdots < a_s$ unless otherwise stated. The symbol $s$ will always be reserved for the number of disjoint intervals that $E$ has. Here the indices of $[s]$ are considered cyclically, so $a_{s+1}=a_1$.
\end{remark}






\section{Computing the rank using non-crossing partitions}\label{sec:computing the rank}

 We will call an interval of form $[x,\pi(x)]$ a \newword{CW-arrow}, and an interval of form $[x,\pi^{-1}(x)]$ a \newword{CCW-arrow} (each standing for clockwise and counterclockwise). Given a cyclic interval $T$, we use $\cw{T}$ to denote the number of CW-arrows contained in $T$. Similarly, we will use $\ccw{T}$ for the number of CCW-arrows contained in $T$. These numbers can easily be read from the associated decorated permutation of $\M$.

Let $E$ be a subset of the ground set as in \cref{rem:E}. We use $E_i$ to denote $[a_i,b_i]$. The rank of $E$ is bounded above by $\rk{\M}$ minus the sum of the minimal number of elements that a basis of $\M$ can possibly have in each cyclic interval of the complement of $E$. So we get $\rk{E} \leq \rk{\M} - \sum_i \minelts{b_i,a_{i+1}}$. Here $\minelts{b,a}$ is the minimal number of elements that a basis of $\M$ can have in the interval $(b,a)$, which turns out to be same as $\ccw{(b,a)}$.  We call this bound the \newword{natural rank bound of $E$}: $\nbd{E} := \rk{\M} - \sum_i (\ccw{b_i,a_{i+1}})$. 

%Notice that $\minelts{b,a} = \rk{\M} - \rk{[a,b]}$.

\begin{definition}
Let $\Pi$ be a partition $T_1 \sqcup \cdots \sqcup T_p$ of $[s]$ into pairwise disjoint non-empty subsets. We say that $\Pi$ is a \newword{non-crossing partition} if there are no cyclically ordered $a,b,c,d$ such that $a,c \in T_i$ and $b,d \in T_j$ for some $i \not = j$. We will call the $T_i$'s as the \newword{blocks} of the partition.
\end{definition}


To illustrate with a simple example, $\{1,3\}\sqcup\{2\}\sqcup\{4\}$ is a non-crossing partition of $[4]$, but $\{1,3\}\sqcup\{2,4\}$ is not. This can be easily verified by drawing the points $1$ to $4$ on a circle and trying to cut the circle into distinct regions corresponding to the partitions; this can only be done in the case of non-crossing partitions.



Let $\Pi$ be an arbitrary non-crossing partition of $[s]$ with $T_1,\ldots,T_p$ as its parts. We define $E|_{T_i}$ as the subset of $E$ obtained by taking only the intervals indexed by elements of $T_i$. For example, $E|_{\{1,3\}}$ would stand for $E_1 \cup E_3$. By submodularity of the rank function, we get another upper bound on the rank of $E$ : $\rk{E} \leq \rk{E|_{T_1}} + \cdots + \rk{E|_{T_p}} \leq \nbd{E, \Pi} := \nbd{E|_{T_1}} + \cdots + \nbd{E|_{T_p}}$. So for each non-crossing partition of $[s]$, we get an upper bound on the rank of $E$. We show that one of those bounds has to be tight in the theorem below.

\begin{theorem}
\label{thm:rk}
Let $E = [a_1,b_1] \union \cdots \union [a_s,b_s]$ be a disjoint union of $s$ cyclic intervals, where $a_1,b_1,a_2,b_2,\ldots,a_s,b_s$ are cyclically ordered. We have $\rk{E} = \nbd{E,\Pi}$ for some non-crossing partition $\Pi$ of $[s]$.
\end{theorem}



\begin{figure}

\begin{center}
\includegraphics[scale = 0.7]{interval13810rk.pdf}

    \caption{Information needed to compute the rank of $[1,3] \union [8,10]$.}
		\label{fig:interval13810rk}

\end{center}
\end{figure}

For example, take a look at \cref{fig:interval13810rk} (the positroid is the one associated to \cref{fig:permutation}). The rank of $E = [1,3] \union [8,10]$ is bounded above by $\nbd{E, \{\{1\},\{2\}\}}$ and $\nbd{E,\{\{1,2\}\}}$. We get $\nbd{E,\{\{1\},\{2\}\}} = \rk{[1,3]} + \rk{[8,10]} = 2 + 3 = 5$, since rank of an interval $[a,b]$ is given by $|[a,b]| - cw([a,b])$ (from $I_a$ being given by $a$-exceedances, and $\rk{[a,b]} = |I_a \intersect [a,b]|)$. We also have $\nbd{E,\{\{1,2\}\}} = \rk{\M} - \ccw{(3,8)} - \ccw{(10,1)} = 7 - 2 - 2 = 3$. Hence the above theorem tells us that $\rk{E} = 3$.

%since $\minelts{(b,a)}$ is given by the number of intervals of form $[x,\pi^{-1}(x)]$ contained in $(b,a)$. Hence the above theorem tells us that $\rk{E} = 3$.


%Recall that $\nbd{[a_1,b_1] \cup \cdots \cup [a_s,b_s]} = \rk{\M} - \sum_i (\minelts{b_i,a_{i+1}})$. And $\minelts{b_i,a_{i+1}}$ stands for the minimal possible number of elements a basis can have in the interval $(b_i,a_{i+1})$, which equals the number $|I_{a+1} \intersect (b_i,a_{i+1})|$. Hence $\minelts{b_i,a_{i+1}} = \ccw{(b_i,a_{i+1})}$. This gives us another way to interpret $\nbd{E}$ : it is $\rk{\M}$ minus the total number of CCW-arrows contained in the complement of $E$. In the special case when $E$ is a cyclic interval, $\nbd{E}$ is given by $|E|$ minus the number of CW-arrows contained in $E$.

Therefore for any $E$, we can obtain $\nbd{E,\Pi}$ by counting CCW-arrows (and CW-arrows for $E$ that is an interval, which is not needed but is usually faster). If $E$ is the disjoint union of $s$ cyclic intervals, we first write all possible non-crossing partitions of $[s]$. Each one of them gives a sum of $\nbd{E'}$'s where $E'$ obtained from $E$ by taking some of the $s$ cyclic intervals of $E$, and we compute them by counting the CCW-arrows (or CW-arrows for intervals) of the decorated permutation.

Consider the positroid associated with \cref{fig:permutation}. Let us try to compute the rank for $E = [1,2] \union [7,10] \union [13,13]$. We have $3$ disjoint intervals, so the upper bounds of $\rk{E}$ will be coming from the non-crossing partitions of $\{1,2,3\}$. The following are the upper bounds for $\rk{E}$ we get:
%\begin{itemize}
%\item $\nbd{E,\{\{1,2,3\}\}} = \nbd{E} =  \rk{\M} - \ccw{(2,7)} - \ccw{(10,13)} - \ccw{(13,13)} = 7 - 1 - 1 - 0 = 5.$
%\item $\nbd{E,\{\{1\},\{2,3\}\}} = \nbd{E_1} + \nbd{E_2 \union E_3} = |[1,2]| - \cw{[1,2]} + \rk{\M} - \ccw{(10,13)} - \ccw{(13,7)} = 1 + 7 - 1 - 1 = 6.$
%\item $\nbd{E,\{\{1,2\},\{3\}\}} = \nbd{E_1 \union E_2} + \nbd{E_3} = \rk{\M} - \ccw{(2,7)} - \ccw{(10,1)} + |[13,13]| - \cw{(13,13)} = 7 - 1 - 2 + 1 - 0 = 5.$
%\item $\nbd{E,\{\{1,3\},\{2\}\}} = \nbd{E_1 \union E_3} + \nbd{E_2} = \rk{\M} - \ccw{(2,13)} - \ccw{(13,1)} + |[7,10]| - \cw{[7,10]} = 7 - 5 - 0 + 4 - 0 = 6.$
%\item $\nbd{E,\{\{1\},\{2\},\{3\}\}} = \nbd{E_1} + \nbd{E_2} + \nbd{E_3} = |[1,2]| - \cw{[1,2]} + |[7,10]| - \cw{[7,10]} + |[13,13]| - \cw{[13,13]} = 2 - 1 + 4 - 0 + 1 - 0  = 6.$
%\end{itemize}

{\small
\begin{align*}
&\bullet  \nbd{E,\{\{1,2,3\}\}} & &= \nbd{E} \\
& & &= \rk{\M} - \ccw{(2,7)} - \ccw{(10,13)} - \ccw{(13,13)}\\
& & &= 7 - 1 - 1 - 0 = 5 \\
&\bullet \nbd{E,\{\{1\},\{2,3\}\}} & & = \nbd{E_1} + \nbd{E_2 \union E_3} \\
& & &= |[1,2]| - \cw{[1,2]} + \rk{\M} - \ccw{(10,13)} - \ccw{(13,7)} \\
& & &= 1 + 7 - 1 - 1 = 6 \\
&\bullet \nbd{E,\{\{1,2\},\{3\}\}} & &= \nbd{E_1 \union E_2} + \nbd{E_3} \\
& & &= \rk{\M} - \ccw{(2,7)} - \ccw{(10,1)} + |[13,13]| - \cw{(13,13)} \\
& & &= 7 - 1 - 2 + 1 - 0 = 5 \displaybreak \\
&\bullet \nbd{E,\{\{1,3\},\{2\}\}} & &= \nbd{E_1 \union E_3} + \nbd{E_2} \\
& & &= \rk{\M} - \ccw{(2,13)} - \ccw{(13,1)} + |[7,10]| - \cw{[7,10]} \\
& & &= 7 - 5 - 0 + 4 - 0 = 6 \\
&\bullet \nbd{E,\{\{1\},\{2\},\{3\}\}} & &= \nbd{E_1} + \nbd{E_2} + \nbd{E_3} \\
& & &= |[1,2]| - \cw{[1,2]} + |[7,10]| - \cw{[7,10]} + |[13,13]| - \cw{[13,13]} \\
& & &= 2 - 1 + 4 - 0 + 1 - 0  = 6.
\end{align*}
}

\cref{thm:rk} tells us that $\rk{E} = 5$.

%Using Theorem~\ref{thm:rk}, in \cite{OX} it is shown that the facets of the matroid polytope are given by cyclic intervals whose complement is covered by CCW-arrows. It is also shown that the facets of the independent set polytope of a positroid are given by sets whose complement is again covered by CCW-arrows. In \cite{CLOZ}, the condition for an arbitrary subset of the ground set being a flat of the positroid will be given in terms of the decorated permutation, again using Theorem~\ref{thm:rk}.



\section{Flats from the decorated permutation}\label{sec:flats from the}
%In this section, we show how to obtain the interval flats and inseparable flats directly from the decorated permutation.

Using \cref{thm:rk}, we get the following result:
\begin{theorem}[\cite{OX}]
\label{thm:gencover}
Let $\M$ be a loopless positroid with associated decorated permutation $\pi$ and let $E \subseteq [n]$ be an inseparable set. Then $E$ is a flat of $\M$ if and only if each element of $E^c$ is contained in some counter-clockwise arrow of $\pi$ contained in $E^c$. If this happens, we say that \newword{$E^c$ is covered by CCW-arrows}.
\end{theorem}

%\begin{proof}
%Let $E$ be the disjoint union of $s$ cyclic intervals. From the fact that $E$ is inseparable, we have $\rk{E} = \nbd{E} < \nbd{E,\Pi}$ where $\Pi$ is any nontrivial non-crossing partition of $[s]$. Let $x$ be an arbitrary element of $[n] \setminus E$ and set $E'$ to denote $E \union \{x\}$. We can think of $E'$ having $s+1$ cyclic intervals (the interval consisting of the lone element $x$ might be adjacent to another cyclic interval, but it does not matter. Index that lone interval as the $s+1$-th interval). Let $\Pi'$ be an arbitrary non-crossing partition of $[s+1]$ and let $\Pi$ be obtained from $\Pi'$ by deleting the element $s+1$. Then we have $\nbd{E} < \nbd{E,\Pi} \leq \nbd{E',\Pi'}$ for every $\Pi'$ that you don't get a trivial partition of $[s]$ after deleting $s+1$.

%Recall that $E$ is a flat if and only if $\rk{E} < \rk{E' = E \union \{x\}}$ for any $x \in [n] \setminus E$. Since $\M$ is loopless, that automatically implies $\nbd{E} < \nbd{E',\{\{1,\ldots,s\},\{s+1\}\}}$. Hence we have $\rk{E} < \rk{E'}$ if and only if we have $\nbd{E} < \nbd{E',\{\{1,\ldots,s+1\}\}} = \nbd{E'}$. This leads to $\nbd{E} < \nbd{E'}$ if and only if there is a CCW-arrow $[\pi^{-1}(z),z]$ contained in $E^c$ such that $x \in [\pi^{-1}(z),z]$. In order words, $E$ is a flat if and only if $E^c$ is covered by CCW-arrows.
%\end{proof}

In the case $E$ is a cyclic interval, we have $\rk{E} = \nbd{E}$ even when $E$ is separable. So as a corollary, we get:

\begin{theorem}
\label{thm:intervalcover}
Let $\M$ be a loopless positroid and let $E \subseteq [n]$ be a cyclic interval. Then $E$ is a flat of $\M$ if and only if $E^c$ is covered by CCW-arrows.
\end{theorem}

\begin{remark}
Beware that we only care about integers of an interval when we discuss the covering of an interval. For example, if there are two CCW-arrows $[7,9]$ and $[10,11]$, we say that $[7,11]$ is covered by CCW-arrows even if there is no CCW-arrow covering the region between $9$ and $10$.
\end{remark}


\begin{figure}

\begin{center}
\includegraphics[scale = 0.5]{interval110.pdf}
\includegraphics[scale = 0.5]{interval13.pdf}

    \caption{The interval $[1,10]$ is a flat. The interval $[1,3]$ is not.}
		\label{fig:interval110}

\end{center}
\end{figure}


For example, take a look at \cref{fig:interval110}. The complement of the interval $[1,10]$ is covered by CCW-arrows disjoint from $[1,10]$. So this is a flat. On the other hand, the complement of the interval $[1,3]$, the elements $8$ and $9$ in particular, are not covered by CCW-arrows outside $[1,3]$. So $[1,3]$ is not a flat (its closure is $[1,3] \union [8,9]$).

\begin{remark}
The study of cyclic intervals that are flats was motivated from the \newword{essential intervals} studied in \cite{Knutson}. We would like to point out that the set of essential intervals and the set of interval flats are incomparable: there are essential intervals that are not flats and there are interval flats that are not essential.
\end{remark}

Although not used for our main result, it is worth noting that arbitrary intersection of interval flats can be described using a similar criterion.

\begin{corollary}
\label{cor:generalcover}
Let $E$ be an arbitrary subset of $[n]$. Then $E$ is the intersection of interval flats if and only if $E^c$ is covered by CCW-arrows.
\end{corollary}

%\begin{proof}
%Let $E$ be an intersection of interval flats. Since the intersection of flats is again a flat \cite{Oxley}, we may assume that $E = [a_1,b_1] \union \cdots \union [a_s,b_s]$ where the $[a_i,b_i]$'s are pairwise disjoint cyclic intervals, the endpoints $a_1,b_1,a_2,b_2,\ldots,a_s,b_s$ are cyclically ordered. Then $E$ is the intersection of $[a_1,b_s],[a_2,b_1],\cdots,[a_s,b_{s-1}]$ where each one of them are interval flats. By Theorem~\ref{thm:intervalcover}, each component of $E^c$ is covered by CCW-arrows in them.

%For the other direction, write $E = [a_1,b_1] \union \cdots \union [a_s,b_s]$ where $[a_i,b_i]$'s are pairwise disjoint cyclic intervals and the endpoints $a_1,b_1,a_2,b_2,\ldots,a_s,b_s$ are cyclically ordered. Again using Theorem~\ref{thm:intervalcover}, the cyclic intervals $[a_1,b_s],[a_2,b_1],\cdots,[a_s,b_{s-1}]$ are all flats.
%\end{proof}



\begin{figure}[h]

\begin{center}
\includegraphics[scale = 0.7]{interval13810.pdf}

    \caption{The set $[1,3] \union [8,10]$ is the intersection of flats $[1,10]$ and $[8,3]$.}
		\label{fig:interval13810}

\end{center}
\end{figure}

For example, take a look at \cref{fig:interval13810}. The complement of $[1,3] \union [8,10]$ consists of the intervals $(3,8)$ and $(10,1)$. And each of those intervals is covered by CCW-arrows that does not intersect $[1,3] \union [8,10]$. So $[1,3] \union [8,10]$ is the intersection of interval flats. In particular, it is the intersection of $[1,10]$ and $[8,3]$, both of which are flats.


\begin{theorem}
Let $\M$ be a positroid of rank $d$ on $[n]$ and $\pi$ be its associated decorated permutation. Its matroid polytope $\Gamma_{\M}$ can be described by the inequalities $x_i \geq 0$ for all $i \in [n]$, the equality $x_1 + \cdots + x_n = d$ and inequalities of form
$$\sum_{l \in E} x_l \leq d - \ccw{E^c}$$
where $E$ is a cyclic interval whose complement is covered by CCW-arrows of $\pi$ and $\ccw{E^c}$ counts the number of CCW-arrows in $E^c$.
\end{theorem}

%\begin{proof}
%From combining Theorem~\ref{thm:matpoly} and Theorem~\ref{thm:intervalcover}, it is enough to show that the  flacets of a positroid are all interval flats. An inseparable set $E$ satisfies $\rk{E} = \nbd{E}$ from Theorem~\ref{thm:rk}. In that case for $E = [a_1,b_1] \union \cdots [a_s,b_s]$ where $a_1,b_1,\ldots,a_s,b_s$ are cyclically ordered, we have $\rk{E} = \rk{\M} - \minelts{b_s,a_1} - \minelts{b_1,a_2} - \cdots - \minelts{b_{s-1},a_s}$, where $\minelts{}$ stands for the number of minimal elements a base can have in that interval. This number is the rank of that interval in the dual matroid $\M^{*}$. Hence if $E$ is not an interval and we have $\rk{E} = \nbd{E}$, then $E^c$ is separable in $\M^{*}$ and is not a flacet. 
%Now if $E$ is not an interval, then $E^c$ 

%Theorem~\ref{thm:posipoly} and Theorem~\ref{thm:intervalcover}.
%\end{proof}

For example, take a look at the positroid coming from the decorated permutation of \cref{fig:permutation}. Recall that $[1,10]$ is a flat and $[1,3]$ is not. Hence $x_1 + \cdots x_{10} =  7 - 2$ (there are $2$ counter-clockwise arrows contained outside $[1,10]$) is one of the facets of the positroid polytope. And $x_1 + \cdots + x_3 = t$ for some number $t$ is not one of the facets of this polytope.


We also get an analogous result for independent sets:

\begin{theorem}
Let $\M$ be a positroid of rank $d$ on $[n]$ and $\pi$ be its associated decorated permutation. Its independent set polytope $\Gamma_{\M}$ can be described by inequalities $x_i \geq 0$ for each $i \in [n]$ and inequalities of form
$$\sum_{l \in E} x_l \leq d - \ccw{E^c}$$
where $E$ is a subset of $[n]$ whose complement is covered by CCW-arrows of $\pi$ and $\ccw{E^c}$ counts the number of CCW-arrows in $E^c$.
\end{theorem}

%\begin{proof}
%This follows from Theorem~\ref{thm:indpoly} with Theorem~\ref{thm:gencover}.
%\end{proof}


In other words, the sets $E$ where $E^c$ is covered by CCW-arrows forms a \newword{descriptive set of flats} \cite{greene} : the set of flats enough to fully obtain the independent sets via counting intersections. For example, again take a look at the positroid coming from the decorated permutation of \cref{fig:permutation}. For the independent set polytope, aside from the interval flats, we also have to consider ones that are not intervals. One of the inseparable flats was given by $[1,3] \union [8,10]$ from \cref{fig:interval13810}, so the corresponding facet of the independent set polytope of the positroid is given by $x_1 + x_2 + x_3 + x_8 + x_9 + x_{10} = 3$, since $\rk{[1,3] \union [8,10]} = 3$.





%\acknowledgements{\lipsum[20]}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\sloppy
\printbibliography
\fussy
%\bibliographystyle{plain}    % (uses file "plain.bst")




\end{document}
