%% 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[finalversion]{FPSAC2025}
\articlenumber{109}
%% 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{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}

\usepackage{float}
\usepackage{lipsum}
\usepackage{mathtools}
\usepackage{tikz}
\usepackage[dvipsnames]{xcolor}
\usepackage{caption}
\usepackage{graphicx}
\newcommand{\colorD}{NavyBlue}
\newcommand{\colorA}{Orchid}
\newcommand{\colorC}{JungleGreen}
\newcommand{\colorB}{Tan}
\newcommand{\colorE}{gray}
\newcommand{\sw}{\textcolor{cyan}}

\newcommand{\colorF}{Brown}
\newcommand{\colorG}{Cerulean}
\newcommand{\colorH}{CadetBlue}
\newcommand{\colorI}{NavyBlue}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{defin}[theorem]{Definition}
\newtheorem{eg}[theorem]{Example}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{prob}[theorem]{Problem}
\newtheorem{quest}[theorem]{Question}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{notation}[theorem]{Notation}

\usepackage{lipsum}
\usepackage{mleftright}

\newcommand{\rk}{\operatorname{rk}}
\newcommand{\cl}{\operatorname{cl}}
\newcommand{\st}{\operatorname{st}}
\newcommand{\supp}{\operatorname{supp}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\quo}{<_{q}}
\newcommand{\col}{\operatorname{col}}
\newcommand{\GrNeck}{\operatorname{GrNeck}}
\newcommand{\GrCoNeck}{\operatorname{GrCoNeck}}
\newcommand{\Pos}{\operatorname{Pos}}
\newcommand{\Uni}{\operatorname{Uni}}
\newcommand{\Lpm}{\operatorname{Lpm}}
\newcommand{\Sch}{\operatorname{Sch}}
\newcommand{\D}{\operatorname{Diag}}
\newcommand{\Path}{\operatorname{Path}}
\newcommand{\cw}{\operatorname{cw}}
\newcommand{\ccw}{\operatorname{ccw}}
\newcommand{\pis}{{\pi,\sigma}}

\newcommand{\nChoosek}{{\mleft(\genfrac..{0pt}{}{[n]}{k}\mright)}}

\newcommand{\yuxuan}[1]{{\color{cyan} \sf Yuxuan: [#1]}}

\usepackage{caption}
\usepackage{subcaption}

%% define your title in the usual way
\title[Partial flag positroids]{Partial flag positroids}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
% \author[Optional shorter names]{\texorpdfstring{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}{Longer names me, and you}}
\author[Zhixing Chen, Yumou Fei, Jiyang Gao, Yuxuan Sun, and Yuchong Zhang]{\texorpdfstring{Zhixing Chen\thanks{\href{mailto:20307110030@fudan.edu.cn}{20307110030@fudan.edu.cn}}\addressmark{1}, Yumou Fei\thanks{\href{mailto:feiym2002@stu.pku.edu.cn}{feiym2002@stu.pku.edu.cn}}\addressmark{2}, Jiyang Gao\thanks{\href{mailto:jgao@math.harvard.edu}{jgao@math.harvard.edu}}\addressmark{3}, Yuxuan Sun\thanks{\href{mailto:sun00816@umn.edu}{sun00816@umn.edu}}\addressmark{4}, \\\and Yuchong Zhang\thanks{\href{mailto:zongxun@umich.edu}{zongxun@umich.edu}}\addressmark{5}}{Zhixing Chen, Yumou Fei, Jiyang Gao, Yuxuan Sun, and Yuchong Zhang}}

%{Zhixing Chen\thanks{\href{mailto:20307110030@fudan.edu.cn}{20307110030@fudan.edu.cn}}\addressmark{1}, Yumou Fei\thanks{\href{mailto:feiym2002@stu.pku.edu.cn}{feiym2002@stu.pku.edu.cn}}\addressmark{2}, Jiyang Gao\thanks{\href{mailto:jgao@math.harvard.edu}{jgao@math.harvard.edu}}\addressmark{3}, Yuxuan Sun\thanks{\href{mailto:sun00816@umn.edu}{sun00816@umn.edu}}\addressmark{4}, \\\and Yuchong Zhang\thanks{\href{mailto:zongxun@umich.edu}{zongxun@umich.edu}}\addressmark{5}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Fudan University, Shanghai, China \\ \addressmark{2}Peking University, Beijing, China \\ \addressmark{3}Harvard University, Cambridge, MA \\ \addressmark{4}University of Minnesota Twin Cities, Minneapolis, MN \\ \addressmark{5}University of Michigan, Ann Arbor, MI}


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

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

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We study two-step flag positroids $(P_1, P_2)$, where $P_1$ is a quotient of $P_{2}$. We provide a complete characterization of all two-step flag positroids that contain a uniform matroid, extending and completing a partial result by Benedetti, Ch\'avez, and Jim\'enez. To contrast general positroids with the special case of lattice path matroids, we show that the containment relations of Grassmann necklaces and conecklaces fully characterize flag lattice path matroids, but are insufficient for general flag positroids. Additionally, we prove that the decorated permutations of any elementary quotient pair are related by a cyclic shift, resolving a conjecture of Benedetti, Ch\'avez and Jim\'enez.}

%% 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, matroids, flag matroids, lattice path matroids, Grassmann necklaces, decorated permutations} %%!!!!!!

%% 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; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{ref.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

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

\section{Introduction}
Positroids are an important class of matroids that can be represented by full-rank matrices with nonnegative maximal minors. They were first introduced by Postnikov in his study of the totally nonnegative Grassmannian \cite{Pos06}. The applications of positroids span several domains, including cluster algebra \cite{PS14} and physics \cite{KW11, Arkani21}.

Positroids also have many nice properties. They are closed under matroid duality and cyclic shifts of the ground set. Moreover, they are in bijection with many combinatorial objects, including Grassmann necklaces and decorated permutations \cite{Pos06,Oh11}.

An ordered pair of matroids $(M_1,M_2)$ is called a \emph{(two-step) flag matroid} if $M_1$ is a quotient of $M_2$, which means that every circuit of $M_2$ is a union of circuits of $M_1$. If both $M_1$ and $M_2$ are positroids, then the pair is called a \emph{(two-step) flag positroid}. 

Characterizing flag positroids via circuits is computationally challenging, as enumerating all unions of circuits requires exponential time. Since positroids can be represented concisely by many combinatorial objects such as Grassmann necklaces, it is natural to seek a more practical combinatrorial criterion for flag positroids.

\begin{quest}[\cite{Oh11}]
    Find a concise combinatorial criterion of flag positroids.
\end{quest}

This question was first posed in \cite[Section 7]{Oh11}, prompting numerous attempts to address it \cite{Oh17, Ben19, Ben22, Jon22}. In particular, several necessary conditions are identified for two-step flag positroids, such as \cite[Proposition 6.2]{Oh17} and \cite[Remark 36]{Ben19}. In contrast, finding sufficient conditions appears to be more challenging. To the authors' knowledge, existing sufficient conditions mainly focus on special cases: \cite{Ben22} provides a necessary and sufficient condition for flag lattice path matroids (a subclass of positroids), and \cite{Ben19} gives a sufficient but not necessary condition for elementary quotients (that is, quotients that decrease the rank by at most 1) of uniform matroids.

Our main result gives a necessary and sufficient characterization of all two-step flag positroids that contain a uniform matroid, based on their CW-arrows (a close relative of Grassmann necklaces, first defined by \cite{Oh17}).

\begin{theorem}\label{thm:uniformCW}
    Given integers $0\leq r\leq k<n$. Let $M$ be a positroid of rank $k-r$ on $[n]$, and let $U_{k,n}$ be the uniform matroid of rank $k$. Then $(M,U_{k,n})$ is a flag positroid if and only if the union of any $r+1$ CW-arrows of $M$ has cardinality at least $k+1$.
\end{theorem}

We note that our criterion is verifiable in $O(n^{3})$ time. The proof of \Cref{thm:uniformCW} employs a novel rank analysis based on results in \cite{mcalmon2020rank}. We also note that both the statement and the proof of \Cref{thm:uniformCW} differ significantly from the partial characterization in \cite{Ben19}.

\begin{remark}\label{rmk:nonlocality}
Consider the case where $k\ll n$. Then each CW-arrow is a clockwise arrow of length no more than $k$ on the circle of perimeter $n$. While each CW-arrow is a ``local structure'' on the circle (that is, involving only a few positions close to each other), \Cref{thm:uniformCW} considers a union of multiple CW-arrows that can be arbitrarily far away from each other. Since whether one positroid is a quotient of another is determined by the combined effects of distantly separated local structures, characterizing flag positroids requires \emph{non-local information} (in terms of positions on the circle). This explains why previous attempts at characterizing flag positroids such as \cite[Conjecture 6.3]{Oh17} have been unsuccessful (we give a simple counterexample for \cite[Conjecture 6.3]{Oh17} in \Cref{cex:Oh conj}). The authors view this insight as a main conceptual contribution of this paper.
\end{remark}
A canonical ``local property'' of flag positroids is the ``Grassmann necklace containment condition'' \cite[Remark 36]{Ben19}. In contrast to \Cref{rmk:nonlocality}, we show that the containment of both Grassmann necklace and Grassmann conecklace \emph{is} sufficient to characterize the quotients among lattice path matroids.

\begin{theorem}\label{thm:LPM}
Let $M$ and $N$ be lattice path matroids. Then $M$ is a quotient of $N$ if and only if the Grassmann necklace of $N$ contains the Grassmann necklace of $M$ entry-wise, and the Grassmann conecklace of $N$ contains the Grassmann conecklace of $M$ entry-wise.
\end{theorem}

\Cref{thm:LPM} demonstrates that certain ``local properties'' may naturally ``globalize'' for lattice path matroids but not for general positroids. In fact, the same counterexample for \cite[Conjecture 6.3]{Oh17}, as shown in \Cref{cex:Oh conj}, also shows that \Cref{thm:LPM} is not true for general positroids. 

We remark that a complete characterization of flag lattice path matroids was already obtained by \cite{Ben22}, and the purpose of our \Cref{thm:LPM} lies more in providing contrast to \Cref{thm:uniformCW}. See \Cref{remark:contrast} for further discussion.

Since CW-arrows are closely related to Grassmann necklaces, it is natural to consider counterparts of Grassmann necklace containment conditions in CW-arrows. Surprisingly, they turn out to be intimately related to the \emph{cyclic shift} operation introduced by \cite{Ben19} for decorated permutations (another canonical representation of positroids). Using this connection, we resolve the following conjecture in \cite{Ben19}.

\begin{theorem}[{\cite[Conjecture 37]{Ben19}}]\label{thm:cyclicshift}
If $M,N$ are positroids and $M$ is an elementary quotient of $N$, then the decorated permutations associated with $M$ and $N$ are related by a cyclic shift.
\end{theorem}

Note that since cyclic shift is a counterpart of the necklace containment condition (as shown in \Cref{thm:neckcontain=shift}), it is by our standards a ``local property,'' and thus does not provide a sufficient characterization of flag positroid (see \Cref{cex:Oh conj}).

This paper is structured as follows. \Cref{sec:prelim} provides necessary background on flag matroids and positroids. \Cref{sec:3} builds a connection between the containment of Grassmann necklaces and cyclic shifts, culminating in a proof of \Cref{thm:cyclicshift}. \Cref{thm:uniformCW,thm:LPM} are proved and discussed in further detail in \Cref{sec:4,sec:5}, respectively.

\section{Preliminaries}\label{sec:prelim}

We denote the set $\{1,2,\dots,n\}$ by $[n]$, and its $k$-element subset by $\binom{[n]}{k}$. 

\subsection{Matroids and flag matroids}\label{subsec:quotient}

Matroids are combinatorial structures that abstract and generalize the concept of linear independence. We refer the readers to \cite{Ox11} for a more detailed exposition.

\begin{defin}
    Let $E$ be a finite set, and let $\mathcal{B}$ be a nonempty collection of subsets in $E$. The pair $M=(E, \mathcal{B})$ is a \emph{matroid} if for all $B, B' \in \mathcal{B}$ and $x \in B\setminus B'$, there exists $y \in B'\setminus B$ such that $(B \cup \left\{y\right\}) \setminus \left\{x\right\} \in \mathcal{B}$. The set $E$ is the \emph{ground set} of $M$, and the elements of $\mathcal{B}=\mathcal{B}(M)$ are the \emph{bases} of $M$.
\end{defin}

\begin{defin}
    It can be shown that all bases of a matroid have the same cardinality. We call this cardinality the \emph{rank} of $M$. Moreover, we associate with every matroid $M=(E,\mathcal{B})$ a \emph{rank function} $\rk:2^{[n]}\rightarrow\mathbb{N}$ defined by $\rk(S):=\max\{|S\cap B|:B\in\mathcal{B}\}$. 
\end{defin}

\begin{defin}
Given a matroid $M = (E, \mathcal{B})$, a subset $I \subseteq E$ is called an \emph{independent set} of $M$ if it is contained in some basis of $M$. Otherwise, we say $I$ is \emph{dependent}. If a subset $C\subseteq E$ is dependent but every proper subset of $C$ is independent, then $C$ is said to be a \emph{circuit} of $M$.
\end{defin}

\begin{defin}
    Given a matroid $M = (E, \mathcal{B})$, the collection $\mathcal{B}^* = \left\{ E \setminus B \mid B \in \mathcal{B}\right\}$ also forms the set of bases of a matroid. The matroid $M^*\coloneq (E,\mathcal{B}^*)$ is called the \emph{dual} of $M$.
\end{defin}

The rank functions of a matroid and its dual are related by the following formula.

\begin{prop}[{\cite[Proposition 2.1.9]{Ox11}}]\label{prop:rank-dual}
Let $\rk_{M}$ be the rank function of $M$ on the ground set $E$, and $\rk_{M^*}$ be the rank function of $M^{*}$. Then for any $S\subseteq E$ we have
    \[\rk_{M^*}(S) = \rk_{M}(E \setminus S) + |S| - \rk(M).\]
\end{prop}

We now define the quotient relation on matroids.

\begin{defin}
Given two matroids $M$ and $N$ on the same ground set $E$, we say that $M$ is a \emph{quotient} of $N$, or $(M,N)$ forms a \emph{flag matroid}, if every circuit of $N$ is the union of a collection of circuits of $M$. If in addition the rank of $M$ is exactly one less than the rank of $N$, then $M$ is called an \emph{elementary quotient} of $N$.
\end{defin}

The quotient relation has a convenient characterization using rank functions.

\begin{prop}[{\cite[Proposition 8.1.6]{white1986theory}}]\label{prop:rank-quotient}
Given two matroids $M$, $M'$ on the same ground set $E$, $M$ is a quotient of $M'$ if and only if for all pairs of subsets $A,B$ of $E$ with $A\subseteq B$, 
$$\rk_{M}(B)-\rk_{M}(A)\leq \rk_{M'}(B)-\rk_{M'}(A).$$
\end{prop}

\subsection{Gale orders}

Positroids are a special class of matroids linked with the cyclic structure $(1,2,\dots,n,1)$ of the ground set $[n]$. We first introduce some useful notions for any ordering of the ground set.

\begin{defin}
For any total order $<_{w}$ on $[n]$, the \emph{Gale order} $\leq_{G,w}$ induced by $<_{w}$ is a partial order on subsets of $[n]$: for two $k$-element subsets $A,B\in\binom{[n]}{k}$, we say $A\leq_{G,w}B$ if $a_{i}\leq_{w}b_{i}$ for all $i\in[k]$, where $a_{i}$ (resp. $b_{i}$) is the $i$-th smallest element of $A$ (resp. $B$) under the order $<_{w}$.    
\end{defin}

The special orderings we use are the cyclic orders $<_{i}$ defined by
$$i<_{i}i+1<_{i}\dots<_{i}n<_{i}1<_{i}2<_{i}\dots <_{i}i-1.$$
With a slight abuse of notation, we use $\leq_{i}$ to also denote the Gale order induced by $<_{i}$.

The following proposition provides another characterization of matroid quotients.


\begin{prop}[{\cite[Theorems 1.3.1 and 1.7.1]{Bor03}}]\label{prop:quotient-implies-containment}
If $\mathcal{B}$ is the collection of bases of a matroid on a ground set ordered by $<_{w}$, then there is a unique basis $A\in\mathcal{B}$ such that $A\leq_{G,w}A'$ for any $A'\in\mathcal{B}$. Moreover, if $\mathcal{B}$ and $\mathcal{B}'$ are the collections of bases of two matroids $M$ and $M'$ respectively, and $M$ is a quotient of $M'$, then their unique minimal bases satisfy $\min_{\leq_{G,w}}\mathcal{B}\subseteq \min_{\leq_{G,w}}\mathcal{B}'.$
\end{prop}

\subsection{Grassmann necklaces and positroids}

The following combinatorial structure helps us define positroids.
\begin{defin}[{\cite[Definition 16.1]{Pos06}}]
For $0\leq k\leq n$, a \emph{Grassmann necklace of type $(k,n)$}, or simply a \emph{necklace}, is a sequence $I=(I_{1},I_{2},\dots,I_{n})$ of subsets $I_{i}\in\binom{[n]}{k}$ such that for every $i\in [n]$ (with the convention that $I_{n+1}:=I_{1}$):
\begin{enumerate}
\item if $i\in I_{i}$, then $I_{i+1}=(I_{i}\setminus\{i\})\cup \{j\}$ for some $j\in[n]$;
\item if $i\not\in I_{i}$, then $I_{i+1}=I_{i}$.
\end{enumerate}
\end{defin}

The original definition of positroids \cite{Pos06} is matroids whose bases correspond to nonzero maximal minors of a $k\times n$ matrix with all maximal minors nonnegative. In this paper, we adopt the following equivalent definition proved by \cite{Oh11}.

\begin{defin}[{\cite[Theorem 6]{Oh11}}]\label{prop:necklace-minimizes}
For any Grassmann necklace $I=(I_{1},\dots,I_{n})$ of type $(k,n)$, $$\mathcal{B}(I)\coloneq \left\{B\in\binom{[n]}{k}:I_{i}\leq_{i} B\text{ for all }i\in [n]\right\}$$
forms the collection of bases of some matroid. Such a matroid is said to be a \emph{positroid} on the ground set $[n]$. In addition, we always have $I_{i}=\min_{\leq_{i}}\left\{\mathcal{B}(I)\right\}$ for all $i\in[n]$.
\end{defin}

We also introduce the following dual version of Grassmann necklaces, which coincides with the ``upper Grassmann necklace'' defined in \cite{Oh11}.

\begin{defin}\label{def:conecklace}
    For a positroid $M$$=$$([n],\mathcal{B})$, the sequence $(J_{1},\dots,J_{n})$ with $J_{i}$$:=\max_{\leq i}\{\mathcal{B}(I)\}$ for $i\in[n]$ is called the \emph{Grassmann conecklace}, or simply the \emph{conecklace}, of $M$.
\end{defin}

    In this paper, a set of Arabic numerals is denoted by their concatenation.
    
\begin{eg}\label{eg:grNeck}
    The necklace and conecklace of the positroid $P = ([5], \left\{ 1234,1235,1245,1345\right\})$ are $I = (1234, 2341, 3451, 4512, 5123)$ and $J=(1345,3451,\allowbreak 4512,5123,1234)$ respectively.
\end{eg}

It is proved in \cite{Oh11} that lattice path matroids form a special class of positroids.
\begin{defin}[{\cite[Definition 3.1]{Bon03}}]\label{def:LPM}
    A \emph{lattice path matroid (LPM)} $M[U,L]$, where $U,L \in \binom{[n]}{k}$ and $U \leq_{1} L$, is a matroid $([n],\mathcal{B})$ with $\mathcal{B} := \left\{B \in \binom{[n]}{k} \mid U \leq_{1} B \leq_{1} L\right\}$.
\end{defin}


\subsection{Decorated permutations}
The paper \cite{Pos06} also introduces decorated permutations, a class of combinatorial objects that are in bijection with Grassmann necklaces.

\begin{defin}[{\cite[Definition 13.3]{Pos06}}]
    A \emph{decorated permutation} $\pi^:$ on $[n]$ consists of data $(\pi,\col)$, where $\pi \in \mathfrak{S}_{n}$ and $\col:[n] \to \{0,\pm 1\}$ is a mapping such that $\col^{-1}(0)$ is the set of unfixed points of $\pi$. %We denote the set of decorated permutations on $[n]$ by $D_{n}$.
\end{defin}

Following the convention of \cite{Pos06}, we add underlines to elements in $\col^{-1}(-1)$, overlines to $\col^{-1}(1)$, and nothing to others. We say elements in $\col^{-1}(1)$ and $\col^{-1}(-1)$ are \emph{loops} and \emph{coloops} respectively.

As a general convention in examples throughout this paper, a decorated permutation $\pi^{:}$ is represented by concatenating the numbers $\pi^{:}(1),\dots,\pi^{:}(n)$, with each number either underlined, overlined, or undecorated. 

\begin{eg}\label{eg:dp}
    Given decorated permutation $\pi^:=(\pi,\col)=41\overline{3}562\underline{7}$, we have $\col^{-1}(0)=4156$, $\col^{-1}(1) = 3$, and $\col^{-1}(-1) = 7$. Thus, its loop is $3$ and coloop is $7$.
\end{eg}

To state the bijection between Grassmann necklaces and decorated permutations on the same ground set, we introduce the concept of \emph{anti-exceedance}.

\begin{defin}[\cite{Pos06}]
    Given a decorated permutation $\pi^:$, the set of its \emph{$i$-anti-exceedances} is
    \[W_{i}(\pi^:) := \left\{j \in [n] \mid j <_{i} \pi^{-1}(j) \text{ or } \col(j) = -1\right\}.\]
\end{defin}

\begin{prop}[{\cite[Lemma 16.2]{Pos06}}]\label{prop:decpermtoneck}
    Given a decorated permutation $\pi^{:}$ on $[n]$, the sequence $(W_{1}(\pi^{:}),\dots,W_{n}(\pi^{:}))$ is a Grassmann necklace. Conversely, the following procedure maps a Grassmann necklace $I=(I_{1},\dots,I_{n})$ to a decorated permutation $\sigma^: = (\sigma, \col)$:
    \begin{enumerate}
        \item if $I_{i+1} = (I_{i} \setminus \{i\}) \cup \{j\}$ with $i \neq j$, let $\sigma(i) = j$ and $\col(i) = 0$;
        \item if $I_{i+1} = I_i$, let $\sigma(i) = i$; moreover, if $i \in I_i$, let $\col(i) = -1$, otherwise $\col(i) = 1$.
    \end{enumerate}

    These maps between Grassmann necklaces and decorated permutations are mutually inverse.
\end{prop}

\begin{eg}
    Consider $\pi^: = \underline{1}5234$. Denote its corresponding necklace by $I$. By calculating anti-exceedances, we obtain the same Grassmann necklace as in \Cref{eg:grNeck}. Applying the procedure in \Cref{prop:decpermtoneck} to this necklace gives rise to $\underline{1}5234$, the decorated permutation we started with.
\end{eg}

Decorated permutations also give a canonical bijection between the Grassmann necklace and the Grassmann conecklace of a positroid.

\begin{prop}[{\cite[Lemma 17]{Oh11}}]\label{prop:coneck deco}
Let $M$ be a positroid over $[n]$. Let $I=(I_{1},\dots,I_{n})$ be its Grassmann necklace and let $\pi^{:}$ be its decorated permutation. Then the Grassmann conecklace $J=(J_{1},\dots,J_{n})$ of $M$ is given by $J_{i}=\pi^{-1}(I_{i})$.
\end{prop}

\begin{remark}\label{remark:different dec convention}
    In some other literature, for example, in \cite{Ard13} and \cite{Ben19}, they use a slightly different convention for decorated permutations compared to \Cref{prop:decpermtoneck}. Specifically, their decorated permutation $ (\pi, \col) $ corresponds to our $ (\pi^{-1}, \col) $, meaning that their ``numbers'' are our ``positions'' and vice versa.
\end{remark}


\section{Cyclic shifts and necklace containment}\label{sec:3}

In \cite{Ben19}, the authors introduce the notion of \emph{cyclic shifts}, an operation on decorated permutations that cyclically shifts some elements. Their main conjecture, \cite[Conjecture 37]{Ben19} (that is, our \Cref{thm:cyclicshift}), claims that the decorated permutations of any elementary quotient of a positroid $M$ can be represented by a cyclic shift of the decorated permutation of $M$. The primary goal of this section is to sketch the proof of this conjecture. Additionally, we characterize the shifted positions using Grassmann conecklaces.


\begin{defin}[{\cite[Definition 22]{Ben19}}] \label{def:shift}
    Given a decorated permutation $\pi^{:} = (\pi,\col_{\pi})$ on $[n]$ and a subset $A \subseteq [n]$, we define a new decorated permutation $(\sigma,\col_{\sigma})=\overrightarrow{\rho_{A}}(\pi^{:})$ as follows:
    \begin{enumerate}
        \item for all $i\in A$, let $\sigma(i)=\pi(i)$ and $\col_{\sigma}(i)=\col_{\pi}(i)$;
        \item for $i \notin A$, let $\sigma(i)=\pi(j)$, where $j$ is the maximum element of $[n]\setminus A$ under $<_{i}$;
        \item for $i\notin A$, let $\col_{\sigma}(i)=1$ if $\sigma(i)=i$. Otherwise, define $\col_{\sigma}(i)=0$.
    \end{enumerate}
    We call $\overrightarrow{\rho_{A}}(\pi^{:})$ the \emph{cyclic shift} of $\pi^{:}$ with respect to the set $A$.
\end{defin}

Intuitively, $\overrightarrow{\rho_{A}}$ fixes all positions in $A$. Then, among the remaining positions, it cyclically shifts the numbers one place to the right and decorates new fixed points as loops.

\begin{eg}
    Let $\pi^{:} = \overline{1}65\overline{4}23\underline{7}$, then $\overrightarrow{\rho_{247}}(\pi^{:}) = 361\overline{45}2\underline{7}$.  
\end{eg}

\begin{remark}
    The convention in \cite{Ben19} is slightly different from ours. Specifically, the subset $A$ in our definition represents the fixed positions, while in \cite{Ben19} it represents fixed numbers. This is because we use a different convention of decorated permutations. See \Cref{remark:different dec convention}.
\end{remark}

\begin{notation}
If $(M,N)$ is a flag positroid with adjacent ranks, and $\sigma^{:}$ and $\pi^{:}$ are their corresponding decorated permutations, then we denote $\sigma^{:} \lessdot \pi^{:}$.
\end{notation}


The following theorem is the main theorem in this section.
%It is conjectured in \cite{Ben19} that if $\sigma^{:}\lessdot\pi^{:}$ then there exists $A\subseteq [n]$ such that $\sigma^{:}=\overrightarrow{\rho_{A}}(\pi^{:})$. In this section, we give an affirmative answer to the conjecture: 

\begin{theorem}\label{thm:neckcontain=shift}
    Let $M$ and $N$ be two positroids on $[n]$, and $\rk(M)=\rk(N)-1$. Let $\sigma^{:}$ and $\pi^{:}$ be the decorated permutations of $M$ and $N$, and let $I^{\sigma}$ and $I^{\pi}$ be the Grassmann necklaces of $M$ and $N$, respectively. Then, $I^{\sigma}_{i}\subseteq I^{\pi}_{i}$ for all $i\in [n]$ if and only if there exists $A\subseteq [n]$ such that $\sigma^{:} = \overrightarrow{\rho_{A}}(\pi^{:})$.
\end{theorem}

By \Cref{prop:quotient-implies-containment,prop:necklace-minimizes}, given a flag positroid $(M,N)$, the Grassmann necklaces satisfy $I^{\sigma}_{i}\subseteq I^{\pi}_{i}$. Therefore, \Cref{thm:neckcontain=shift} implies \Cref{thm:cyclicshift}.

Our key insight in the proof is reflected in a tool we defined, called \emph{Grassmann matrices}, whose rows and columns characterize the information about cyclic shifts and Grassmann necklaces, respectively, thereby establishing a connection between them.

For decorated permutations $\pi^{:}$ and $\sigma^{:}$ over $[n]$, we use $I^{\pi}$ and $I^{\sigma}$ to denote the corresponding Grassmann necklaces, and use $J^{\pi}$ and $J^{\sigma}$ to denote the corresponding Grassmann conecklaces.  
We also use the convention that the cyclic interval $(i,i]=\emptyset$.


\begin{defin}
Given a decorated permutation $\pi^{:}$ on $[n]$, we define the \emph{Grassmann interval} $S_i^\pi$ associated with each $i \in [n]$ to be the cyclic interval $(\pi^{-1}(i), i]$. In the exceptional case where $\pi^:(i) = \overline{i}$, we set $S_i^\pi \coloneq [n]$.
The \emph{Grassmann matrix} $M^\pi$ is the $n \times n$ binary matrix where the $i$-th row is the indicator vector of the Grassmann interval $S_i^\pi$. Specifically, the entry $(M^\pi)_{i,j}$ is equal to $1$ if $j \in S_i^\pi$ and $0$ otherwise.
\end{defin}

We remark that the ``Grassmann interval'' used here is almost the same as the ``CW-arrow'' defined by \cite{Oh17} (see \Cref{rmk:interval-to-arrow} for further discussion). Our definition of Grassmann intervals serve to demonstrate more clearly the close relation of CW-arrows to Grassmann necklaces, as captured by the following lemma.

\begin{lemma}\label{lemma:grassmann matrix}
    Given a Grassmann matrix $M^{\pi}$, the $j$-th column of $M^{\pi}$ is the indicator vector for $I^{\pi}_j$. Consequently, the sum of each column of $M^{\pi}$, which we hereafter denote by $\rk(\pi^{:})$, coincides with $|I^{\pi}_{1}|$, the rank of the associated positroid.
\end{lemma}

\begin{eg}
     Let $\pi^{:} = \overline{1}65\overline{4}23\underline{7}$, then the Grassmann matrix is
     \[M^\pi=\begin{pmatrix}
         0&0&0&0&0&0&0\\
         1&1&0&0&0&1&1\\
         1&1&1&0&0&0&1\\
         0&0&0&0&0&0&0\\
         0&0&0&1&1&0&0\\
         0&0&1&1&1&1&0\\
         1&1&1&1&1&1&1
     \end{pmatrix}.\]
     The Grassmann interval $S_3^\pi=(\pi^{-1}(3),3]=(6,3]=\{7,1,2,3\}=\{1,2,3,7\}$ can be read through the third row of $M^\pi$, and $I_4=\{5,6,7\}$ of the Grassmann necklace $I$ can be read through the fourth column of $M^\pi$.
\end{eg}

\Cref{lemma:grassmann matrix} immediately implies the following corollary.
\begin{cor}\label{cor:neckcontain=vecdom}
    $I^{\sigma}_{i}\subseteq I^{\pi}_{i}$ for any $i\in [n]$ if and only if $S^{\sigma}_i\subseteq S^{\pi}_i$ for any $i\in[n]$
\end{cor}

To establish connections with cyclic shifts $\sigma^{:} = \overrightarrow{\rho_{A}}(\pi^{:})$, we define \emph{shift intervals} $S^{\pis}_i$. In fact, shift intervals record the rows of $M^\pi-M^\sigma$.

\begin{defin}\label{def:vec_w}
Given two decorated permutations $\sigma^:, \pi^:$ over $[n]$, 
we define the \emph{$i$-th shift interval} as cyclic interval $(\pi^{-1}(i), \sigma^{-1}(i)]$. In the exceptional case where $\sigma^:(i)=\overline{i}$ and $\pi^:(i)=\underline{i}$, we set $S^{\pis}_i\coloneq [n]$.
\end{defin}

\begin{eg}
    Let $\pi^:=456123$ and $\sigma^:=2461\overline{5}3$. We have
    \begin{align*}
         &S^{\pi}_2=(\pi^{-1}(2),2]=\{6,1,2\}, \quad S^{\sigma}_2=(\sigma^{-1}(2),2]=\{2\}, \text{ and}\\
        &S^\pis_2=(\pi^{-1}(2),\sigma^{-1}(2)]=\{6,1\}=S^{\pi}\setminus S^{\sigma}.
    \end{align*}
\end{eg}

Using the shift intervals as an intermediary, we establish the connection between Grassmann necklace containment and the cyclic shift.

 \begin{lemma}\label{lemma:Gr contain and shift}
     For two decorated permutations $\sigma^:, \pi^:$ over $[n]$ where $\rk(\sigma^:)=\rk(\pi^:)-1$, we have
     \begin{enumerate}
     \item      $\bigsqcup_{i=1}^{n}S^\pis_i=[n]$ if and only if $S^{\sigma}_i\subseteq S^{\pi}_i$ for any $i\in[n]$;
     
     \item $\bigsqcup_{i=1}^{n}S^\pis_i=[n]$ if and only if $\sigma^{:}=\overrightarrow{\rho_{A}}(\pi^{:})$ for some $A\subseteq [n]$.
     \end{enumerate}
 \end{lemma}

\Cref{thm:neckcontain=shift} now follows from \Cref{lemma:grassmann matrix,lemma:Gr contain and shift}. Furthermore, we can use Grassmann conecklaces to characterize the shifting positions of cyclic shifts.

\begin{theorem}\label{thm:shift}
    Let $(M,N)$ be a flag positroid with $\rk(M)=\rk(N)-1$.
    If $\sigma^{:}$ and $\pi^{:}$ represent the decorated permutations of $M$ and $N$ respectively, 
    then $\sigma^{:} = \overrightarrow{\rho_{A}}(\pi^{:})$, where $A = [n] \setminus \bigcup_{i \in [n]}(J^{\pi}_{i} \setminus J^{\sigma}_{i})$. Here,  $(J^{\sigma}_{i})_{i\in [n]}$ and $(J^{\pi}_{i})_{i\in [n]}$ are the conecklaces of $M$ and $N$ respectively.
\end{theorem}

\begin{eg}\label{eg:cyclic shift not quotient}
    Using SageMath \cite{sagemath}, the readers could verify that $\pi^{:} = 315642$ has exactly two positroid quotients with adjacent rank: $\sigma^:_1=235641$ and $\sigma^:_2=314562$. We have $\sigma^:_1=\overrightarrow{\rho_{345}}(\pi^:)$ and $\sigma^:_2=\overrightarrow{\rho_{126}}(\pi^:)$, which agrees with \Cref{thm:shift}.
\end{eg}

\begin{remark}
    The converse of \Cref{thm:shift} is false -- cyclic shifts do not always produce quotients. For example, $\sigma^:_3=135642$ is not a quotient of $\pi^{:}= 315642$, but $\sigma^:_3=\overrightarrow{\rho_{3456}}(\pi^:)$.
\end{remark}

\section{Positroid quotients of uniform matroids}\label{sec:4}
In this section, we sketch the proof of \Cref{thm:uniformCW}, which gives a complete characterization of flag positroids $(P,U_{k,n})$. We first introduce the definition of CW-arrows.

\begin{defin}[\cite{Oh17}]
    Let $\pi^: = (\pi, \col)$ be a decorated permutation on $[n]$. For each $i \in [n]$, the \emph{CW-arrow} starting at $i$ is defined by\[
    C_{i}=\begin{cases}
[n],&\text{if }\pi(i)=i\text{ and }\col(i)=-1,\\
\{j\in [n]:j\leq_{i}\pi(i)\}, &\text{otherwise.}
\end{cases}
    \]
\end{defin}

\begin{remark}\label{rmk:interval-to-arrow}
The intuition behind CW-arrows is that, we put $1, \dots, n$ on a circle in the clockwise order, and draw an arrow from $i$ to $\pi(i)$ clockwise. The numbers covered by the arrow are in the CW-arrow starting at $i$. When $i$ is a coloop, the arrow goes through the entire circle, whereas when $i$ is a loop, its CW-arrow is a singleton. Moreover, CW-arrows can be viewed as Grassmann intervals with their left endpoints included.
\end{remark}

The proof of \Cref{thm:uniformCW} combines the following two lemmas and \cite[Theorem~25]{mcalmon2020rank}.

\begin{lemma}\label{lem:rankcyclic}
Let $M$ be a positroid on $[n]$, and let $\rk$ be its rank function. Let $(I_{1},\dots,I_{n})$ be the Grassmann necklace associated with $M$. If 
$J$ is a cyclic interval of the form $J=\{\ell\in [n]:\ell\leq_{i} j\}$ for some $j\in [n]$, then we have
$\rk(J)=|J\cap I_{i}|.$
\end{lemma}

\begin{lemma}\label{lem:rank_char_of_quotient}
Let $M$ be a matroid on $[n]$ of rank $k-r$, and let $\rk$ be its rank function. Then $M$ is a quotient of $U_{k,n}$ if and only if
$\rk(A)=k-r$
for any $k$-element subset $A\subseteq [n]$.
\end{lemma}

We give the readers some working examples to check \Cref{thm:uniformCW}.

\begin{eg}\label{eg:cw}
    Consider the uniform matroid $U_{4,6}$, a positroid $P$ of rank $2$ whose decorated permutation is $\overline{1}54623$, and a positroid $Q$ of rank $1$ whose decorated permutation is $6 \overline{2345} 1$. The CW-arrows of $P$ are $1, 2345, 34, 456, 5612$, $6123$. The readers could check that the union of any $3$ of them has cardinality of at least $5$. The CW-arrows of $Q$ are $123456,2,3,4,5,61$. If we take $2,3,4,5$, the cardinality of the union of these $4$ CW-arrows is less than $5$. Therefore, $P$ is a quotient of $U_{4,6}$, but $Q$ is not.
\end{eg}

By \Cref{thm:cyclicshift}, we know that the decorated permutation of any elementary quotient of $U_{k,n}$ takes the form $\overrightarrow{\rho_{A}}(\pi_{k,n})$, where $\pi_{k,n}$ is the decorated permutation corresponding to $U_{k,n}$. The special case $r=1$ of \Cref{thm:uniformCW} allows us to obtain a criterion on $A$ to determine whether $\overrightarrow{\rho_{A}}(\pi_{k,n})$ represents a quotient of $U_{k,n}$.

\begin{theorem}\label{thm:uniform}
    Let $1\leq k\leq n-1$, and let $\sigma^:$ be a decorated permutation on $[n]$. Then $\sigma^{:}\lessdot \pi_{k,n}$ if and only if $\sigma^: = \overrightarrow{\rho_{A}}(\pi_{k,n})$ for some $A \subseteq [n]$, where the union of any two distinct cyclic components of $A$ has cardinality at most $k-1$.
\end{theorem}

\begin{eg}
 Consider the uniform positroid $U_{8,4}$ given by the decoration $\pi_{4,8} = 56781234$. If the fixing set is $\{3\} \cup \{5\} \cup [8,1]$ or $\{3\} \cup \{6\} \cup \{8\}$, then in either case, the union of any two components does not exceed $3 = 4 - 1$. By \Cref{thm:uniform}, we know both two cyclic shifts give positroid quotients of $U_{4,8}$.
    If the fixing set is $A = \{5\} \cup [8,2]$, then the union of two components $\{5\}$ and $[8,2]$ has size $4$, violating the condition. As a result, $\overrightarrow{\rho_{A}}(\pi_{4,8})$ does not produce a quotient of $U_{4,8}$.
\end{eg}

\begin{remark}
The paper \cite{Ben19} also focuses on characterizing elementary positroid quotients of uniform matroids. They proved that the condition $|A|\leq k-1$ is sufficient for  $\overrightarrow{\rho_{A}}(\pi_{k,n})\lessdot \pi_{k,n}$ (\cite[Theorem 28]{Ben19}), while a necessary condition is that each \emph{individual} cyclic component of $A$ has cardinality at most $k-1$ (\cite[Theorem 26]{Ben19}). In comparison, our results show that the precise necessary and sufficient condition lies between these two: specifically, the union of any two cyclic components must have cardinality at most $k-1$.
\end{remark}


\section{Flag LPMs and necklace containment}\label{sec:5}

By \Cref{prop:quotient-implies-containment}, \Cref{prop:necklace-minimizes}, and \Cref{def:conecklace}, we know that flag positroids satisfy the containment conditions of Grassmann necklaces and Grassmann conecklaces.

\begin{prop}\label{prop:Ne CoNe Cont}
    Given a flag positroid $(M,N)$, let $I,I'$ be the Grassmann necklaces of $M$ and $N$, and let $J,J'$ be the Grassmann conecklaces of $M$ and $N$, respectively. Then $I_{i}\subseteq I_{i}'$ and $J_{i}\subseteq J'_{i}$ for all $i\in [n]$.
\end{prop}

\begin{remark}\label{rmk:necklace-containment-is-local}
Recall from \Cref{rmk:nonlocality} that we regard each CW-arrow as a ``local object,'' and that \Cref{thm:uniformCW} shows that ``non-local'' information is needed to characterize flag positroids. By \Cref{cor:neckcontain=vecdom}, we know that the necklace containment condition (that is, $I_{i}\subseteq I'_{i}$ for all $i\in [n]$) captures only ``local'' information of both positroids. The same reasoning applies to the conecklace containment condition. Thus, the converse of \Cref{prop:Ne CoNe Cont} is not true for flag positroids in general. We provide a concrete counterexample in the next remark.
\end{remark}

\begin{remark}\label{cex:Oh conj}
For example, let $M$ be a positroid given by the decorated permutation $261534$ and take $N$ to be the uniform positroid $U_{4,6}$. The necklace and conecklace of $M$ are $(134,234,346,461,\allowbreak 561,613)$ and $(356,561,562,623,234,235)$, respectively. For $N$, they are $(1234,2345,3456,$ {\parfillskip=0pt \par} \noindent
$4561,\allowbreak 5612,6123)$ and $(3456,4561,5612,6123,1234,2345)$. They satisfy the containment conditions. However, $\rk_{M}([6])-\rk_{M}(1245)=1$ while $\rk_{N}([6])-\rk_{N}(1245)=0$. This means $M$ is \emph{not} a quotient of $N$, since the rank condition in \Cref{prop:rank-quotient} is violated. Furthermore, the counterexample above also disproves the ``if'' part of \cite[Conjecture 6.3]{Oh17}. 
\end{remark}

The containment of necklaces and conecklaces only gives a necessary condition of flag positroids. But we show that in LPMs, the converse remains true. 

\begin{theorem}\label{thm:LPM Ne CoNe theorem}
    Given two LPMs $M$ and $N$ on $[n]$, let $I,I'$ be the Grassmann necklaces of $M$ and $N$, and let $J,J'$ be the Grassmann conecklaces of $M$ and $N$, respectively. The following conditions are equivalent:
    \begin{enumerate}
        \item $I_{i}\subseteq I_{i}'$ and $J_{i}\subseteq J_{i}'$ for all $i\in [n]$;
        \item $(M,N)$ is a flag positroid.
    \end{enumerate}

\end{theorem}

\begin{remark}\label{remark:contrast}
    We note that a necessary and sufficient criterion for flag LPMs was previously established in \cite{Ben22}, and our proof of \Cref{thm:LPM Ne CoNe theorem} builds upon these results. The main contribution of \Cref{thm:LPM Ne CoNe theorem}, as the authors see it, lies in its contrast with the ''non-local phenomenon'' described in \Cref{thm:uniformCW} (see \Cref{rmk:nonlocality}). As discussed in \Cref{rmk:necklace-containment-is-local,cex:Oh conj}, necklace containment captures only ``local information.'' Our \Cref{thm:LPM Ne CoNe theorem} highlights the insight that LPMs, as a special class of positroids, are structured in such a way that ``local information'' alone suffices to guarantee the ``global'' property of quotient relations.
\end{remark}


\begin{remark}
It is worth mentioning that neither necklace containment nor conecklace containment guarantees flag LPMs alone. A counterexample for necklaces is $M[14, 57]$ and $N[145, 467]$. In this case, we have 
\[
    I =(14,24,34,45,56,16,17) \quad \text{and} \quad I'=(145,245,345,456,156,167,147).
\]
So we have $I_i\subseteq I'_i$ for all $i=1,2, \dots, 7$, but $M$ is not a quotient of $N$. By examining the dual of this counterexample, one can obtain a counterexample for conecklaces.
    
\end{remark}




\acknowledgements{This research was carried out as part of the PACE program in the summer of 2023 at Peking University, Beijing, partially supported by NSFC grant 12426507. We thank Shiliang Gao, Yibo Gao, and Lauren Williams for helpful discussions. }

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography


\end{document}