\documentclass[submission]{FPSAC2017}

\articlenumber{81}
\addbibresource{81_Chavez_Gotti.bib}

% Theorems-like Format and Numbering:

\newtheorem*{maintheorem*}{Main Theorem}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{cor}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\numberwithin{equation}{section}


\usepackage{amssymb}
\usepackage{bm}


%% Personalized Commands:

\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.
}

\title[Dyck Paths and Positroids from Unit Interval Orders]{Dyck Paths and Positroids from Unit Interval Orders}

\author{Anastasia Chavez \and Felix Gotti\thanks{\href{mailto:felixgotti@berkeley.edu}{felixgotti@berkeley.edu}}}

\address{Department of Mathematics, UC Berkeley, Berkeley CA 94720}


\abstract{It is well known that the number of non-isomorphic unit interval orders on $[n]$ equals the $n$-th Catalan number. Using work of Skandera and Reed and work of Postnikov, we show that each unit interval order on $[n]$ naturally induces a rank $n$ positroid on $[2n]$. We call the positroids produced in this fashion \emph{unit interval positroids}. We characterize the unit interval positroids by describing their associated decorated permutations, showing that each one must be a $2n$-cycle encoding a Dyck path of length $2n$.}

\keywords{positroid, Dyck path, unit interval order, semiorder, decorated permutation, positive Grassmannian}


\begin{document}
	
	\maketitle
	
	\section{Introduction}
	
	A \emph{unit interval order} is a partially ordered set that captures the order relations among a collection of unit intervals on the real line. Unit interval orders were introduced by Luce~\cite{rL56} to axiomatize a class of utilities in the theory of preferences in economics. Since then they have been systematically studied (see \cite{DK68, pF85, pF73, FW57, SR03} and references therein). These posets exhibit many interesting properties; for example, they can be characterized as the posets that are simultaneously $({\bf 3}+ {\bf 1})$-free and $({\bf 2} + {\bf 2})$-free. Moreover, it is well known that the number of non-isomorphic unit interval orders on $[n]$ equals $\frac{1}{n+1}\binom{2n}{n}$, the $n$-th Catalan number (see \cite[Section~4]{DK68} or \cite[Exercise~2.180]{rS15}).
	
	In \cite{SR03}, motivated by the desire to understand the $f$-vectors of various classes of posets, Skandera and Reed showed that one can canonically label the elements of a unit interval order from $1$ to $n$ so that its $n \times n$ antiadjacency matrix is totally nonnegative (i.e., has all its minors nonnegative) and its zero entries form a right-justified Young diagram located strictly above the main diagonal and anchored in the upper-right corner. The zero entries of such a matrix are separated from the one entries by a Dyck path joining the upper-left corner to the lower-right corner. Motivated by this observation, we call such matrices \emph{Dyck matrices}. The Hasse diagram and the antiadjacency (Dyck) matrix of a canonically labeled unit interval order are shown in \cref{fig:UIO and its antiadjacency matrix}.
	
	\begin{figure}[h]
		\centering
		\includegraphics[width = 2.8cm]{images/HasseDiagram6} \quad \,
		\includegraphics[width = 1.2cm]{images/MapsToArrow} \quad \quad
		\includegraphics[width = 3.8cm]{images/DyckMatrix6}
		\caption{A canonically labeled unit interval order on the set $\{1,\dots, 6\}$ and its antiadjacency matrix, which exhibits its \emph{semiorder path}, i.e., the Dyck path separating its one entries from its zero entries.}
		\label{fig:UIO and its antiadjacency matrix}
	\end{figure}
	
	On the other hand, it follows from work of Postnikov \cite{aP06} that $n \times n$ Dyck matrices can be regarded as representing rank $n$ \emph{positroids} on the ground set $[2n]$. Positroids, which are special matroids, were introduced and classified by Postnikov in his study of the totally nonnegative part of the Grassmannian \cite{aP06}. He showed that positroids are in bijection with various interesting families of combinatorial objects, including decorated permutations and Grassmann necklaces. Positroids and the nonnegative Grassmannian have been the subject of a great deal of recent work, with connections and applications to cluster algebras \cite{jS06}, soliton solutions to the KP equation \cite{KW14}, and free probability \cite{ARW16}.
	
	In this paper we characterize the positroids that arise from unit interval orders, which we call \emph{unit interval positroids}.  We show that the decorated permutations associated to rank $n$ unit interval positroids are certain 2n-cycles in bijection with Dyck paths of length $2n$. The following theorem is a formal statement of our main result.
	
	\begin{maintheorem*}
		A decorated permutation $\pi$ represents a unit interval positroid on $[2n]$ if and only if $\pi$ is a $2n$-cycle $(1 \ j_1 \ \dots \ j_{2n-1})$ satisfying the following two conditions:
		\begin{enumerate}
			\item in the sequence  $(1, j_1, \dots, j_{2n-1})$ the elements $1,\dots,n$ appear in increasing order while the elements $n+1, \dots, 2n$ appear in decreasing order;
			\item for every $1 \le k \le 2n-1$, the set $\{1, j_1, \dots, j_k\}$ contains at least as many elements of the set $\{1,\dots,n\}$ as elements of the set $\{n+1, \dots, 2n\}$.
		\end{enumerate}
		In particular, there are $\frac{1}{n+1} \binom{2n}{n}$ unit interval positroids on $[2n]$.
	\end{maintheorem*}
	
	The decorated permutation associated to a unit interval positroid on $[2n]$ naturally encodes a Dyck path of length $2n$. Here we provide a recipe to read this decorated permutation directly from the antiadjacency matrix of the unit interval order.
	
	\begin{theorem} \label{thm:reading decorated permutation from Dyck matrix}
		Let $P$ be a canonically labeled unit interval order on $[n]$ and $A$ the antiadjacency matrix of $P$\!. If we number the $n$ vertical steps of the semiorder (Dyck) path of $A$ from bottom to top in increasing order with $\{1,\dots,n\}$ and the $n$ horizontal steps from left to right in increasing order with $\{n+1, \dots, 2n\}$, then we obtain the decorated permutation associated to the unit interval positroid induced by $P$ by reading the semiorder (Dyck) path in northwest direction.
	\end{theorem}
	
	\begin{example} \label{ex:main example}
		The vertical assignment on the left of \cref{fig:visual interpretation of our main result} shows a set $\mathcal{I}$ of unit intervals along with a canonically labeled unit interval order $P$ on $[5]$ describing the order relations among the intervals in $\mathcal{I}$ (see \cref{thm:UIO characterization}). The vertical assignment on the right illustrates the recipe given in \cref{thm:reading decorated permutation from Dyck matrix} to read the decorated permutation $\pi = (1 \ 2 \ 1\! 0 \ 3 \ 9 \ 4 \ 8 \ 7 \ 5 \ 6)$ associated to the unit interval positroid induced by $P$ directly from the antiadjacency matrix. Note that the decorated permutation $\pi$ is a $10$-cycle satisfying conditions (1) and (2) of our main theorem. The solid and dashed assignment signs represent functions that we shall introduce later.
		\vspace{3pt}
		\begin{figure}[h]
			\centering
			\includegraphics[width = 14.8cm]{images/MainPicture}
			\caption{Following the solid assignments: unit interval representation $\mathcal{I}$, its unit interval order $P$, the antiadjacency matrix $\varphi(P)$, and the semiorder (Dyck) path of $\varphi(P)$ showing the decorated permutation $\pi$.}
			\label{fig:visual interpretation of our main result}
		\end{figure}
	\end{example}
	
	
	\vspace{-40pt}
	
	\section{Background and Notation} \label{sec:background}
	
	For ease of notation, when $(P,<_P)$ is a partially ordered set (\emph{poset} for short), we just write $P$, tacitly assuming that the order relation on $P$ is to be denoted by the symbol $<_P$. In addition, every poset showing up in this paper is assumed to be finite.
	
	\begin{definition}
		A poset $P$ is a \emph{unit interval order} provided that there exists a bijective map $i \mapsto [q_i, q_i+1]$ from $P$ to a set $S = \{[q_i, q_i + 1] \mid 1 \le i \le n, \, q_i \in \mathbb{R}\}$ of closed unit intervals of the real line such that for distinct $i,j \in P$, $i <_P j$ if and only if $q_i + 1 < q_j$. We then say that $S$ is an \emph{interval representation} of $P$.
	\end{definition}
	
	For each $n \in \mathbb{N}$, we denote by $\mathcal{U}_n$ the set of all non-isomorphic unit interval orders of cardinality $n$. For nonnegative integers $n$ and $m$, let ${\bf n} + {\bf m}$ denote the poset which is the disjoint sum of an $n$-element chain and an $m$-element chain. Let $P$ and $Q$ be two posets. We say that $Q$ is an \emph{induced} subposet of $P$ if there exists an injective map $f \colon Q \to P$ such that for all $r,s \in Q$ one has $r <_Q s$ if and only if $f(r) <_P f(s)$. By contrast, $P$ is a $Q$-\emph{free} poset if $P$ does not contain any induced subposet isomorphic to $Q$. The following theorem provides a useful characterization of the elements of $\mathcal{U}_n$.
	
	\begin{theorem} \cite[Theorem~2.1]{dS64} \label{thm:UIO characterization}
		A poset is a unit interval order if and only if it is simultaneously $(\bf{3}+\bf{1})$-free and $(\bf{2}+\bf{2})$-free.
	\end{theorem}
	
	For a poset $P$, a bijection $\ell \colon P \to [n]$ is called an $n$-\emph{labeling} of $P$. After identifying $P$ with $[n]$ via $\ell$, we say that $P$ is an $n$-\emph{labeled} poset. The $n$-labeled poset $P$ is \emph{naturally labeled} if $i <_P j$ implies that $i \le j$. \cref{fig:UIO and interval representation} depicts the $6$-labeled unit interval order introduced in \cref{fig:UIO and its antiadjacency matrix} with a corresponding interval representation.
	
	\begin{figure}[h]
		\centering
		\includegraphics[width = 2.6cm]{images/HasseDiagram6} \!\!
		\raisebox{-0.1\height}{\includegraphics[width = 1.2cm]{images/DoubleArrow}} \
		\includegraphics[width = 9.6cm]{images/FloatingIntervalDiagram}
		\caption{A $6$-labeled unit interval order and one of its interval representations.}
		\label{fig:UIO and interval representation}
	\end{figure}
	
	Another useful way of representing an $n$-labeled unit interval order is through its \emph{antiadjacency matrix}.
	
	\begin{definition}
		If $P$ is an $n$-labeled poset, then the \emph{antiadjacency matrix} of $P$ is the $n \times n$ binary matrix $A = (a_{i,j})$ with $a_{i,j} = 0$ if and only if $i \neq j$ and $i <_P j$.
	\end{definition}
	
	Recall that a binary square matrix is said to be a \emph{Dyck matrix} if its zero entries form a right-justified Young diagram strictly above the main diagonal and anchored in the upper-right corner. All minors of a Dyck matrix are nonnegative (see, for instance, \cite{ASW52}). We denote by $\mathcal{D}_n$ the set of all $n \times n$ Dyck matrices. As presented in \cite{SR03}, every unit interval order can be naturally labeled so that its antiadjacency matrix is a Dyck matrix. This yields a natural map $\varphi \colon \mathcal{U}_n \to \mathcal{D}_n$ that is a bijection (see \cref{thm:bijection between UIOs and Dyck matrices}). In particular, $|\mathcal{D}_n|$ is the $n$-th Catalan number, which can also be deduced from the one-to-one correspondence between Dyck matrices and their semiorder (Dyck) paths.
	
	Let $\text{Mat}^{\ge 0}_{d,n}$ denote the set of all full rank $d \times n$ real matrices with nonnegative maximal minors. Given a totally nonnegative real $n \times n$ matrix $A$, there is a natural assignment $A \mapsto \phi(A)$, where $\phi(A) \in \text{Mat}^{\ge 0}_{n,2n}$.
	
	\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}.}
		For an $n \times n$ real matrix $A = (a_{i,j})$, consider the $n \times 2n$ matrix $B = \phi(A)$, where
		\[
			\begin{pmatrix}
				a_{1,1} 		& \dots		 & a_{1,n}     \\
				\vdots 	      & \ddots	   & \vdots     \\
				a_{n-1,1}    & \dots       & a_{n-1,n} \\
				a_{n,1}        & \dots      & a_{n,n}    
			\end{pmatrix} \
			\stackrel{\phi}{\longmapsto} \
			\begin{pmatrix}
				1  	  		&\dots   &  0        &   0  	 & (-1)^{n-1} a_{n,1} & \dots	& (-1)^{n-1} a_{n,n}  \\
				\vdots  &\ddots  &\vdots & \vdots & \vdots 	      			& \ddots & \vdots         			\\
				0  	  		&\dots   &  1        &   0  	 & -a_{2,1}  			& \dots   & -a_{2,n}    		    	\\
				0  	  		&\dots   &  0        &   1  	 & a_{1,1}        			& \dots   & a_{1,n}   
			\end{pmatrix}.
		\]
		Under this correspondence, $\Delta_{I,J}(A) = \Delta_{(n+1 - [n]\setminus I) \cup (n + J)}(B)$ for all $I,J \subseteq [n]$ with $|I| = |J|$ (here $\Delta_{I,J}(A)$ is the minor of $A$ determined by the rows $I$ and columns $J$, and $\Delta_K(B)$ is the maximal minor of $B$ determined by columns $K$).
	\end{lemma}
	
	Using \cref{lem:correspondence between totally nonnegative square and rectangular matrix} and the aforementioned map $\varphi \colon \mathcal{U}_n \to \mathcal{D}_n$, we can assign via $\phi \circ \varphi$ a matrix of $\text{Mat}^{\ge 0}_{n,2n}$ to each unit interval order of cardinality $n$. In turns, every real matrix of $\text{Mat}^{\ge 0}_{n,2n}$ gives rise to a positroid, a special representable matroid which has a very rich combinatorial structure. Let us recall the definition of matroid.
	
	\begin{definition}
		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}$.
	\end{definition}
	
	If $M = (E, \mathcal{B})$ is a matroid, then the elements of $\mathcal{B}$ are said to be \emph{bases} of $M$. Any two bases of $M$ have the same size, which we denote by $r(M)$ and call the \emph{rank} of $M$.
	
	\begin{definition}
		For $d,n \in \mathbb{N}$ such that $d \le n$, let $A \in \text{Mat}^{\ge 0}_{d,n}$ whose columns are denoted by $A_1, \dots, A_n$. The subsets $B$ of $[n]$ such that $\{A_b \mid b \in B\}$ is a basis for the vector space $\mathbb{R}^d$ are the bases of a matroid $M(A)$. Such a matroid is called a \emph{positroid}.
	\end{definition}
	
	Each unit interval order $P$ (labeled so that its antiadjacency matrix is a Dyck matrix) induces a positroid via \cref{lem:correspondence between totally nonnegative square and rectangular matrix}, namely, the positroid represented by the matrix $\phi(\varphi(P))$.
	
	\begin{definition}
		A positroid on $[2n]$ induced by a unit interval order is called \emph{unit interval positroid}.
	\end{definition}
	
	We denote by $\mathcal{P}_n$ the set of all unit interval positroids on the ground set $[2n]$. The function $\rho \circ \phi \circ \varphi \colon \mathcal{U}_n \to \mathcal{P}_n$, where $\rho(B)$ is the positroid represented by $B \in \text{Mat}^{\ge 0}_{n,2n}$, plays a fundamental role in this paper. Indeed, we will end up proving that such a function is a bijection (see \cref{thm:fundamental bijection}).
	
	\vspace{4pt}
	Several families of combinatorial objects, in bijection with positroids, were introduced in \cite{aP06} to study the totally nonnegative Grassmannian, including decorated permutations, Grassmann necklaces, Le-diagrams, and plabic graphs. We use decorated permutations, obtained from Grassmann necklaces, to provide a compact and elegant description of unit interval positroids. In the next definition subindices are considered module $n$.
	
	\begin{definition}
		Let $d,n \in \mathbb{N}$ such that $d \le n$. An $n$-tuple $(I_1, \dots, I_n)$ of $d$-subsets of $[n]$ is called a \emph{Grassmann necklace} of type $(d,n)$ if for every $i \in [n]$ the next 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 $<_i$ on $[n]$ defined by $i <_i \dots <_i n <_i 1 <_i \dots <_i i-1$ is called \emph{shifted linear $i$-order}. For a matroid $M = ([n], \mathcal{B})$ of rank $d$, one can define the sequence $\mathcal{I}(M) = (I_1, \dots, I_n)$, where $I_i$ is the lexicographically minimal ordered basis of $M$ with respect to the shifted linear $i$-order. It was proved in \cite[Section~16]{aP06} that the sequence $\mathcal{I}(M)$ is a Grassmann necklace of type $(d,n)$. We call $\mathcal{I}(M)$ the Grassmann necklace \emph{associated} to $M$. When $M$ is a positroid we can recover $M$ from its Grassmann necklace (see, e.g., \cite{sO11} and \cite{aP06}).
	
	For $i \in [n]$, the \emph{Gale order} on $\binom{[n]}{d}$ with respect to $<_i$ is the partial order $\prec_i$ defined in the following way. If $S = \{s_1 <_i \dots <_i s_d\} \subseteq [n]$ and $T = \{t_1 <_i \dots <_i t_d\} \subseteq [n]$, then $S \prec_i T$ if and only if $s_j <_i t_j$ for each $j\in[d]$.
	
	\begin{theorem}\cite[Theorem~6]{sO11}
		For $d,n \in \mathbb{N}$ such that $d \le n$, let $\mathcal{I} = (I_1, \dots, I_n)$ be a Grassmann necklace of type $(d,n)$. Then
		\[
			\mathcal{B}(\mathcal{I}) = \bigg\{B \in \binom{[n]}{d} \ \bigg{|} \ I_j \prec_j B \ \text{for every} \ j \in [n] \bigg\}
		\]
		is the collection of bases of a positroid $M(\mathcal{I}) = ([n], \mathcal{B}(\mathcal{I}))$, where $\prec_i$ is the Gale $i$-order on $\binom{[n]}{d}$. Moreover, $M(\mathcal{I}(M)) = M$ for all positroids $M$.
	\end{theorem}
	
	Therefore there is a natural bijection between positroids on $[n]$ of rank $d$ and Grassmann necklaces of type $(d,n)$. However, \emph{decorated permutations}, also in one-to-one correspondence with positroids, will provide a more succinct representation.
	
	\begin{definition}
		A \emph{decorated permutation} of $[n]$ is an element $\pi \in S_n$ whose fixed points $j$ are marked either ``clockwise"(denoted by $\pi(j)=\underline{j}$) or ``counterclockwise" (denoted by $\pi(j) = \overline{j}$).
	\end{definition}
	
	A \emph{weak $i$-excedance} of a decorated permutation $\pi \in S_n$ is an index $j \in [n]$ satisfying $j <_i \pi(j)$ or $\pi(j) = \overline{j}$. It is easy to see that the number of weak $i$-excedances does not depend on $i$, so we just call it the number of \emph{weak excedances}.
	
	To every Grassmann necklace $\mathcal{I} = (I_1, \dots, I_n)$ one can associate a decorated permutation $\pi_{\mathcal{I}}$ as follows:
	\begin{itemize}
		\item if $I_{i+1} = (I_i \setminus \{i\}) \cup \{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{itemize}
	The assignment $\mathcal{I} \mapsto \pi_{\mathcal{I}}$ defines a one-to-one correspondence between the set of Grassmann necklaces of type $(d,n)$ and the set of decorated permutations of $[n]$ having exactly $d$ weak excedances.
	
	\begin{prop}\cite[Proposition 4.6]{ARW16}
		The map $\mathcal{I} \mapsto \pi_{\mathcal{I}}$ is a bijection between the set of Grassmann necklaces of type $(d,n)$ and the set of decorated permutations of $[n]$ having exactly $d$ weak excedances.
	\end{prop}
	
	\begin{definition}
		If $P$ is a positroid and $\mathcal{I}$ is the Grassmann necklace associated to $P$, then we call $\pi_{\mathcal{I}}$ the decorated permutation \emph{associated} to $P$.
	\end{definition}

	
	\section{Canonical Labelings on Unit Interval Orders} \label{sec:canonically labelings on UIO}
	
	In this section we introduce the concept of \emph{canonically} labeled poset, and we use it to exhibit an explicit bijection from the set $\mathcal{U}_n$ of non-isomorphic unit interval orders of cardinality $n$ to the set $\mathcal{D}_n$ of $n \times n$ Dyck matrices.
	
	Given a poset $P$ and $i \in P$, we denote the \emph{order ideal} and the \emph{dual order ideal} of $i$ by $\Lambda_i$ and $\text{V}_i$, respectively. The \emph{altitude} of $P$ is the map $\alpha \colon P \to \mathbb{Z}$ defined by $i \mapsto |\Lambda_i| - |\text{V}_i|$. An $n$-labeled poset $P$ \emph{respects} altitude if for all $i,j \in P$, the fact that $\alpha(i) < \alpha(j)$ implies $i < j$ (as integers). Notice that every poset can be labeled by the set $[n]$ such that, as an $n$-labeled poset, it respects altitude.
	
	\begin{definition}
		An $n$-labeled poset is \emph{canonically labeled} if it respects altitude.
	\end{definition}
	
	Each canonically $n$-labeled poset is, in particular, naturally labeled. The next proposition characterizes canonically $n$-labeled unit interval orders in terms of their antiadjacency matrices.
	\vspace{-2pt}
	\begin{prop}\cite[Proposition~5]{SR03} \label{prop:a labeled UIO is canonical if and only if its antiadjacency matrix is Dyck}
		An $n$-labeled unit interval order is canonically labeled if and only if its antiadjacency matrix is a Dyck matrix.
	\end{prop}
	\vspace{-2pt}
	The above proposition indicates that the antiadjacency matrices of canonically labeled unit interval orders are quite special. In addition, canonically labeled unit interval orders have very convenient interval representations.
	
	\begin{prop} \label{prop:interval representations of a canonically labeled UIO}
		Let $P$ be an $n$-labeled unit interval order. Then the labeling of $P$ is canonical if and only if there exists an interval representation $\{[q_i, q_i + 1] \mid 1 \le i \le n\}$ of $P$ such that $q_1 < \dots < q_n$.
	\end{prop}
	
	If $P$ is a canonically $n$-labeled unit interval order, and $\mathcal{I} = \{[q_i,q_i + 1] \mid 1 \le i \le n\}$ is an interval representation of $P$ satisfying $q_1 < \dots < q_n$, then we say that $\mathcal{I}$ is a \emph{canonical} interval representation of $P$.
	
	Note that the image (as a multiset) of the altitude map does not depend on the labels but only on the isomorphism class of a poset. On the other hand, the altitude map $\alpha_P$ of a canonically $n$-labeled unit interval order $P$ satisfies $\alpha_P(1) \le \dots \le \alpha_P(n)$. Thus, if $Q$ is a canonically $n$-labeled unit interval order isomorphic to $P$, then
	\begin{equation} \label{eq:equality of altitude vectors}
		(\alpha_P(1), \dots, \alpha_P(n)) = (\alpha_Q(1), \dots, \alpha_Q(n)),
	\end{equation}
	where $\alpha_Q$ is the altitude map of $Q$. Let $A_P$ and $A_Q$ be the antiadjacency matrices of $P$ and $Q$, respectively. As $\alpha_P(1) = \alpha_Q(1)$, the first rows of $A_P$ and $A_Q$ are equal. Since the number of zeros in the $i$-th column (respectively, $i$-th row) of $A_P$ is precisely $|\text{V}_i(P) - 1|$ (respectively, $|\Lambda_i(P)| - 1$), and similar statement holds for $Q$, the next lemma follows immediately by using \eqref{eq:equality of altitude vectors} and induction on the row index of $A_P$ and $A_Q$.
	
	\begin{lemma} \label{lem:isomorphic canonically labeled UIO have equal Dyck matrix}
		If two canonically labeled unit interval orders are isomorphic, then they have the same antiadjacency matrix.
	\end{lemma}
	
	Now we can define a map $\varphi \colon \mathcal{U}_n \to \mathcal{D}_n$, by assigning to each unit interval order its antiadjacency matrix with respect to any of its canonical labelings. By \cref{lem:isomorphic canonically labeled UIO have equal Dyck matrix}, this map is well defined.
	
	\begin{theorem} \label{thm:bijection between UIOs and Dyck matrices}
		For each natural $n$, the map $\varphi \colon \mathcal{U}_n \to \mathcal{D}_n$ is a bijection.
	\end{theorem}

	
	\section{Description of Unit Interval Positroids} \label{sec:description of UIP}
	
	Now we proceed to describe the decorated permutation associated to a unit interval positroid. Throughout this section $A$ is an $n \times n$ Dyck matrix and $B = (b_{i,j}) = \phi(A)$ is as in \cref{lem:correspondence between totally nonnegative square and rectangular matrix}. We will consider the indices of the columns of $B$ module $2n$. Furthermore, let $P$ be the unit interval positroid represented by $B$, and let $\mathcal{I}_P$ and $\pi^{-1}$ be the Grassmann necklace and the decorated permutation associated to $P$. \\
	
	
	The \emph{set of principal indices} of $B$ is the subset of $\{n+1, \dots, 2n\}$ defined by
	\[
		J = \{j \in \{n+1, \dots, 2n\} \mid B_j \neq B_{j-1}\}.
	\]
	We associate to $B$ the \emph{weight} map $\omega \colon [2n] \to [n]$ defined by $\omega(j) = \max\{i \mid b_{i,j} \neq 0\}$; more explicitly, we obtain that
	\[
		\omega(j) = \twopf{j}{j \in \{1,\dots,n\}}{|b_{1,j}| + \dots + |b_{n,j}|}{j \in \{n+1, \dots, 2n\}.}
	\]
	Since the last row of the antiadjacency matrix $A$ has all its entries equal to $1$, the map $\omega$ is well defined. If $j \in \{n+1,\dots, 2n\}$, then $\omega(j)$ is the number of nonzero entries in the column~$B_j$. Now we find an explicit expression for the function representing the inverse of the decorated permutation associated to $P$.
	
	\begin{prop} \label{prop:explicity function for decorated permutations}
		For $i \in \{1,\dots,2n\}$,
		\[
			\pi(i) = \fivepf{i+1}{n < i < 2n \text{ and } i+1 \notin J}{\omega(i)}{n < i \text{ and either } i = 2n \text{ or } i+1 \in J}{n+1}{i-1}{1 < i \le n \text{ and } \omega(j) \neq i-1 \ \text{for all} \ j \in J}{j}{1 < i \le n \text{ and } \{j\} = J \cap \omega^{-1}(i-1).}
		\]
	\end{prop}
	
	Now we are in a position to prove our main result, which describes the attractive combinatorial structure of the decorated permutation $\pi^{-1}$. The above proposition plays an important role in the (omitted) proof.
	
	\begin{theorem} \label{thm:main result}
		$\pi^{-1}$ is a $2n$-cycles $(1 \ j_1 \ \dots \ j_{2n-1})$ satisfying the next two conditions:
		\begin{enumerate}
			\item in the sequence  $(1, j_1, \dots, j_{2n-1})$ the elements $1,\dots,n$ appear in increasing order while the elements $n+1, \dots, 2n$ appear in decreasing order;
			\item for every $1 \le k \le 2n-1$, the set $\{1, j_1, \dots, j_k\}$ contains at least as many elements of the set $\{1,\dots,n\}$ as elements of the set $\{n+1, \dots, 2n\}$.
		\end{enumerate}
	\end{theorem}

	\section{A Direct Way to Read The Unit Interval Positroid} \label{sec:reading the UIP from the Dyck matrix}
	
	Throughout this section, let $P$ be a canonically $n$-labeled unit interval order with antiadjacency matrix $A$. Also, let $\mathcal{I} = \{[q_i, q_i + 1] \mid 1 \le i \le n\}$ be a canonical interval representation of $P$ (i.e., $q_1 < \dots < q_n$); \cref{prop:interval representations of a canonically labeled UIO} ensures the existence of such an interval representation. In this section we describe a way to obtain the decorated permutation associated to the unit interval positroid induced by $P$ directly from either $A$ or $\mathcal{I}$. Such a description will reveal that the function $\rho \circ \phi \circ \varphi \colon \mathcal{U}_n \to \mathcal{P}_n$ introduced in \cref{sec:background} is a bijection (\cref{thm:fundamental bijection}).
	
	The north and east borders of the Young diagram formed by the nonzero entries of $A$ give a path of length $2n$ we call the \emph{semiorder path} of $A$. Let $B = (I_n | A') = \phi(A)$, where $\phi$ is the map introduced in \cref{lem:correspondence between totally nonnegative square and rectangular matrix}. Let us call \emph{inverted path} of $A$ the path consisting of the south and east borders of the Young diagram formed by the nonzero entries of $A'$. \cref{ex:decorated permutation from Dyck matrices} sheds light upon the statement of the next theorem, which describes a way to find the decorated permutation associated to the unit interval positroid induced by $P$ directly from $A$.
	
	\begin{theorem} \label{thm:decorated permutations from the antiadjacency matrices of UIOs}
		If we number the $n$ vertical steps of the semiorder path of $A$ from bottom to top in increasing order with $\{1,\dots,n\}$ and the $n$ horizontal steps from left to right in increasing order with $\{n+1, \dots, 2n\}$, then we obtain the decorated permutation associated to the unit interval positroid induced by $P$ by reading the semiorder path in northwest direction.
	\end{theorem}
	
	\begin{example} \label{ex:decorated permutation from Dyck matrices}
		The figure below displays the antiadjacency matrix $A$ of the canonically $5$-labeled unit interval order $P$ introduced in \cref{ex:main example} and the matrix $\phi(A)$ both showing their respective semiorder and inverted path encoding the decorated permutation $\pi = (1 \ 2 \ 1\!0 \ 3 \ 9 \ 4 \ 8 \ 7 \ 5 \ 6)$ associated to the positroid induced by $P$.
		\begin{figure}[h]
			\centering
			\includegraphics[width = 3.6cm]{images/MatrixWithSemiorderPath}
			\raisebox{-0.13\height}{\includegraphics[width = 1.6cm]{images/ArrowWithFunction}}
			\includegraphics[width = 6.5cm]{images/MatrixWithInvertedPath}
			\caption{Dyck matrix $A$ and its image $\phi(A)$ exhibiting the decorated permutation $\pi$ along their semiorder path and inverted path, respectively.}
			\label{fig:Dyck matrix showing its semiorder path}
		\end{figure}
	\end{example}
	
	\vspace{-30pt}
	
	The next remark follows immediately.
	
	\begin{remark} \label{rem:Dyck paths specified by decorated permutations}
		The set of $2n$-cycles $(1 \ j_1 \ \dots \ j_{2n-1})$ satisfying conditions (1) and (2) of \cref{thm:main result} is in bijection with the set of Dyck paths of length $2n$.
	\end{remark}

	It is not hard to argue, as a consequence of \cref{thm:decorated permutations from the antiadjacency matrices of UIOs} and \cref{rem:Dyck paths specified by decorated permutations}, that the map $\rho \circ \phi \circ \varphi \colon \mathcal{U}_n \to \mathcal{P}_n$, where $\rho$, $\phi$, and $\varphi$ are as defined in \cref{sec:background} and \cref{sec:canonically labelings on UIO}, is indeed a bijection.
	
	\begin{theorem} \label{thm:fundamental bijection}
		The map $\rho \circ \phi \circ \varphi \colon \mathcal{U}_n \to \mathcal{P}_n$ is a bijection.
	\end{theorem}
	
	\begin{cor}
		The number of unit interval positroids on the ground set $[2n]$ equals the $n$-th Catalan number.
	\end{cor}
	
	We conclude this section describing how to decode the decorated permutation associated to the unit interval positroid induced by $P$ directly from its canonical interval representation $\mathcal{I}$. Labeling the left and right endpoints of the intervals $[q_i, q_i + 1] \in \mathcal{I}$ by $-$ and $+$, respectively, we obtain a $2n$-tuple consisting of pluses and minuses by reading from the real line the labels of the endpoints of all such intervals. On the other hand, we can have another \emph{plus-minus} $2n$-tuple if we replace the horizontal and vertical steps of the semiorder path of $A$ by $-$ and $+$, respectively, and then read it in southeast direction as indicated in the following example.
	
	\begin{example} \label{ex:plus-minus vectors of the semiorder and inverted paths}
		\cref{fig:plus-minus vectors of the semiorder and inverted paths} shows the antiadjacency matrix of the canonically $5$-labeled unit interval order $P$ showed in \cref{ex:main example} and a canonical interval representation of $P$, both encoding the plus-minus $10$-tuple $(-,+,-,-,+,-,+,-,+,+)$, as described in the previous paragraph.
		\begin{figure}[h] \label{fig:plus-minus vectors}
			\centering
			\includegraphics[width = 3.5cm]{images/PlusMinusTuplesMatrix} \
			\includegraphics[width = 1.2cm]{images/DoubleArrow} \
			\includegraphics[width = 7.1cm]{images/PlusMinusTuplesIntervals}
			\caption{Dyck matrix and canonical interval representation of $P$ encoding the $10$-tuple $(-,+,-,-,+,-,+,-,+,+)$.}
			\label{fig:plus-minus vectors of the semiorder and inverted paths}
		\end{figure}
	\end{example}

	\vspace{-35pt}
	
	\begin{lemma} \label{lem:matrix and interval representations of UIO have the same pm-tuple}
		Let $\mathbf{a}_n =(a_1, \dots, a_{2n})$ and $\mathbf{b}_n = (b_1, \dots, b_{2n})$ be the $2n$-tuples with entries in $\{+,-\}$ obtained by labeling the steps of the semiorder path of $A$ and the endpoints of all intervals in $\mathcal{I}$, respectively, in the way described above. Then $\mathbf{a}_n = \mathbf{b}_n$.
	\end{lemma}
	

\cref{lem:matrix and interval representations of UIO have the same pm-tuple} immediately implies our final result.
	
	\begin{theorem} \label{thm:decorated permutations from interval representations of UIOs}
		Labeling the left and right endpoints of the intervals $[q_i, q_i + 1]$ by $n+i$ and $n+1-i$, respectively, we obtain the decorated permutation associated to the positroid induced by $P$ by reading the label set $\{1,\dots, 2n\}$ from the real line from right to left.
	\end{theorem}
	
	
		The diagram below illustrates how to label the endpoints of a canonical interval representation of the $6$-labeled unit interval order $P$ shown in \cref{fig:UIO and its antiadjacency matrix} to obtain the decorated permutation $\pi = (1 \ 1\!2 \ 2 \ 3 \ 1\!1 \ 1\!0 \ 4 \ 5 \ 9 \ 6 \ 8 \ 7)$ of the positroid induced by $P$. 
		\begin{figure}[h]
			\centering
			\includegraphics[width = 10cm]{images/LabeledIntervalDiagram}
			\label{fig:decorated permutation from interval representation}
		\end{figure}

\acknowledgements{While working on this paper, the first author was partially supported by the NSF-AGEP, while the second author was partially supported by the UC Berkeley Department of Mathematics. Both authors are grateful to Lauren Williams for her guidance, Federico Ardila for many helpful suggestions, and Alejandro Morales for the initial question that motivated this project.}

\printbibliography
	
	
\end{document}