# Transversal and Paving Positroids

John Machacek and George D. Nasr  Department of Mathematics, University of
Oregon<EMAIL_ADDRESS>Department of Mathematics, Augustana University
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we study positroids and its overlap with two classes of
matroids: transversal and paving matroids. We exhibit a new class of
fundamental transversal matroids and classify the  $\Gamma$ -diagram for rank
two transversal positroids. We also establish a combinatorial description for
paving positroids in terms of  $\Gamma$ -diagrams.

##  1\. Introduction

Positroids and transversal matroids are two types of real representable
matroids. Paving and sparse paving matroids are two other classes of matroids
that are important in matroid theory. Our focus is a study of the overlap
between these classes of matroids. We will define positroids, transversal
matroids, and (sparse) paving matroids in Section 2, along with other
necessary preliminary information for this paper. Since both transversal
matroids and positroids are real representable matroids this means for either
case there is a matrix with real entries determining these matroids.
Positroids come from real-valued matrices for which all maximal minors are
nonnegative. We will often work with particular a matrix coming from weighted
paths in a planar network. Meanwhile, transversal matroids come from real-
valued matrices with a fixed pattern of zero entries along with “generic”
nonzero entries. On the other hand, (sparse) paving matroids are not typically
representable.

For transversal positroids, Marcott [Mar] has previously worked on determined
when a given transversal matroid has a representation of a positroid. Other
recent related work includes Bonin’s work on the structure of and excluded
minors for positroids [Bon]. This has been followed by the work of Park which
focuses on excluded minors for positroids that are themselves paving matroids
[Par]. In contrast, we will focus on determining which positroids are paving
matroids and developing a criterion for identifying this property amongst
positroids.

It is known that problems of deciding if a matroid is transversal or paving is
a difficult problem [JK82, Theorem 1] in that there is no polynomial time
algorithm to decide if a matroid has one of these two properties using an
independence test oracle. We approach these decision problems and related
questions in the special case of positroids making using of combinatorial
objects that parameterize positroids. One of two natural problems relating
positroids and transversal matroids is as follows.

######  Problem 1.1.

Determine if a given transversal matroid is a postroid.

Marcott has worked on understanding Problem 1.1 and has a conjecture solution
via a noncrossing condition [Mar]. This work of Marcott is motivated by
studying positroid varieties and computations in $\mathcal{N}=4$ SYM theory.
In Theorem 3.6 we connect Marcott’s noncrossing condition to the topological
noncrossing of planar networks used by Postnikov [Pos] to parameterize the
totally nonnegative Grassmannian. We do this by defining what we call
$\Gamma$ $\Gamma$ -diagrams in Definition 3.2 and showing that they define
transversal positroids which satisfy Marcott’s noncrossing in Theorem 3.6. We
also consider the opposite direction of the previously stated problem which is
the positroid version of one of the decision problems mentioned earlier.

######  Problem 1.2.

Determine if a given positroid is a transversal matroid.

In approaching Problem 1.2 one must choose how to represent positroids as
there is a wealth of objects indexing and parameterizing them. We will
primarily work with the  $\Gamma$ -diagrams and  $\Gamma$ -Networks of
Postnikov [Pos]. In Theorem 4.10 we are able to give a simple criterion on the
$\Gamma$ -diagram of a rank $2$ positroid that completely determines if it is
a transversal matroid.

One difficulty in finding a solution to Problem 1.1 or Problem 1.2 is that one
has many different matrices (in fact different vector subspaces) representing
a given matroid. Consider the matrix

$\begin{bmatrix}1&0&-a&-ac\\\ 0&1&b&bc\end{bmatrix}$

for any positive real numbers $a$, $b$, and $c$. One can readily check all
maximal minors are nonnegative. Hence, this matrix defines a positroid. This
positroid is the one index by the diagram in Figure 1. These diagrams and the
construction of the matrix will be explained in Section 2.1, and this
particular diagram will be important to us. Now it turns out this positroid is
also a transversal matroid, but this is not apparent from the matrix above.
Indeed despite four nonzero entries in the third and fourth columns the
corresponding $2\times 2$ minor vanishes meaning the matrix entries are not
“generically” chosen. However, by performing a row operation we obtain

$\begin{bmatrix}1&\frac{a}{b}&0&0\\\ 0&1&b&bc\end{bmatrix}$

from which we can see the matrix is transversal. Here we find no
“coincidental” cancellation in the computation of maximal minors.

centertableaux & ∙
∙ ∙

Figure 1. A  $\Gamma$ -diagram which is not a  $\Gamma$ $\Gamma$ -diagram yet
gives a transversal positroid.

Paving matroids are long been thought to be a “large class” among all matroids
[CR70]. A precise conjecture to this fact has been made [MNWW11, Conjecture
1.6]. Furthermore, the smaller class of sparse paving matroids is also
conjectured to be asymptotically large within all matroids [PvdP15]. In
Theorem 5.8 and Corollary 5.13 we are able to characterize exactly which
positroids are paving and sparse paving respectively in terms of their
$\Gamma$ -diagrams. The characterization uses a collection of inequalities on
an $n$-tuple of nonegative integers which has a direct interpretation as a
$\Gamma$ -diagram defining a paving positroid.

Determining if a given matroid is a paving matroid has to do with considering
with properties of which bases are “missing” (i.e. which bases must be added
to obtain a uniform matroid). In terms of  $\Gamma$ -diagrams this has to do
with which cells are unfilled. The difficulty arises in attempting to find
compatibility amongst unfilled cells. For example, in Figure 2 we see two
$\Gamma$ -diagrams each fitting a $2\times 2$ rectangle with $2$ unfilled
cells, but one corresponds to a paving matroid while the other does not.

centertableaux &
∙ ∙ & ∙
∙

Figure 2. A  $\Gamma$ -diagram of a paving positroid on the left and a
$\Gamma$ -digram of a positroid that is not paving on the right.

In Section 6, we give enumerations of the types of positroid we study in the
earlier sections. For sparse paving positroids, we can give a precise
enumeration and recurrence. In other cases, we give computer-generated counts
that can be used to compare to other enumerations of positroids in the
literature.

At the end of our paper we have two appendices, both of which are important
for the portion of the paper on paving matroids. In Appendix A, we provide an
alternative definition of paving matroids proved by another group of
mathematicians which they never published. In Appendix B, we have an important
result used in the main result on paving positroids. The length and technical
nature of its proof is the reason for its location.

##  2\. Preliminaries

###  2.1. The Grassmannian and positroids

The _(real) Grassmannian_ $\operatorname{Gr}(k,n)$ is the set of
$k$-dimensional subspaces of $\mathbb{R}^{n}$. We may assume $0\leq k\leq n$.
Any element of $V\in\operatorname{Gr}(k,n)$ can be represented by a full rank
$k\times n$ matrix $A$ so that $V$ is the row span of $A$. In this case we
write $V=[A]$ and not that the choice of $A$ in unique up to left
multiplication by elements of the _general linear group_ $GL_{k}$ which
consists of invertible $k\times k$ real matrices.

We set $[n]:=\\{1,2,\dots,n\\}$ and let $\binom{[n]}{k}$ denote the collection
of all $k$-elements subsets of $[n]$. Given $I\in\binom{[n]}{k}$ and a
$k\times n$ matrix $A$, we let $\Delta_{I}(A)$ denote the value of the maximal
minor with columns indexed by $k$. The _totally nonnegative Grassmannin_ is

$\operatorname{Gr}^{\geq
0}(k,n)=\left\\{V\in\operatorname{Gr}(k,n):V=[A]\text{ and }\Delta_{I}(A)\geq
0\text{ for all }I\in\binom{[n]}{k}\right\\}$

as defined by Postnikov [Pos]. This “elementary” setting of total positivity
agrees with the Grassmannian case a more general notion of positivity in Lie
Theory due to Lusztig [Lus98]. Furthermore, it comes with a wealth of related
combinatorial objects as well as connections to other areas including the
physics of $\mathcal{N}=4$ SYM theory (see e.g., [AHBC+16]). We will now
explain a construction due to Postnikov from which we can obtain matrices
representing all possible positroids.

######  Definition 2.1 (Network).

A _planar directed network_ , or simply _network_ , is a planar acyclic111The
acyclic assumption is not necessary, but it is sufficient for our purpose and
lets us not worry about convergence. directed graph $N=(V,E)$ with embedding a
disk so that:

  * •

$[n]\subseteq V$ and the elements of $[n]$ are _boundary vertices_ which embed
on the boundary of the disk in order going clockwise,

  * •

each boundary vertex is designated a source or sink and is incident on at most
one edge,

  * •

each direct edge $e$ comes with a strictly positive real edge weight $w_{e}$.

Note with can have an isolated source or sink. For constructing the matroid is
important to know if an isolated boundary vertex is a source or sink (they
will correspond to coloops and loops respectively). An example network is
shown on the right in Figure 3.

######  Definition 2.2 (Boundary Measurement).

Given a network $N$ with $K\subseteq[n]$ being the set of boundary sources, we
get the $K\times[n]$ _boundary measurement matrix_ of $N$ defined by

$\operatorname{Meas}(N)_{ij}=\sum_{P:i\rightsquigarrow
j}(-1)^{s_{ij}}\prod_{e\in P}w_{e}$

for each $i\in K$ and $j\in N$. Here the $P:i\rightsquigarrow j$ denotes a
path from $i$ to $j$, and $e\in P$ is a directed edge along this path. Note
the acyclic assumption ensures each entry of the matrix is a finite sum. The
value $s_{ij}$ counts the numbers of sources strictly between $i$ and $j$ in
the usual order.

For $i\in K$ we have $\operatorname{Meas}(N)_{ii}=1$ which can be thought of
as coming from the empty path $i\rightsquigarrow i$. This construction is due
to Postnikov who proved that $\operatorname{Meas}(N)$ represents a positroid
and every positroid can be represented by some network [Pos, Theorem 4.8].
There is another object related to positroids we will need which we now
define.

######  Definition 2.3 ( $\Gamma$ -diagram [Pos, Definition 6.1]).

For any partition $\lambda$ we consider its Young diagram in the convention
that our diagrams are left justified with the largest part on top. A _
$\Gamma$ -diagram_ $D$ is a filling of the Young diagram so that each box is
either empty or contains $\bullet$ such that for $i<i^{\prime}$ and
$j<j^{\prime}$ when the box $(i^{\prime},j^{\prime})$ exists it contains
$\bullet$ whenever each the boxes $(i,j^{\prime})$ and $(i^{\prime},j)$
contain $\bullet$. We let $|D|$ denote the number of $\bullet$’s that $D$
contains, and we let $\raisebox{0.0pt}{\scalebox{-1.0}[-1.0]{$\Gamma$}}(k,n)$
denote the collection of all  $\Gamma$ -diagrams that fit inside a
$k\times(n-k)$ box.

A key feature of  $\Gamma$ -diagrams is that they can readily be turned into
networks (see [Pos, Definition 6.3 and Theorem 6.5]). Given
$D\in\raisebox{0.0pt}{\scalebox{-1.0}[-1.0]{$\Gamma$}}(k,n)$ the southeast
boundary of the shape, along with possibly the top and left sides of the box,
give us a lattice path from the top right to bottom left of the box. We will
start in the upper right corner of the $k\times(n-k)$ box and label each step
with an element from $[n]$ in order. Vertical steps are sources and horizontal
steps are sinks. Any $\bullet$ in $D$ is an internal vertex. A directed edge
is given a positive real weight and drawn from right to left from each source
or internal vertex whenever there is an internal vertex to the right in the
same row. Also, a directed edge is drawn down from an internal vertex whenever
there is an internal vertex or sink below in the same column. A weight equal
to $1$ is given to all downward vertical edges.

centertableaux &∙ ∙

∙ ∙ ∙

∙

$1$$2$$3$$4$$5$$6$$7$$c$$a$$d$$f$$b$$e$

Figure 3. A  $\Gamma$ -diagram $D$ (left) and its network $N_{D}$ (right).

######  Example 2.4 ( $\Gamma$ -diagram, network, and boundary measurement).

In Figure 3 we find both a  $\Gamma$ -diagram $D$ on the left and its network
$N_{D}$ on the right. The boundary vertex $7$ plays the role of a sink in this
network since it comes from the horizontal step in the border of the  $\Gamma$
-diagram. The boundary measure matrix is then

$\operatorname{Meas}(N_{D})=\begin{bmatrix}1&0&0&0&a&ab+ae&0\\\
0&1&c&0&-cd&-ced&0\\\ 0&0&0&1&f&0&0\end{bmatrix}$

where the rows are indexed by the boundary vertices $1$, $2$, and $4$.

###  2.2. Matroids

We briefly review matroids and relevant terminology. For more details about
matroid theory, one may see [Oxl11] and [Wel76].

######  Definition 2.5.

Let $E$ be a finite set. A matroid basis system on ground set $E$ is a
nonempty family $\mathcal{B}\subseteq 2^{E}$ of bases satisfying the exchange
axiom: for all distinct $B,B^{\prime}\in\mathcal{B}$ and all $e\in B\setminus
B^{\prime}$, there exists $e^{\prime}\in B^{\prime}\setminus B$ such that
$\left(B\setminus\\{e\\}\right)\cup\\{e^{\prime}\\}\in\mathcal{B}$. The pair
$M=(E,\mathcal{B})$ defines a matroid. We call $E$ the ground set for $M$. Any
subset of a basis is called an independent set. The rank function of $M$ is
defined by $\operatorname{rank}(A)=\max\\{|A\cap B|:\ B\in\mathcal{B}\\}$ for
$A\subseteq E$. The number $\operatorname{rank}(E)$ is called the rank of $M$.

Some additional matroid terminology that will be useful:

  * •

A circuit in a matroid is a minimal dependent subset of $E$. A loop is a
circuit of size 1.

  * •

A flat of $M$ is a subset $F\subseteq E$ such that
$\operatorname{rank}(G)>\operatorname{rank}(F)$ for every $G\supsetneq F$.

  * •

A cyclic flat of a matroid $M$ is a flat of M that is the union of a (possibly
empty) set of circuits. Note that the maximal cyclic flat (the set of non-
coloops) and minimal flat (the set of loops) for $M$ are always cyclic
flats—we refer to these as the trivial cyclic flats.

  * •

The dual of a matroid $M=(E,\mathcal{B})$ is the matroid
$M^{*}:=(E,\mathcal{B}^{*})$ where

$\mathcal{B}^{*}:=\\{E\setminus B:B\in\mathcal{B}\\}.$

  * •

The restriction of $M$ to a set $S\subseteq E$ is a matroid $M|_{S}$, whose
groundset is $S$ and whose bases are the bases of $M$ intersected with $S$.

In general, proving a collection of sets is a matroid base system is no
trivial task, though some examples require less work than others. For an
example, for nonnegative integers $r$ and $n$, the uniform matroid $U_{r}(E)$
on ground set $E$ has basis system $\binom{E}{r}=\\{B\subseteq[n]:\ |B|=r\\}$.
We leave it to the reader to verify this collection of sets indeed satisfies
the exchange axiom. We will often find it more convenient to write
$U_{r,n}:=U_{r}([n])$, where $[n]:=\\{1,2,\dots,n\\}$. If we take $r=|E|$, we
get a matroid whose unique basis is the groundset. We call this the boolean
matroid and denote it $B(E)$.

Given a full rank222It is possible to use any field, and the choice of the
field will affect the matroid. However, in this work, we will always use the
field of real numbers since we are concerned with positivity. $k\times n$
matrix $A$ one can obtain a _linear matroid_ denoted
$M_{A}:=([n],\mathcal{B})$ were $\mathcal{B}\subseteq\binom{[n]}{k}$ consists
of those $k$-element subsets of columns that index nonvanishing maximal minors
of $A$. Equivalently, $\mathcal{B}$ consists of collections of column vectors
from $A$ that form of basis of $\mathbb{R}^{k}$. Linear matroids are also
called _representable matroids_. Note that all positroids are linear matroids.

A _loop_ is an element of a matroid that is not in any basis while a _coloop_
of a matroid is an element of a matroid that is in every basis. We will let
$\hat{M}$ denote the loopless reduction of a matroid which is the original
matroid with all loops removed from the ground set. Also, for a  $\Gamma$
-diagram $D$ with let $\hat{D}$ denote the  $\Gamma$ -diagram associated with
the loopless reduction of the postroid corresponding to $D$ (this  $\Gamma$
-diagram is obtained by deleting all columns that do not contain any
$\bullet$).

###  2.3. Transversal Matroids

Here we define a class matroids central to the focus of this paper. A _set
system_ $(S_{1},S_{2},\dots,S_{k})$ is a family of subsets of some ground set
$E$. A set system may contain repeated sets, that is we may have $S_{i}=S_{j}$
for $i\neq j$. Also, even though they are written as a tuple, we do not
distinguish between rearrangements of a set system. A _transversal_ of a set
system $(S_{1},S_{2},\dots,S_{k})$ is a bijection $\phi:[k]\to I$ so that
$I\subseteq[n]$ and $\phi(j)\in S_{j}$ for all $j\in[k]$. The _transversal
matroid_ $M[(S_{1},S_{2},\dots,S_{k})]$ is the matroid whose bases are the
transversal of the set system $(S_{1},S_{2},\dots,S_{k})$. It is possible that
many set systems give us the same matroid. So, we say that
$M[(S_{1},S_{2},\dots,S_{k})]$ with a given set system is a _presentation_ of
the transversal matroid. It is the case that all transversal matroids are
linear matroids, and they can be represented using a matrix of real numbers
[Oxl11, Corollary 11.2.7].

A _fundamental transversal matroid_ is a transversal matroid
$M[(S_{1},\dots,S_{k})]$ on ground set $E$ that such for each $1\leq i\leq k$
there exists $e\in E$ where $e\in S_{i}$ and $e\not\in S_{j}$ for $j\neq i$.
This is one of many descriptions of fundamental matroids (see e.g., [RI80,
Theorem 4]).

######  Example 2.6.

Every uniform matroid $U_{r,n}$ is a transversal matroid. For instance, we
have

$U_{r,n}=(\underbrace{[n],[n],\dots,[n])}_{r}.$

Another presentation for this matroid is

$U_{r,n}=([1,n-r+1],[2,n-r+2],\dots,[r,n]),$

where for integers $i$ and $j$, we have $[i,j]:=\\{k\in\mathbb{Z}:i<k<j\\}$.

We will be interested in a special subclass of transversal matroids, which we
define now. For each $a\in[n]$ we define the order $<_{a}$ by
$a<_{a}a+1\cdots<_{a}n<_{a}1<_{a}2\cdots<_{a}a-1$ which the simply a cyclic
shift of the usual total order on $[n]$. For $S,T\subseteq[n]$, we say $S$
_crosses_ a set $T$ with there exists $a,b,c,d\in[n]$ such that:

  * (i)

$a<_{a}b<_{a}c<_{a}d$,

  * (ii)

$a,c\in S$ and $a,c\not\in T$,

  * (iii)

$b,d\in T$ and $b\not\in S$.

A set system $(S_{1},S_{2},\dots,S_{k})$ is called _crossing_ if there exisits
$i$ and $j$ so that $S_{i}$ crosses $S_{j}$, otherwise the set system is
called uncrossing.

So far, what we have shown is that, given a presentation, one can produce a
matroids. This may lead one to ask about the converse: Given a matroid $M$,
can one show that it is a transversal matroid? A criterion for this was
determined by Mason [Mas71] and later Ingleton [Ing77] using cyclic flats and
inequalities of ranks. In [BKdM11] a similar characterization of fundamental
transversal matroids was found. We know give a restated formulation of
[BKdM11, Theorem 3.2] and [BKdM11, Theorem 4.1].

######  Theorem 2.7 ([Ing77, Mas71, BKdM11]).

A matroid is transversal if and only if for all nonempty antichains
$\mathcal{F}$ of cyclic flats,

(1)
$\operatorname{rank}(\cap\mathcal{F})\leq\sum_{\mathcal{F}^{\prime}\subseteq\mathcal{F}}(-1)^{|\mathcal{F}^{\prime}|+1}\operatorname{rank}(\cup\mathcal{F}^{\prime}),$

where

$\cap\mathcal{F}=\bigcap_{F\in\mathcal{F}}F.$

Moreover, the matroid is a fundamental transversal matroids if and only if the
above holds with equality for all nonempty antichais for cyclic flats.

Note that when $\mathcal{F}$ is a singleton, both sides of inequality (1) are
equal always. The same is not true in general when $\mathcal{F}$ is not a
singleton.

###  2.4. Paving and sparse paving matroids

A matroid of rank $r$ is called _paving_ if every circuit has cardinality
greater than or equal to $r$, and it is _sparse paving_ if it and its dual are
both paving. Paving matroids are well-known objects to matroid theorists
[Wel76, Chapter 2,3]. It is conjectured and widely believed that
asymptotically all matroids are paving matroids, or even sparse paving
matroids; see [MNWW11], [PvdP15], [Oxl11, Chapter 15.5]. The case of sparse
paving matroids was historically of particular interest due to the following
result.

######  Lemma 2.8.

[Oxl11, Prop.1.5.14] Let $C$ be a circuit-hyperplane, that is, a set that is
both a circuit and a hyperplane. If $C$ is a circuit-hyperplane, then the
family $\mathcal{B}\cup\\{C\\}$ is in fact a matroid basis system, called the
relaxation of $M$ at $C$.

In particular, this leads to an alternative definition of sparse paving
matroids: a matroid which, after relaxing all circuit-hyperplanes, yields a
uniform matroid.

Recently, the notion of relaxation was generalized to from circuit-hyperplanes
to something called “stressed-subsets” in [FS22]. This operation allows one to
define a class of matroids called elementary split matroids in an analogous
way to how the original relaxation operation corresponds to sparse paving
matroids. Elementary split matroids—which contain the class of paving
matroids—are outside the scope of this paper. Thus we look at the special case
where their generalized relaxation operation are specialized to work best with
paving matroids. This case was first established in [FNV22], which we expand
on now.

######  Definition 2.9.

[FNV22, Def. 3.1] A hyperplane $H$ of $M$ is a _stressed hyperplane_ if every
subset of $H$ of size $r$ is a circuit.

Note that every circuit-hyperplane is stressed. Stressed hyperplanes are a
special example of cyclic flats.

Moreover, stressed hyperplanes are intimately connected with paving matroids:

######  Proposition 2.10.

[FNV22, Prop. 3.16] A matroid is a paving matroid if and only if every
hyperplane is stressed.

Compare this result with [Oxl11, Prop. 2.1.21]: a family $\mathcal{H}$ of
subsets of $E$, all of size at least $r-1$, is the set of hyperplanes of a
paving matroid of rank $r$ if and only if each $(r-1)$-subset of $E$ is
contained in exactly one element of $\mathcal{H}$. In the Appendix, we will
provide another useful way of classifying paving matroids. For now, though, we
finally discuss the generalized relaxation operation that we will rely on in
this paper.

######  Definition 2.11.

[FNV22, Theorem 1.2] Let $H\subseteq E$ be a stressed hyperplane of a rank $r$
matroid $M=(E,\mathcal{B})$. Then

$\widetilde{M}=\left(E,\mathcal{B}\cup{H\choose r}\right)$

is a matroid, which we call the _relaxation of $H$ in $M$_.

When $H$ is a circuit-hyperplane, note that we recover the original notion of
relaxation from [Oxl11]. Further, as we would hope, we have the following.

######  Proposition 2.12.

[FNV22, Thm. 1.2] If $H$ is a stressed hyperplane of a matroid $M$, then $H$
can be relaxed.

When $H$ is a circuit-hyperplane, the relaxation of $M$ at $H$ coincides with
the usual notion of a relaxation as in [Oxl11, Section 1.5].

##  3\. A class of fundamental transversal positroids

Given any vector $v=(v_{1},\dots,v_{n})\in\mathbb{R}^{n}$ we have its
_support_ given by

$\operatorname{supp}(v):=\\{i:v_{i}\neq 0\text{ and }1\leq i\leq n\\}$

which simply consists of the indices of nonzero entries of the vector. For a
$k\times n$ matrix $A$ be rows $r_{i}\in\mathbb{R}^{n}$ for $1\leq i\leq k$ we
define

$\operatorname{supp}(A):=(\operatorname{supp}(r_{1}),\operatorname{supp}(r_{2}),\dots,\operatorname{supp}(r_{k}))$

and obtain a set system.

######  Lemma 3.1.

If $N\in\operatorname{Net}(k,n)$, then
$\operatorname{supp}\left(\operatorname{Meas}(N)\right)$ is noncrossing.

$a$$b$$c$$d$$S_{i}$$a=S_{i}$$b$$c$$d$ Figure 4. Situations used in proof of
Lemma 3.1 that prevent crossings in set systems coming from supports of
boundary measurement matrices.

###### Proof.

Take $N\in\operatorname{Net}(k,n)$ and let $A=\operatorname{Meas}(N)$ with
rows $r_{i}\in\mathbb{R}^{n}$ for $1\leq i\leq k$. Assume that
$\operatorname{supp}(A)$ has a crossing so that $\operatorname{supp}(r_{i})$
crosses $\operatorname{supp}(r_{j})$ for some $i$ and $j$. This means there
exists to that

$\displaystyle a,c\in\operatorname{supp}(r_{i})$ $\displaystyle
b,d\in\operatorname{supp}(r_{j})$ $\displaystyle
b\not\in\operatorname{supp}(r_{i})$ $\displaystyle
a,c,\not\in\operatorname{supp}(r_{j})$

where $a<_{a}b<_{a}<c<_{a}d$.

Let $S_{i}$ and $S_{j}$ be the sources indexing the rows $r_{i}$ and $r_{j}$
respectively. This means we must have paths $S_{i}\rightsquigarrow a$ and
$S_{i}\rightsquigarrow c$. In could be the case that both $a$ and $c$ are
sinks which is shown on the left of Figure 4. Here the placement of $S_{1}$
can vary, but the fact that there is a continuous (undirected) curve from $a$
to $c$ will not change. Indeed we may always choose a path
$S_{i}\rightsquigarrow a$ and a path $S_{i}\rightsquigarrow c$ which begin
overlapping at $S_{1}$ then eventually diverge (if they intersect after
diverging we can simply follow an overlapping portion for longer).
Alternatively one of $a$ or $c$ could be a source. This situation where $a$ is
a source is shown on the right of Figure 4.

We find in any case we cannot have $S_{j}\rightsquigarrow b$ and
$S_{j}\rightsquigarrow d$ without have a path departing from $S_{j}$ intersect
the (undirected) continuous curve between $a$ and $c$. Such on intersection
would force a path $S_{j}\rightsquigarrow a$ or $S_{j}\rightsquigarrow c$.
This is a contradiction to our assumption by $\operatorname{supp}(r_{i})$
crossing $\operatorname{supp}(r_{j})$. Therefore $\operatorname{supp}(A)$ must
be noncrossing the the lemma is proven. ∎

centertableaux &
$d$ $a$

$c$ $b$

Figure 5. Example conditions for  $\Gamma$ -diagrams and  $\Gamma$ $\Gamma$
-diagrams. When boxes labeled $a$ and $c$ are each nonempty, then to be a
$\Gamma$ -diagram the box labeled $b$ must be nonempty. When boxes labeled
$a$, $b$, and $c$ are all nonempty to be a  $\Gamma$ $\Gamma$ -diagram the box
labeled $d$ also must be nonempty.

######  Definition 3.2 ( $\Gamma$ $\Gamma$ -diagram).

For any partition $\lambda$ we consider its Young diagram in the convention
that our diagrams are left justified with the largest part on top. A _
$\Gamma$ $\Gamma$ -diagram_ $D$ is a  $\Gamma$ -diagram with the additional
requirement that for $i<i^{\prime}$ and $j<j^{\prime}$ the box $(i,j)$
contains $\bullet$ whenever each the boxes $(i,j^{\prime})$, $(i^{\prime},j)$,
and $(i^{\prime},j^{\prime})$ contain $\bullet$. Note the condition that
$(i^{\prime},j^{\prime})$ contains a $\bullet$ implies this box must exist. We
let $\raisebox{0.0pt}{\scalebox{-1.0}[-1.0]{$\Gamma$}}\hbox
to0.0pt{\hss$\Gamma$\hskip 0.56917pt}(k,n)$ denote the collection of all
$\Gamma$ $\Gamma$ -diagrams that fit inside a $k\times(n-k)$ box.

The collection of  $\Gamma$ $\Gamma$ -diagrams is of course smaller than the
collection of all  $\Gamma$ -diagrams. However, there are many  $\Gamma$
$\Gamma$ -diagrams including infinite families which are of interest. The
following example shows the occurrence of certain  $\Gamma$ $\Gamma$ -diagrams
in the study of the amplituhedron.

######  Example 3.3 ($m=2$ amplituhedron cells).

A set  $\Gamma$ -diagrams which turn out to in fact be  $\Gamma$ $\Gamma$
-diagrams was given in [KWZ20] (see also [AHTT18]) to index full dimensional
cells in a “triangulation333In the physics literature triangulation means a
disjoint collection which covers a dense subset.” of the $m=2$ amplituhedron
[EZLT]. For a $k\times(n-k)$ box the  $\Gamma$ $\Gamma$ -diagrams in the
indexing set are of shape $\lambda=(\lambda_{1},\dots,\lambda_{k})$ for
$\lambda_{i}\geq 2$ for $1\leq i\leq k$. Then boxes $(j,1)$ and
$(j,\lambda_{j})$ contain a $\bullet$ for $1\leq j\leq k$ and all other boxes
are empty. The diagrams for $n=6$ and $k=3$ are shown in Figure 6.

centertableaux ∙& ∙
∙ ∙
∙ ∙ ∙& ∙
∙ ∙
∙ ∙ ∙& ∙
∙ ∙
∙ ∙ ∙& ∙
∙ ∙
∙ ∙

Figure 6. Diagrams for top dimensional cells in $m=2$ amplituhedron for $n=6$
and $k=3$ from [KWZ20].

The following lemma was proven in [AF23], but we will give an alternative
proof. A key feature of the boundary measurement matrix is that the maximal
minors (i.e. Plücker coordinates) are subtraction-free rational expressions as
originally proven by Postnikov [Pos, Theorem 4.11] (see also [Tal08, Mac18]).
We will use a case444The formula works more generally for networks with
directed cycle, but we state this simpler version which will be sufficient for
us. of Talaska’s formula [Tal08, Corollary 4.3] that states for
$N\in\operatorname{Net}(k,n)$ which has no directed cycles and $J\subseteq[n]$
with $|J|=k$ we have

(2)
$\Delta_{J}(\operatorname{Meas}(N))=\sum_{F\in\mathcal{A}_{J}(N)}2^{\theta(N)}\operatorname{wt}(F)$

where $\theta(F)\geq 0$ is an integer and $\mathcal{A}_{J}(N)$ is the
collection of alternating flows we will define presently. An _alternating flow
terminating at $J$_ is a collection $(P_{1},P_{2},\dots,P_{k})$ so that
$P_{i}$ starting at the $i$th source, each vertex of $J$ has one path that
terminates at it, and at each interior vertex the edges from
$(P_{1},P_{2},\dots,P_{k})$ incident to it alternate in orientation when
moving clockwise around the vertex. We set
$\operatorname{wt}(F):=\prod_{i=1}^{k}\operatorname{wt}(P_{i})$ where
$F=(P_{1},P_{2},\dots,P_{k})$. Also, let $\mathcal{F}_{J}(N)$ denote the set
_flows_ terminating at $J$ which is the collection of all alternating flows
such that the paths pairwise have no vertices in common. Here will allow
$P_{i}$ to be the empty path which has weight equal to $1$ and terminates at
the $i$th. If $J$ has a flow terminating at $J$ we say $J$ is _realized by a
disjoint path system_.

######  Lemma 3.4 ([AF23, Theorem 2.14]).

A subset $J\subseteq[n]$ is a base in the positroid associated with some
$D\in\raisebox{0.0pt}{\scalebox{-1.0}[-1.0]{$\Gamma$}}(k,n)$ if and only if
there is a flow terminating at $J$ in the  $\Gamma$ -network $N_{D}$. In
particular, the bases are exactly the $k$-element subsets of $[n]$ realized by
a disjoint path system.

###### Proof.

From Equation (2) we see that $\Delta_{J}(N_{D})$ is nonzero if and only if
there is an alternating flow terminating at $J$. If there is no alternating
flow, then by definition there is no flow either. We must show that if there
is an alternating flow, then it must actually be a flow by considering how
$\Gamma$ -networks are constructed. Consider an alternating flow which is not
a flow. Then two paths must have a first meeting place. At this vertex, a path
enters from the top while another enters from the right (with no edges in
between them) which is a contradiction to the alternating orientation. Hence,
every alternating flow must be a flow in a  $\Gamma$ -network and the lemma is
proven. ∎

######  Lemma 3.5.

If $N\in\operatorname{Net}(k,n)$, then
$M[\operatorname{supp}(\operatorname{Meas}(N))]$ is a fundamental transversal
matroid.

###### Proof.

Take $N\in\operatorname{Net}(k,n)$ and let
$\operatorname{supp}(\operatorname{Meas}(N))=(S_{1},S_{2},\dots,S_{k})$. Let
$a\in[n]$ be the $i$th source of $N$, then $a\in S_{i}$ and $a\not\in S_{j}$
for $j\neq i$. It follows that
$M[\operatorname{supp}(\operatorname{Meas}(N))]$ is a fundamental transversal
matroid. ∎

flipflip Figure 7. Flips used to remove an intersection.

######  Theorem 3.6.

If $D\in\raisebox{0.0pt}{\scalebox{-1.0}[-1.0]{$\Gamma$}}\hbox
to0.0pt{\hss$\Gamma$\hskip 0.56917pt}(k,n)$, then the postroid
$M_{\operatorname{Meas}(N_{D})}$ is a fundamental transversal matroid
satisfying

$M_{\operatorname{Meas}(N_{D})}=M[\operatorname{supp}(\operatorname{Meas}(N_{D}))]$

where $\operatorname{supp}(\operatorname{Meas}(N_{D}))$ is a noncrossing
minimal presentation.

###### Proof.

Let $N=N_{D}$ for some
$D\in\raisebox{0.0pt}{\scalebox{-1.0}[-1.0]{$\Gamma$}}\hbox
to0.0pt{\hss$\Gamma$\hskip 0.56917pt}(k,n)$ and take $J\subseteq[n]$ with
$|J|=k$. By Lemma 3.4 $J$ is a base of the positriod represented by
$\operatorname{Meas}(N)$ if and only if there is flow in $N$ terminating at
$J$. Also, $J$ in a base of the transversal matroid presented by
$\operatorname{supp}(\operatorname{Meas}(N))$ if and only if there is a
collection of paths $(P_{1},P_{2},\dots,P_{k})$ terminating at $J$ (with no
conditions on being on flow). So, we must show that if in $N$ there exists a
collection of paths $(P_{1},P_{2},\dots,P_{k})$ with $P_{i}$ starting at the
$i$th source and each member of $J$ having a path terminating at it, then
there exists a flow in $N$ terminating at $J$.

Let $(P_{1},P_{2},\dots,P_{k})$ be such a collection of paths terminating at
$J$. If two paths intersect they must first meet at a vertex with one path
coming from above and the other coming from the right. Then the two may be
identical for some time, but they must eventually diverge because no two paths
in the collection terminate in the same place. Now pick two paths that
intersect so that the vertex they first meet in as far to the bottom right on
the $k\times(n-k)$ box our  $\Gamma$ $\Gamma$ -diagram lives inside. It is
then possible to perform an operation on the two paths which “flips” portions
of the paths to remove this intersection. Two cases of this operation are
shown in Figure 7 where this figure only shows the relevant portion of the
paths near the intersection vertex. There can be vertices present in the
$\Gamma$ $\Gamma$ -network that are not explicitly shown in the figure (i.e.
there can be vertices between the change of direction which are not important
to us). However, starting with the vertices on the paths the existence each
other vertex shown is implied by the definition of a  $\Gamma$ $\Gamma$
-diagram.

There are four cases depending on whether the solid blue path diverges from
the red by taking a horizontal or vertical step. Also, the paths may agree by
either first going downward or first going left. The unpictured cases are
analogous to those shown in Figure 7. In any case new edges arising, hence any
new intersections, from the operation are strictly on the above left side of
the diagram the intersection we started with is. So, we can find a flow
terminating at $J$ by iterating this operation.

We have shown that
$M_{\operatorname{Meas}(N_{D})}=M[\operatorname{supp}(\operatorname{Meas}(N_{D}))]$.
By Lemma 3.1 we know that $\operatorname{supp}(\operatorname{Meas}(N_{D}))$ is
noncrossing. Also, by Lemma 3.5 we find that
$M_{\operatorname{Meas}(N_{D})}=M[\operatorname{supp}(\operatorname{Meas}(N_{D}))]$
is a fundamental transversal matroid. Since $N$ is a  $\Gamma$ $\Gamma$
-network a source $i$ is connected to a sink $j$ if and only if $D$ has
$\bullet$ is the row corresponding to source $i$ in the position corresponding
the column of sink $j$. So, $|D|$ is to equal the number of nonzero entries in
$\operatorname{Meas}(N_{D})$ minus $k$. We know that $|D|$ is the dimension of
the space parameterized by the  $\Gamma$ -network $N_{D}$. By [KLS13, Theorem
5.9] we obtain that $|D|=\dim(\Pi_{D})$. Let
$\mathcal{S}=(S_{1},S_{2},\dots,S_{k})=\operatorname{supp}(\operatorname{Meas}(N_{D}))$,
then by [Mar, Theorem 4.1] we see that $|D|=\dim(L(\mathcal{S}))$ because
$M_{\operatorname{Meas}(N_{D})}=M[\operatorname{supp}(\operatorname{Meas}(N_{D}))]$
is a positroid. Now we have that

$|D|=-k+\sum_{i=1}^{k}|S_{i}|$

from which it follows that $\operatorname{supp}(\operatorname{Meas}(N_{D}))$
is a minimal presentation by using [Mar, Theorem 3.2]. ∎

##  4\. Rank 2 Transversal Positroids

Throughout this section, we only consider rank two positroids. That is, we
will be dealing with  $\Gamma$ -diagrams $D$ which have at most two rows
inside $2\times(n-2)$ rectangle. See Figure 8 for an example.

∙& ∙ ∙ ∙ ∙

∙ ∙ ∙ ∙∙

Figure 8. An example of a rank $2$ $\Gamma$ -diagram.

In this section, we will be consistently translating between  $\Gamma$
-diagrams, their networks, and the measurement of their network. We use the
start of this section to set up notation and terminology which will aid in our
ability to write more concise proofs. We will use $s_{1}$ and $s_{2}$ for the
sources of $N_{D}$ and $t_{1}$, $t_{2}$, $\dots$, $t_{n-2}$ be the sinks of
$N_{D}$ achieved by labeling the  $\Gamma$ -diagram along the along the
southeast boundary as in Figure 9 below.

∙& ∙ ∙ ∙ ∙

∙ ∙ ∙ ∙∙
$s_{1}$$s_{2}$$t_{1}$$t_{2}$$t_{3}$$t_{4}$$t_{5}$$t_{6}$$t_{7}$$t_{8}$$t_{9}$$t_{10}$

Figure 9. The labels for sources and sinks of the network corresponding to the
$\Gamma$ -diagram in Figure 8.

All other vertices in $N_{D}$ will be labeled $x_{r,c}$ when they correspond
to the filled position of $D$ which is to the left of $s_{r}$ and above
$t_{c}$. For instance, the network for the  $\Gamma$ -diagram in Figure 9 is
drawn below in Figure 10. Note we have also assigned weights to our edges,
using $a_{i}$ for the edges in row 1 in $b_{i}$ for edges in row 2, which will
be needed for computing the boundary measurement of the network.

$x_{1,10}$$x_{2,9}$$x_{1,8}$$x_{2,8}$$x_{2,6}$$x_{2,5}$$x_{2,4}$$x_{1,4}$$x_{1,3}$$x_{1,1}$$s_{1}$$s_{2}$$t_{1}$$t_{2}$$t_{3}$$t_{4}$$t_{5}$$t_{6}$$t_{7}$$t_{8}$$t_{9}$$t_{10}$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a_{5}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{5}$
Figure 10. The network for the diagram labeled in Figure 9.

One may notice that Figure 10 has two sinks, $t_{2}$ and $t_{7}$ which are not
connected to the rest of the network. Note that the corresponding columns in
Figure 9 contain no $\bullet$’s in them. This corresponds to a matroid where
$t_{2}$ and $t_{7}$ are loops. Note that if $L$ is the set of loops for a
matroid $M$ on the ground set $[n]$ and rank $r$, we have that
$M=U_{0}(L)\oplus M|_{[n]\setminus L}$. The  $\Gamma$ -diagram for this
matroid is precisely the  $\Gamma$ -diagram of $M$ with the columns
corresponding to the elements of $L$ removed. Thus, we may reduce our
arguments to the case where $M$ is loopless. It is worth further noticing that
the bases of $M$ and $M|_{[n]\setminus L}$ are equal, as loops appear in no
basis, so structurally the two matroids are nearly identical. In this case, we
call $M|_{[n]\setminus L}$ the _loopless reduction_ of $M$. We will also apply
the term loopless reduction to  $\Gamma$ -diagrams, and an example of a
loopless reduction of a  $\Gamma$ -diagram is shown in Figure 11. In this
section, we will frequently work in the loopless situation because it will
simplify the definition of some statistics we need on  $\Gamma$ -diagrams.
There is no loss of generality since a matroid is transversal if and only if
its loopless reduction is transversal. Indeed, one can look at the
characterization in Theroem 2.7 of notice the loops do not affect the
structure of the lattice of cyclic flats.

∙& ∙ ∙ ∙ ∙

∙ ∙∙ ∙∙

Figure 11. The loopless reduction of the  $\Gamma$ -diagram in Figure 8.

In this section, we will often be interested only in particular columns on the
boundary measurement matrix, and hence only interested in particular vertices
of a given network. However, when computing the boundary measurement, it is
important to keep track of the weights. We let $w_{i,j}$ be the accumulated
weight starting from the sources and ending at $x_{i,j}$. This allows us to
draw simplified versions of our networks while not losing the relevant weight
information of the ambient graph. For instance, if we were only interested in
studying vertices $x_{1,8}$, $x_{2,8}$, $x_{2,9}$ from the network in Figure
10, along with the relevant sources and sinks, we may draw the simplified
graph in Figure 12.

$x_{2,9}$$x_{1,8}$$x_{2,8}$$s_{1}$$s_{2}$$t_{8}$$t_{9}$$(w_{1},w^{\prime}_{1})$$w_{2}$$b_{5}$
Figure 12. A simplified network schematic corresponding to $x_{1,8}$,
$x_{2,8}$, and $x_{2,9}$, along with the relevant sources and sinks, from the
network in Figure 9.

The dashed edges with weights are meant to signify the cumulative weight of
paths in the original network drawing. Note also vertical edges are suppressed
when their incidences are not explicitly present. The pair of weights of the
form $(w,w^{\prime})$ are such that $w$ is the total weight of all paths to
the vertex below while $w^{\prime}$ is the total weight to the vertex. Notice
$w^{\prime}$ will always be a term in $w$, and this drawing convention allows
to again assume the weight of all downward vertical edges is $1$. For
instance, using Figures 10 and 12,
$w_{1}=a_{1}a_{2}a_{3}(a_{4}+b_{2}b_{3}b_{4})$ and
$w_{2}=b_{1}b_{2}b_{3}b_{4}$ while $w^{\prime}_{1}=a_{1}a_{2}a_{3}a_{4}$.

This is not quite the induced subgraph on the corresponding vertices. Rather,
it is more of a schematic that shows us most of the relevant information. The
utility of this is that it allows us to study the columns of
$\operatorname{Meas}(N_{D})$ corresponding to some chosen sinks. In the case
of Figure 12, $t_{8}$ and $t_{9}$. For instance, the corresponding columns for
the above network is

$\begin{bmatrix}-w_{1}&-w_{1}b_{5}\\\ w_{2}&w_{2}b_{5}\end{bmatrix}.$

Here $w^{\prime}_{1}$ was not directly used in computing the boundary
measurement, but for other examples, it can be necessary to keep track of the
weight along the top row of the  $\Gamma$ -network.

This is all the notation needed for us to proceed with the main ideas of this
section. First, we define a special type of le diagram.

######  Definition 4.1.

For $i\geq 1$, let $\mathcal{L}(i)$ be the following Ferrer’s diagram, where
$i$ is the number of columns with one $\bullet$ in them.

&

∙∙ ∙ $\cdots$ & ∙

∙ ∙∙

######  Definition 4.2.

Let $L$ be a  $\Gamma$ -diagram. We say that $L^{\prime}$ is an contiguous
subdiagram of $L$ if one can find a copy of $L^{\prime}$ in $L$ where
$L^{\prime}$ is realized the taking consecutive columns in $L$.

For example, the  $\Gamma$ -diagram in Figure 8 has $\mathcal{L}(1)$ and
$\mathcal{L}(2)$ as contiguous subdiagrams. The definition for
$\mathcal{L}(i)$ and contiguous subdiagrams as well as the next lemma
illustrate why we wish to restrict to loopless  $\Gamma$ -diagrams. If we
allow for columns corresponding to loops we have to account for these loop
columns being inside an $\mathcal{L}(i)$ without changing the span of the
columns on the $\mathcal{L}(i)$ subdiagram. Thus avoiding loops allows for
cleaner bookkeeping.

######  Lemma 4.3.

Let $D$ be a  $\Gamma$ -diagram with network $N$. If $D$ contains
$\mathcal{L}(i)$ as a contiguous subdiagram, then the columns in
$\operatorname{Meas}(N_{D})$ corresponding to $\mathcal{L}(i)$ are spanned by
a single vector.

###### Proof.

The part of $N_{D}$ corresponding to $\mathcal{L}(i)$ looks like the
following. That is, the columns of $\mathcal{L}(i)$ are above the sinks
labeled $t_{j}$, $t_{j+1}$, $\dots$, $t_{j+i}$ for some $j$.

$x_{2,j+i}$$x_{2,j+1}$$\cdots$$x_{1,j}$$x_{2,j}$$s_{1}$$s_{2}$$t_{j}$$t_{j+1}$$t_{j+i}$$b_{i}$$b_{2}$$b_{1}$$(w_{1},w^{\prime}_{1})$$w_{2}$

Then the columns of $\operatorname{Meas}(N_{D})$ corresponding to the sinks
$t_{j}$, …, $t_{j+i}$ are described by the following matrix

$\begin{bmatrix}-w_{1}&-w_{1}b_{1}&-w_{1}b_{1}b_{2}&\cdots&-w_{1}b_{1}b_{2}\cdots
b_{i}\\\ w_{2}&w_{2}b_{1}&w_{2}b_{1}b_{2}&\cdots&w_{2}b_{1}b_{2}\cdots
b_{i}\\\ \end{bmatrix}$

where we can readily observe that all columns are multiples of the first
column. Notice $w^{\prime}_{1}$ does not appear in
$\operatorname{Meas}(N_{D})$ because all paths in our picture passing through
$x_{1,j}$ must also pass through $x_{2,j}$. ∎

######  Lemma 4.4.

Suppose a  $\Gamma$ -diagram $D$ has the following contiguous subdiagram

∙
∙ $\cdots$ ∙
∙

$t_{i}$ $t_{j}$

where columns $t_{j+1}$ through $t_{i-1}$ can be filled in anyway respecting
the  $\Gamma$ -condition, then columns corresponding to $t_{i}$ and $t_{j}$ in
$M$ are linearly independent.

This lemma is useful as it yields the following statement.

######  Corollary 4.5.

If a  $\Gamma$ -diagram $L$ contains two disjoint contiguous subdiagrams
$\mathcal{L}(i_{1})$ and $\mathcal{L}(i_{2})$, then a column vector in
$\operatorname{Meas}(N_{D})$ corresponding to any column of
$\mathcal{L}(i_{1})$ is not a scalar multiple of a column vector corresponding
to any column of $\mathcal{L}(i_{2})$.

###### Proof of Lemma 4.4..

The induced subnetwork of $N$ on the vertices $s_{1}$, $s_{2}$, $t_{i}$,
$t_{j}$ is the following.

$x_{2,i}$$x_{1,i}$$x_{1,j}$$x_{2,j}$$s_{1}$$s_{2}$$t_{j}$$t_{i}$$(w_{1},w_{1}^{\prime})$$(w_{2},w_{2}^{\prime})$$w_{3}$$w_{4}$

The column in $M$ corresponding to $t_{j}$ is thus $\begin{bmatrix}-w_{1}\\\
w_{3}\end{bmatrix}$. The column in $M$ corresponding to $t_{i}$ is

$\begin{bmatrix}-w^{\prime}_{1}w_{2}-(w_{1}-w^{\prime}_{1})w_{4}\\\
w_{3}w_{4}\end{bmatrix},$

To see the columns are not multiples of each other it remains to show that
$-w^{\prime}_{1}w_{2}-(w_{1}-w^{\prime}_{1})w_{4}\neq-w_{1}w_{4}$. We first
observe that $w_{4}$ must be a term in $w_{2}$ since $w_{2}$ records all paths
from $x_{1,j}$ to $x_{2,i}$ and going straight down then left is one such
path. So, we may write $w_{2}=w_{4}+x$ for some $x$ recording all paths from
$x_{1,j}$ to $x_{2,i}$ that begin by moving left. We then have

$-w^{\prime}_{1}w_{2}-(w_{1}-w^{\prime}_{1})w_{4}=-w^{\prime}_{1}(w_{4}+x)-(w_{1}-w^{\prime}_{1})w_{4}=-w_{1}w_{4}-w^{\prime}_{1}x\neq-
w_{1}w_{4}$

since $w^{\prime}_{1}x\neq 0$ by the assumption on the form of the  $\Gamma$
-diagram. Therefore the lemma is proven. ∎

######  Lemma 4.6.

Suppose a loopless  $\Gamma$ -diagram $D$ has the following as a subdiagram

∙
or  ∙

then the corresponding column in $\operatorname{Meas}(N_{D})$ is spanned by
$\begin{bmatrix}1\\\ 0\end{bmatrix}$.

Similarly, if $D$ has

∙

as a subdiagram, which is not contained in a contiguous subdiagram of the form
$\mathcal{L}(i)$ for some integer $i$, then the corresponding column of
$\operatorname{Meas}(N_{D})$ is spanned by $\begin{bmatrix}0\\\
1\end{bmatrix}$.

###### Proof.

The proofs of all cases are similar, let us first consider the case
corresponding to the following.

∙

Suppose this appears above source $t_{j}$. Then the corresponding subdiagram
for $N_{D}$ involving $x_{1,j}$, $t_{j}$, and $s_{1}$ is the following.

$x_{1,j}$$s_{1}$$t_{j}$$w_{1}$

Then the column of $M$ corresponding to $t_{j}$ is $\begin{bmatrix}-w_{1}\\\
0\end{bmatrix}$. The case corresponding to $\ytableau\bullet$ (where is cell
below is not in the diagram) also gives us a column in the span of
$\begin{bmatrix}1\\\ 0\end{bmatrix}$.

The case of $\ytableau\\\ \bullet$ is similar, and we obtain a column in the
span of $\begin{bmatrix}0\\\ 1\end{bmatrix}$. Since our diagram is loopless
and the column of the diagram in question is not part of any $\mathcal{L}(i)$,
it follows that it must not occur after any column of the form
$\ytableau\bullet\\\ \bullet$. Note also that it cannot occur after any column
of the form $\ytableau\bullet\\\ $ by the defining condition of  $\Gamma$
-diagrams. ∎

######  Definition 4.7.

Let $\mathcal{L}(i)$ be a contiguous subdiagram of a  $\Gamma$ -diagram $D$.
We say $\mathcal{L}(i)$ is maximal if the column immediately to the left of
$\mathcal{L}(i)$ in $L$ (if it exists) is not

∙

For example, in Figure 8, $\mathcal{L}(1)$ appears twice as a contiguous
subdiagram, but only the leftmost one is maximal.

######  Definition 4.8.

For a loopless  $\Gamma$ -diagram $D$ of rank $2$ let $\tau_{D}$ be an integer
defined in the following way:

  1. (1)

Set $\tau_{D}$ to be the number of maximal distinct contiguous subdiagrams of
$\mathcal{L}(i)$, for varying values of $i$.

  2. (2)

Ignoring any columns covered by (1),

    1. (a)

if there is a column with $\bullet$ in the only top row, add 1 to $\tau_{D}$;
and

    2. (b)

if there is a column with $\bullet$ in the only bottom row occurring not
occurring in any $\mathcal{L}(i)$, add 1 to $\tau_{D}$.

Note both 2(a) and 2(b) may occur.

For instance, if $D$ is the  $\Gamma$ -diagram from Figure 11, there is a
maximal $\mathcal{L}(1)$ and a maximal $\mathcal{L}(2)$. Ignoring the columns
in these subdiagrams, we have columns that have the only top entry filled with
a $\bullet$. Thus, $\tau_{D}=3$.

######  Lemma 4.9.

If $D$ is a loopless  $\Gamma$ -diagram of rank $2$, then $\tau_{D}$ is the
number of cyclic flats that have rank $1$.

###### Proof.

Cyclic flats that have rank $1$, in our case, correspond to maximal
collections of columns of $\operatorname{Meas}(N_{D})$ which are pair-wise
scalar multiples of one another. From Lemma 4.3 we get pair-wise parallel
columns for any $\mathcal{L}(i)$. Corollary 4.4 tells us that each maximal
copy of an $\mathcal{L}(i)$ will contribute to our count since disjoint copies
will be linearly independent.

Note that the vectors corresponding to columns from an $\mathcal{L}(i)$ are
never scalar multiples of $\begin{bmatrix}1\\\ 0\end{bmatrix}$ nor
$\begin{bmatrix}0\\\ 1\end{bmatrix}$ whose count can be found by Lemma 4.6.
Hence, $\tau_{D}$ counts the desired cyclic flats and the lemma is proven. ∎

We can now state our main result proving a necessary and equivalent condition
proving when a  $\Gamma$ -diagram is transversal.

######  Theorem 4.10.

Let $D$ be a  $\Gamma$ -diagram of rank $2$. The positroid associated with $D$
is transversal if and only if $0\leq\tau_{\hat{D}}\leq 2$ where $\hat{D}$ is
the loopless reduction.

For example, the  $\Gamma$ -diagram $D$ from Figure 11 gives a positroid that
is not transversal since $\tau_{D}=3$.

###### Proof of Theorem 4.10.

By previous discussion, it suffices to consider the loopless form. So, we may
assume $D$ is loopless. We will use Theorem 2.7 and check the inequality

$\operatorname{rank}(\cap\mathcal{F})\leq\sum_{\mathcal{F}^{\prime}\subseteq\mathcal{F}}(-1)^{|\mathcal{F}^{\prime}|+1}\operatorname{rank}(\cup\mathcal{F}^{\prime})$

over antichains of cyclic flats. It is clear that the inequality is satisfied
with equality if $\mathcal{F}$ is empty or consists of a single cyclic flat.
So, we immediately see that the positroid will be transversal when
$\tau_{D}\leq 1$. Since the positroid we are dealing with has rank $2$ any
antichain $\mathcal{F}$ containing multiple cyclic flats must be a collection
of rank $1$ cyclic flats. The key point is in rank $2$ in the intersection and
union in the inequality are well controlled. The intersection of any two or
more rank $1$ flats is the unique rank $0$ flat. Similarly, the union of any
two or more rank $1$ flats is the unique rank $2$ flat.

Let us assume we have at least cyclic flats on rank $1$ and take
$\mathcal{F}=\\{F_{1},F_{2}\\}$. It must be that
$\operatorname{rank}(\cap\mathcal{F})=\operatorname{rank}(F_{1}\cap F_{2})=0$.
We also have

$\displaystyle\sum_{\mathcal{F}^{\prime}\subseteq\mathcal{F}}(-1)^{|\mathcal{F}^{\prime}|+1}\operatorname{rank}(\cup\mathcal{F}^{\prime})$
$\displaystyle=-\operatorname{rank}(\emptyset)+\operatorname{rank}(F_{1})+\operatorname{rank}(F_{2})-\operatorname{rank}(F_{1}\cup
F_{2})$ $\displaystyle=0+1+1-2$ $\displaystyle=0$

and the inequality is again satisfied with equality. Thus, we may conclude the
positroid is transversal whenever $0\leq\tau_{D}\leq 2$.

It remains to argue that the positroid is not transversal whenever
$\tau_{D}\geq 3$. To do this is sufficient to take
$\mathcal{F}=\\{F_{1},F_{2},F_{3}\\}$ and show the inequality is violated.
Again on the left we
$\operatorname{rank}(\cap\mathcal{F})=\operatorname{rank}(F_{1}\cap F_{2}\cap
F_{3})=0$ On the left, we compute and find

$\displaystyle\sum_{\mathcal{F}^{\prime}\subseteq\mathcal{F}}(-1)^{|\mathcal{F}^{\prime}|+1}\operatorname{rank}(\cup\mathcal{F}^{\prime})$
$\displaystyle=-\operatorname{rank}(\emptyset)+\operatorname{rank}(F_{1})+\operatorname{rank}(F_{2})+\operatorname{rank}(F_{3})$
$\displaystyle\quad\quad\quad-\operatorname{rank}(F_{1}\cup
F_{2})-\operatorname{rank}(F_{1}\cup F_{3})-\operatorname{rank}(F_{2}\cup
F_{3})+\operatorname{rank}(F_{1}\cup F_{2}\cup F_{3})$
$\displaystyle=0+1+1+1-2-2-2+2$ $\displaystyle=-1$

violating the inequality. Therefore, the theorem is proven. ∎

######  Remark 4.11.

Matroids whose lattice of cyclic flats is “small” have been studied before.
The _width_ of a poset the size of the largest antichain. In our rank $2$
setting the width of the lattice of cyclic flats on the positroid associated
to $D$ is $\max\\{1,\tau_{D}\\}$. In [BdM08, Theorem 5.6] it was shown that
for any rank if the lattice of cyclic flats has width $2$, then the matroid
and its dual are both transversal.

######  Remark 4.12.

If $M$ is a paving matroid, note that the cyclic flats are precisely the
stressed hyperplanes. Thus, as a poset, the lattice of cyclic flats is
isomorphic to the lattice of cyclic flats for rank 2 matroids discussed in the
prior Theorem (i.e., it consists of a minimal element, a maximal element, and
possibly some antichain in between). It is tempting to think that our prior
theorem implies a classification of transversal paving matroids. However, the
arbitrary rank of paving matroids makes this not the case, as we now
demonstrate. Suppose $M$ is a paving matroid of rank $r$ with at least three
dependent hyperplanes, say $H_{1}$, $H_{2}$, and $H_{3}$. Let
$\mathcal{F}=\\{H_{1},H_{2},H_{3}\\}$, then the left-hand side of equation (1)
satisfies $\operatorname{rank}(\cap\mathcal{F})\leq r-2$, but we cannot
conclude equality when $r>2$. The right-hand side of equation (1), however, is

$\displaystyle\operatorname{rank}(H_{1})+\operatorname{rank}(H_{2})+\operatorname{rank}(H_{3})-\operatorname{rank}(H_{1}\cup
H_{2})-\operatorname{rank}(H_{1}\cup H_{3})-\operatorname{rank}(H_{1}\cup
H_{3})+\operatorname{rank}(H_{1}\cup H_{2}\cup H_{3})$
$\displaystyle=r-1+r-1+r-1-r-r-r+r$ $\displaystyle=r-3.$

##  5\. Paving Positroids

In this section, we will determine when a  $\Gamma$ -diagram corresponds to a
paving matroid. First recall that the uniform matroid $U_{k,n}$ is a positroid
and its  $\Gamma$ -diagram is the full $k\times(n-k)$ rectangle with a
$\bullet$ in each possible position. To begin we number $n$ cell along the
boundary of the $k\times(n-k)$ rectangle. If $k>1$, we do the following:

  1. (i)

We number the cell in the lower right corner with a $1$.

  2. (ii)

We number right to left with $2,3,\dots n-k+1$ the cells in the top row.

  3. (iii)

We number top to bottom with $n-k+1,n-k+2,\dots,n$ the cells in the the left-
most column.

If $k=1$, that is, our diagram is a horizontal strip, we number the rightmost
cell with both $1$ and $2$, and then from right-to-left, number the remaining
cells $3$ through $n$. If $k=n-1$, we do something similar but label the
bottom-most cell with both $1$ and $n$. An example of this numbering is shown
in Figure 13.

7& 6 5 4 3 2

8

9

10 1

7&6 5 4 3 1 2

2

3

4

5

1 6

Figure 13. The numbering of the cells for $k=4$ and $n=10$ on the left, $k=1$
and $n=7$ in the middle, and $k=5$ and $n=6$ on the right.

If the $k\times(n-k)$ rectangle is completely filled with $\bullet$’s then the
numbered cells are the only cells that can be modified to still obtain a
$\Gamma$ -diagram. Let $f:[n]\to[0,n-k-1]$ be a function. We define
$D_{k,n}(f)\in\raisebox{0.0pt}{\scalebox{-1.0}[-1.0]{$\Gamma$}}(k,n)$ to be
the  $\Gamma$ -diagram obtained by taking the completely filled diagram and,
for each $i\in[n]$,

  1. (1)

if $f(i)=0$, do nothing. Otherwise,

  2. (2)

if $i=1$, use the diagram ($k$, $k$, $\dots$, $k$, $k-f(i)$) instead.
(Intuitively, we remove the $f(i)$ right-most cells in the bottom-most row.)

  3. (3)

if $n-k+1\geq i>1$, remove the $\bullet$ in the cell labeled by $i$ along with
the $f(i)-1$ cells to the left of $i$.

  4. (4)

if $i>n-k+1$, remove the $\bullet$ in the cell labeled by $i$ along with the
$f(i)-1$ cells to the right of $i$.

Figure 14 has an example of such a diagram.

∙& ∙ ∙ ∙ ∙

∙∙∙∙∙∙

∙∙∙

∙∙∙∙

∙& ∙ ∙∙

∙& ∙ ∙ ∙

Figure 14. On the left, we have the  $\Gamma$ -diagram $D_{4,10}(f)$, where
$f:[10]\to[5]$ so that $f(1)=2$, $f(3)=1$, $f(9)=3$, and $f$ is zero
otherwise. In the middle, we have $D_{1,7}(f)$ where $f(1)=1$ and $f(5)=1$. On
the right, we have $D_{1,7}(f)$ where $f(2)=1$ and $f(5)=1$.

######  Remark 5.1.

We wish to point out a couple of unfavorable things that may occur without
further restrictions on $f$.

  1. (1)

Note that the value of $i$ implies some values for $f(i)$ are not possible.
For instance, $f(n-k)$ must always be at most $2$, since there is one cell to
the left of the cell labeled $n-k$.

  2. (2)

If $i,j\in[n]$ are distinct, it is possible that in the construction of
$D_{k,n}(f)$, the cells removed to the right of cell $i$ and cell $j$ may have
some overlap or create an entire row with empty cells. For instance, consider
$f$ so that $f(3)=3$ and $f(4)=2$. The $\bullet$’s in cells $4$ and $5$ are
being removed both because of $f(3)$ and because of $f(4)$.

In light of Remark 5.1, we define the following.

######  Definition 5.2.

Let $n$ and $k$. A function $f:[n]\to[0,n-k-1]$ is said to be _ $\Gamma$
-diagram compliant (ldc)_ if

  1. (1)

$f(i)\leq n-k+1-i$, if $1<i\leq n-k+1$;

  2. (2)

$f(i)\leq n-k-1$, when $i=1$ or $i\geq n-k+2$;

  3. (3)

if $i<j\leq n-k+1$ and $f(i)$ and $f(j)$ are both nonzero, then $f(i)<j-i$;
and

  4. (4)

$f(1)+f(n)\leq n-k-1$.

The first two conditions for a function to be ldc guarantees it avoids (1) in
Remark 5.1, and the last two conditions for a function to be ldc guarantees it
avoids (2) in Remark 5.1.

From here on, we assume all our functions $f:[n]\to[0,n-k-1]$ are ldc unless
stated otherwise. We leave it to the reader to verify the following.

######  Proposition 5.3.

$D_{k,n}(f)$ is a  $\Gamma$ -diagram.

######  Remark 5.4.

One thing we have yet to address is why we choose the maximum of any image to
be $n-k-1$. Indeed, there can be up to $n-k$ cells in a given row. However, a
row with every cell empty means that the corresponding source is a coloop. The
following Proposition justifies why it suffices to assume our matroids are
coloop-less. In particular, note that when $k=n-1$, being coloop-less implies
$D_{k,n}(f)$ is a uniform matroid, that is, $f$ is identically zero.

######  Proposition 5.5.

A non-Boolean paving matroid $M=(E,\mathcal{B})$ has at most one coloop.
Moreover, a non-Boolean paving matroid $M$ has a coloop $c$ if and only if
$M=B(\\{c\\})\oplus U_{k-1}(E\setminus\\{c\\})$

###### Proof.

Let $M$ be a rank $k$ non-Boolean paving matroid. Let $C$ be the set of
coloops for a matroid $M$, then $M=B(C)\oplus M|_{[n]\setminus C}$. As Boolean
matroids have no circuits, the circuits of $M$ are precisely the circuits of
$M|_{[n]\setminus C}$. As $M$ is not Boolean it follows that $M|_{[n]\setminus
C}$ cannot be Boolean, and the set of circuits cannot be empty.

Note that the rank of $M|_{[n]\setminus C}$ is $k-|C|$. Since
$M|_{[n]\setminus C}$ is a minor of a paving matroid, it is itself a paving
matroid. We claim it must be a uniform matroid. If not, it has a circuit of
size $k-|C|$, but this set would then have to be a circuit with cardinality
$k-|C|<k$ in $M$ This would contradict the fact that $M$ is paving and has
rank $k$. Thus, $M|_{[n]\setminus C}$ is uniform, and thus its circuits are
all size $k-|C|+1$. Therefore, we see $M$ cannot be a paving matroid when
$|C|>1$.

Conversely, note that $B(\\{c\\})\oplus U_{k-1}(E\setminus\\{c\\})$ is paving
as its rank is $k$ and its circuits must be the circuits of
$U_{k-1}(E\setminus\\{c\\})$, all of which have cardinality $k$. ∎

Even with the aforementioned restrictions on ldc functions, we are interested
in an even finer class of functions.

######  Definition 5.6.

Given an ldc function $f:[n]\to[0,n-k-1]$, we further call it _paving $\Gamma$
-diagram compliant_ (pldc) if for all $i<j$ with $i,j\in[n]$, and both $f(i)$
and $f(j)$ nonzero,

  1. (1)

If $i=1$ and $j<n$, then when $j\leq n-k+1$, we have $f(1)+2\leq j$, when
$n>j>n-k+1$, we have $f(1)+f(j)\leq n-k$

  2. (2)

If $1<i\leq n-k+1$ and $j>n-k+1$ is a pair of indices, then
$f(i)+f(j)\leq\min(j-i,n-k)$.

  3. (3)

If $j>i>n-k+1$, then $f(j)\leq\min(j-i-1,n-k-f(i))$.

  4. (4)

If $i=1$ and $j=n$, then we require $f(1)+f(\ell)+f(n)\leq n-k$ for all $\ell$
where $f(\ell)>0$.

For example, the $f$ in Figure 14 is not pldc as it violates condition (1).
Item (1) can be reinterpreted as saying “the empty cells caused by $f(j)$ can
not be in the right-most $f(1)$ columns.”

For such a pldc function, we associate an important collection of sets for
each of its nonzero outputs.

######  Definition 5.7.

Let $f:[n]\to[0,n-k-1]$ be pldc. An _obstruction set_ is a set $H_{i}$,
defined for each $i$ where $f(i)>0$, where

$H_{i}:=\begin{cases}\\{i,i+1,...,i+k+f(i)-2\\}&i\leq n-k+1\\\
\\{i-f(i)+1,i-f(i)+2,\dots,i+k-1\\}&i>n-k+1.\end{cases}$

When $f(1)$ and $f(n)$ are nonzero, in place of $H_{1}$ and $H_{n}$, we have
the obstruction set

$\hat{H}:=H_{1}\cup H_{n}$

While the descriptions in the prior two definitions are seemingly
unintelligible, they lead to the following result.

######  Theorem 5.8.

A coloop-less positroid is a paving matroid if and only if its  $\Gamma$
-diagram is of the form $D_{k,n}(f)$, where $f:[n]\to[0,n-k-1]$ is pldc.

In particular, when $k\geq 2$, the hyperplanes for the matroid are given by
the obstructions for $f$.

When $k=1$, the hyperplane, that is, the set of loops, is the set

$\bigcup_{i=1}^{n}H_{i}=\bigcup_{i=1}^{n}[i,i+f(i)-1]$

###### Proof when $k=1$..

We show why the hyperplane of $D_{1,n}(f)$ is as described. When $f(i)>0$ for
$i>1$, we have $\bullet$’s missing in columns $i,i+1,\dots,i+f(i)-1$. This
makes it impossible for there to be a path from the source to sinks
$i,i+1,\dots,i+f(i)-1$. Thus, $[i,i+f(i)-1]$ is a set of loops for
$D_{k,n}(f)$. Furthermore, if $f(1)>0$, then the numbers in $[1,f(1)]$ are all
sinks appearing before the first source, so these are also loops. Any integer
$i$ with $f(i)=0$ has a bullet above sink $i$, and since condition (1) of $f$
being pldc implies that $i\geq f(1)+2$, this guarantees that such $i$ must
occur after the source, $f(1)+1$. Thus, $\\{i\\}$ is not a loop. This
demonstrates that $D_{k,n}(f)$ is a matroid whose loops are

$\bigcup_{i=1}^{n}[i,i+f(i)-1].$

The fact that the main statement is true follows from the fact that any
matroid of rank $1$ is paving with its set of loops as its only hyperplane.

∎

######  Remark 5.9.

As we know precisely which paving matroids have coloops, one could define a
pldc function to allow for this case so that Theorem 5.8 could be stated
without the coloop condition. However, both the description of pldc and the
proofs which follow work out much cleaner in the way which we have currently
stated. In terms of  $\Gamma$ -diagrams, a paving matroid with a coloop would
have $\bullet$ in all but one row.

While we are not yet ready to prove this Theorem for $k\geq 2$, we can still
motivate the conditions of pldc by considering Theorems A.1 and A.2, which
provide an alternate framework for building paving matroids. Our goal is to
show that the obstructions of $f$ satisfy the same conditions as the
$\mathcal{S}$ in the statement for Theorem A.1 and that the bases of
$D_{k,n}(f)$ are precisely the collection $\mathcal{B}(E,k,\mathcal{S})$ as in
the statement for Theorem A.1. From this and Theorem A.2, it follows that
$D_{k,n}(f)$ is paving. One can verify that the obstructions for $f$ satisfy
conditions (1) and (2) of Theorem A.1. The following Lemma shows that they
also satisfy condition (3) specifically when $f$ is pldc.

######  Lemma 5.10.

Let $k\geq 2$ and let $f:[n]\to[0,n-k-1]$ be an ldc function. Then the
intersection of any obstructions for $f$ has cardinality at most $k-2$ if and
only if $f$ is pldc.

###### Proof.

We proceed by cases on the two sets we intersect.

  1. (1)

Consider the intersection $H_{1}\cap H_{j}$. Recall

$H_{1}=\\{1,2,\dots,k+f(1)-1\\}.$

When $j\leq n-k+1$,

$H_{j}=\\{j,j+1,\cdots,j+k+f(j)-2\\}$

Note that if $|H_{1}\cap H_{j}|\leq k-2$, then it is impossible that
$H_{j}\subseteq H_{1}$. Conversely, if $H_{j}\subseteq H_{1}$, then
$k+f(1)-1\geq j+k+f(j)-2$, which implies $f(1)+1\geq j+f(j)$. This is not
possible if $f$ is pldc since $f(1)+2\leq j$. Thus, we have that the max of
$H_{1}$ is less then the max of $H_{j}$, and so the cardinality of the
intersection is precisely $\max(0,k+f(1)-j)$. The second argument is at most
$k-2$ if and only if $f(1)+2\leq j$, which is part of condition (1) for $f$ to
be pldc.

If $j>n-k+1$, then

$H_{j}=\\{j-f(j)+1,\dots,j+k-1\\}.$

This case is a bit subtle, as some of these elements are larger than $n$, and
thus must be considered modulo $n$. To proceed, let $j=n-k+1+\ell$ for
$1\leq\ell<k-1$. Then $I_{\ell}:=\\{1,2,\dots,\ell\\}\subseteq H_{1}\cap
H_{j}$. If $j-f(j)+1>k+f(1)-1$, then $H_{1}\cap H_{j}=I_{\ell}$, which has
cardinality $\ell\leq k-2$. Otherwise, we additionally have
$T:=\\{j-f(j)+1,j-f(j)+2,\dots,k+f(1)-1\\}\subseteq H_{1}\cap H_{j}$, and note
that $T$ and $I_{\ell}$ are disjoint and make up the entire intersection
$H_{1}\cap H_{j}$. Also observe that

$|T\cup I_{\ell}|=k+f(1)-j+f(j)-1+\ell=2k+f(1)-n+f(j)-2$

which is at most $k-2$ if and only if $f(1)+f(j)\leq n-k$.

  2. (2)

Now we consider $H_{j_{1}}\cap H_{j_{2}}$, where $1<j_{1}<j_{2}\leq n-k+1$..
Then

$H_{j_{1}}=\\{j_{1},j_{1}+1,\dots,j_{1}+k+f(j_{1})-2\\}$

and

$H_{j_{2}}=\\{j_{2},j_{2}+1,\dots,j_{2}+k+f(j_{2})-2\\}.$

Note that condition (3) for $f$ being ldc states $f(j_{1})<j_{2}-j_{1}$, and
thus $j_{1}+f(j_{1})+k-2$, the maximum element of $H_{j_{1}}$, is less than
$j_{2}+k-2$. In other words, $|H_{j_{1}}\cap H_{j_{2}}|\leq k-2$, with
equality when all of $j_{2}$ through $j_{2}+k-1$ are contained in $H_{1}$.

  3. (3)

Now we again consider the intersection $H_{j_{1}}\cap H_{j_{2}}$ but with
$1<j_{1}\leq n-k+1$ and $j_{2}>n-k+1$. We have

$H_{j_{1}}=\\{j_{1},j_{1}+1,\dots,j_{1}+k+f(j_{1})-2\\}$

and

$H_{j_{2}}=\\{j_{2}-f(j_{2})+1,j_{2}-f(j_{2})+2,\dots,j_{2}+k-1\\}.$

As in case (1), we pick $1\leq\ell<k-1$ so that $j_{2}=n-k+1+\ell$, so that
$1,2,\dots,\ell$ are the smallest elements of $H_{j_{2}}$. There are two ways
in which $H_{j_{1}}$ and $H_{j_{2}}$ may intersect:

     * •

If $j_{1}<\ell$, then $S:=\\{j_{1},j_{1}+1,\dots,\ell\\}\subseteq
H_{j_{1}}\cap H_{j_{2}}$.

     * •

If $j_{2}-f(j_{2})+1\leq j_{1}+k+f(j_{1})-2$, then
$T:=\\{j_{2}-f(j_{2})+1,j_{2}-f(j_{2})+2,...,j_{1}+k+f(j_{1})-2\\}\subseteq
H_{j_{1}}\cap H_{j_{2}}$. Remember that $j+k-1>n\geq i+k+f(i)-2$, and thus
$j+k-1$ is not the maximum of $T$.

Note that $S$ and $T$ is a partition of $H_{i}\cap H_{j}$. Thus, this
intersection can be described in one of three ways: $S$ (when $T$ is empty),
$T$ (when $S$ is empty), and $S\cup T$. Thus, we proceed with cases.

    1. (a)

If $T$ is empty, then note that

$|S|=\ell-j_{1}=-n+k+j_{2}-j_{1}$

This is at most $k-2$ when $j_{2}-j_{1}\leq n-2$, which is already true since
we are assuming $j_{1}>1$.

    2. (b)

If $S$ is empty, then note that if

$|T|=j_{1}+f(j_{1})-j_{2}+f(j_{2})+k-2$

is at most $k-2$ if and only if $f(j_{1})+f(j_{2})\leq j_{2}-j_{1}$. Note that
in this case we have $j_{2}-j_{1}\leq n-k$ as otherwise the maximum of
$H_{j_{2}}$, $j_{2}+k-1$, is larger then $j_{1}+n-1$, which is really
$j_{1}-1$. That is to say that $j_{2}+k-1$ would be at least $j_{1}$, but then
$S$ would be non-empty, a contradiction. Thus, condition (2) of pldc is
equivalent to $|T|\leq k-2$.

    3. (c)

If both $S$ and $T$ are nonempty, then

$|S\cup
T|=(-n+k+j_{2}-j_{1})+(j_{1}+f(j_{1})-j_{2}+f(j_{2})+k-2)=-n+2k+f(j_{1})+f(j_{2})-2$

This is at most $k-2$ if and only if $f(j_{1})+f(j_{2})\leq n-k$. Note in this
case we have $n-k\leq j_{2}-j_{1}$ as otherwise the maximum of $H_{2}$,
$j_{2}+k-1$, is smaller than $n+j_{1}-1$, which is really $j_{1}-1$. But this
suggests that $S$ is empty, a contradiction. Thus, condition (2) of pldc is
equivalent to $|S\cup T|\leq k-2$.

  4. (4)

We again consider the intersection $H_{j_{1}}\cap H_{j_{2}}$ but with
$j_{2}>j_{1}>n-k+1$. Then we have

$H_{j_{1}}=\\{j_{1}-f(j_{1})+1,\dots,j_{1}+k-1\\}$

and

$H_{j_{2}}=\\{j_{2}-f(j_{2})+1,\dots,j_{2}+k-1\\}.$

The intersection of $H_{j_{1}}\cap H_{j_{2}}$ is non-empty (since, for
instance, $n$ is in both) and note $j_{1}<j_{2}$ implies
$j_{1}+k-1<j_{2}+k-2$. Note then that $j_{1}-f(j_{1})+1\geq j_{2}-f(j_{2})+1$
if and only if $H_{j_{1}}\subseteq H_{j_{2}}$ which is true if and only if
$|H_{j_{1}}\cap H_{j_{2}}|=|H_{j_{1}}|=k-2+f(j_{1})$. If we assume the
intersection is at most $k-2$, this is an immediate contradiction as
$f(j_{1})>0$. If we assume $f$ is pldc, this is also a contradiction as this
implies that $f(j_{2})+1>f(j_{2})-f(j_{1})\geq j_{2}-j_{1}$, which contradicts
condition (3) for $f$ being pldc. Thus, $j_{1}-f(j_{1})+1<j_{2}-f(j_{2})+1$.
Thus, $H_{j_{1}}\cap H_{j_{2}}$ definitely contains
$T:=\\{j_{2}-f(j_{2})+1,\dots,j_{1}+k-1\\}$. Observe that

$|T|=j_{1}-j_{2}+f(j_{2})+k-1.$

Now, define $\ell_{2}$ so that $j_{2}=n-k+1+\ell_{2}$. In particular,
$[1,\ell_{2}]\subseteq H_{j_{2}}$. It is possible that $H_{j_{1}}\cap
H_{j_{2}}$ also contains $S:=[j_{1}-f(j_{1})+1,\dots,\ell_{2}$, which is
disjoint from $T$. Note that

$|S|=\ell_{2}-(j_{1}-f(j_{1})+1)+1=j_{2}-j_{1}+f(j_{1})-n+k-1.$

If $S$ is empty, then $H_{j_{1}}\cap H_{j_{2}}$ has cardinality

$|T|=j_{1}-j_{2}+f(j_{2})+k-1$

which is at most $k-2$ if and only if $f(j_{2})\leq j_{2}-j_{1}-1$. For $S$ to
be empty, we have

$j_{1}-f(j_{1})+1>\ell_{2}=j_{2}-n+k-1$

which is equivalent to

$n-k-f(j_{1})\geq j_{2}-j_{1}-1.$

Thus, in this case, $|T|\leq k-2$ is equivalent to condition (3) for $f$ being
pldc.

If $S$ is nonempty, then the intersection has cardinality

$|S|+|T|=(j_{2}-j_{1}+f(j_{1})-n+k-1)+(j_{1}-j_{2}+f(j_{2})+k-1)=f(j_{1})+f(j_{2})-n+2k-2$

which is at most $k-2$ if and only if $f(j_{2})\leq n-k-f(j_{1})$. Since in
this case we have $S$ is non-empty we have

$j_{1}-f(j_{1})+1\leq\ell_{2}=j_{2}-n+k-1$

which is equivalent to

$n-k-f(j_{1})<j_{2}-j_{1}-1.$

Thus, $|S|+|T|\leq k-2$ is equivalent to condition (3) of $f$ being pldc.

  5. (5)

$\hat{H}=\\{n-f(n)+1,n-f(n)+2,...,n,1,2,...,k+f(1)-1\\}.$

We verify that $|H_{i}\cap\hat{H}|\leq k-2$ if and only if $f$ is pldc. We
proceed here based on cases for $i$.

    1. (a)

If $1<i\leq n-k+1$, then $H_{i}\cap\hat{H}$ has at most two disjoint pieces:

$I=\\{i,i+1,\cdots,f(1)+k-1\\}$

and

$J=\\{n-f(n)+1,\dots,i+k+f(i)-2\\}.$

The case where one of $I$ or $J$ is empty follow from the above work
(specifically items (1) and (3)). Otherwise,

$H_{i}\cap\hat{H}=|I\cup J|=f(1)+2k+f(i)-n+f(n)-2$

which is at most $k-2$ if and only if $f(1)+f(i)+f(n)\leq n-k$, which is
condition (4) for $f$ being pldc.

    2. (b)

If $n-k+1<i<n$, then again $H_{i}\cap\hat{H}$ has at most two disjoint pieces:

$I=\\{i-f(i)+1,\dots,f(1)+k-1\\}$

and

$J=\\{n-f(n)+1,\dots,i+k-1\\}.$

As above, if $I$ or $J$ is empty, then we have already settled this above
(specifically items (1) and (4) above). Otherwise,

$|H_{i}\cap\hat{H}|=|I\cup J|=f(1)+2k+f(i)-n+f(n)-2$

which is at most $k-2$ if and only if $f(1)+f(i)+f(n)\leq n-k$, which is
condition (4) for $f$ being pldc.

∎

Thus, to be able to take advantage of the results in appendix A, all that is
left to show one must also show the subsets of $[n]$ which correspond to
disjoint path systems of $D_{k,n}(f)$ are precisely those contained in the
obstructions of $f$. That is, the bases of $D_{k,n}(f)$ are precisely
$\mathcal{B}(E,r,\mathcal{S})$ as in Theorem A.1, where $\mathcal{S}$ is the
set of obstructions of $f$. The proof of this is long and technical, but the
reader may find the details in Appendix B. In light of these details, we can
now prove one direction of Theorem 5.8.

######  Lemma 5.11.

Let $k\geq 2$ and $n$ be integers. If $f$ is pldc, then the positroid with
$\Gamma$ -diagram $D_{k,n}(f)$ is paving with $\\{H_{i}:{f(i)\neq 0}\\}$ as
its set of dependent stressed hyperplanes, where $H_{i}$ is defined as in
Theorem 5.8, and when both $f(1)$ and $f(n)$ are nonzero, we have
$\hat{H}:=H_{1}\cup H_{n}$ in place of $H_{1}$ and $H_{n}$.

###### Proof.

By Theorem B.2, we know that any sets not contained in the obstructions for
$f$ are all the sets that correspond to path systems in $D_{k,n}(f)$ which can
not be disjoint.

Thus, we now know that the obstructions for $f$ correspond to the sets
containing all $k$-sets which can not be disjoint path systems. By Lemma 5.10,
we also have $|H_{j_{1}}\cap H_{j_{2}}|\leq k-2$ for all possible distinct
$j_{1}$ and $j_{2}$, and also $|\hat{H}\cap H_{j}|$ for all necessary $j$ when
$f(1)$ and $f(n)$ are positive. Thus, by the results in Appendix A, these
obstruction sets are in fact the stressed hyperplanes of a paving matroid, and
this paving matroid is by construction our matroid.

∎

We now prove the other direction for Theorem 5.8.

######  Lemma 5.12.

If $M$ is paving matroid of rank $k\geq 2$ and on ground set $[n]$ which is
also a positroid. Then there exists a pldc function $f:[n]\to[0,n-k-1]$ so
that the positroid with  $\Gamma$ -diagram $D_{k,n}(f)$ is isomorphic to $M$.

###### Proof.

Let $D$ be the underlying  $\Gamma$ -diagram for $M$. We first show that the
only two possible shapes for $D$ are partitions of the form $(k,k,\dots,k,j)$
for $1\leq j\leq k$. If not, then $S:=\\{1,2,...,k-1\\}$ contains at least one
sink, making it impossible for any subset $V\subseteq[n]$ corresponding to a
path system to contain $S$, as this requires a path from a source in $S$ to a
sink in $S$, which means the source would not be in $V$ to begin with. In
other words, $S$ is dependent. But the cardinality of $S$ would contradict $M$
being paving.

Thus, this proves that $D$ must have shape $(k,k,\dots,k,j)$ for $1\leq j\leq
k$. Note that the value of $f(1)$ corresponds inversely with $j$, meaning that
$f(1)=0$ implies $j=k$, $f(1)=1$ implies $j=k-1$, and so on.

Next, we claim that if any cells in $D$ are empty, then they must be a part of
a contiguous horizontal segment of contiguous empty cells, in which the left-
most cell is on the boundary. Given an empty cell, since $D$ is a  $\Gamma$
-diagram, this means either all cells above or to the left must be empty. In
the latter case, we have our desired result. We show that the prior case is
impossible. If so, then suppose these empty vertical cells are above sink $t$.
Choose $j$ maximally so that the top $j$ cells of the column labeled by sink
$t$ are empty. We will refer to the lowest of these cells as $\gamma$. If $t$
is larger than any source, let $S=\\{t,t-1,...,t-k+j\\}$. We proceed by
assuming that the underlying partition is rectangular, noting the other case
is similar.555If the partition is not rectangular, then it is possible $t$ is
smaller than some source. In that case, set $S=\\{t,t-1,...,t-k-1+j\\}$. This
accounts for the fact that the column with source $t$ only has $k-1$ cells.
First, note if $j=k$, then $t$ becomes a loop, which is a contradiction. Thus,
assume $j<k$, and so $|S|<k$. We show that $S$ is a dependent set. Simply note
that due to the lack of $\bullet$s in the column above $t$, there can not be
enough space for disjoint paths to reach all sources in the columns above and
to the right of $t$. That is, $S$ is a dependent set, which contradicts the
fact that $M$ is paving.

Thus, we have demonstrated that if $M$ is a paving matroid which is also a
positroid, it at least must have a  $\Gamma$ -diagram of the form $D_{k,n}(f)$
where $f$ is ldc. The fact that $f$ may be assumed to be pldc follows from
Lemma 5.10.

∎

Applying Theorem 5.8 to sparse paving matroids yields the following
interesting result.

######  Corollary 5.13.

A positroid is sparse paving if and only if there is a pldc function
$f:[n]\to[0,n-k-1]$ so that $f(i)+f(i+1)\leq 1$ for all $i\in[n]$ (where $n+1$
is interpreted as $1$).

###### Proof.

This almost directly follows from the fact that for each $i$ with $f(i)=1$, as
then each set $H_{i}$ has cardinality $k$ (and thus a circuit-hyperplane). The
one exception is that we must require $f(1)+f(n)\leq 1$, otherwise $H_{1}\cup
H_{n}$ would be a hyperplane with cardinality larger than $k$, which is not
allowed for sparse paving matroids. ∎

Thus, in practice, one can identify a sparse paving  $\Gamma$ -diagram by
seeing single empty cells along the boundary of the diagram (along with the
condition that at most of positions 1 or $n$ are empty, and likewise with 1
and 2). See Figure 15 for some examples and nonexamples of sparse paving
positroids, all of which are paving.

∙& ∙ ∙ ∙
∙∙∙∙∙∙
∙ ∙∙∙∙
∙∙∙∙∙

∙& ∙ ∙
∙∙∙∙∙∙
∙ ∙∙∙∙
∙∙∙∙∙

∙& ∙ ∙ ∙
∙∙∙∙∙∙
∙ ∙ ∙∙∙∙
∙∙∙∙

Figure 15. The left diagram corresponds to a sparse paving matroid. The middle
is paving, but not sparse paving, since the corresponding function $f$ has
$f(3)=2$, which is larger than $1$. The right is also paving, but not sparse
paving, due to the fact that $f(1)=f(10)=1$.

##  6\. Enumeration

In this section, we look at enumerating positroids of the types studied in
this paper. One thing to keep in mind is, as is usual with positroids, we
enumerate positroids with an ordered labeled ground set. This is because the
ordering of the ground set is important for the positivity of the matrix
representing the positroid. In contrast, in many other situations, matroids
are often counted up to matroid isomorphism.

Our tables in this section can be compared to enumerations in the literature.
Work of Williams [Wil05] on topological cells in the totally nonnegative
Grassmannian enumerates all positroids. Recently, Billey and Weaver [BW] have
characterized and enumerated positroids which defined a smooth positroid
variety. Such positroids end up being direct sums of uniform matroids and thus
are transversal matroids.

###  6.1. Counting transversal and fundamental transversal positroids

n k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---|---
1 | 1 | 1 |  |  |  |  |  |  |
2 | 1 | 3 | 1 |  |  |  |  |  |
3 | 1 | 7 | 7 | 1 |  |  |  |  |
4 | 1 | 15 | 33 | 15 | 1 |  |  |  |
5 | 1 | 31 | 131 | 131 | 31 | 1 |  |  |
6 | 1 | 63 | 471 | 883 | 473 | 63 | 1 |  |
7 | 1 | 127 | 1583 | 5062 | 5111 | 1611 | 127 | 1 |
8 | 1 | 255 | 5055 | 25803 | 44241 | 26799 | 5281 | 255 | 1
Table 1. The enumeration of transversal positroids by rank given by $k$ and size of ground set given by $n$. n k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---|---
1 | 1 | 1 |  |  |  |  |  |  |
2 | 1 | 3 | 1 |  |  |  |  |  |
3 | 1 | 7 | 7 | 1 |  |  |  |  |
4 | 1 | 15 | 33 | 15 | 1 |  |  |  |
5 | 1 | 31 | 131 | 131 | 31 | 1 |  |  |
6 | 1 | 63 | 471 | 880 | 471 | 63 | 1 |  |
7 | 1 | 127 | 1583 | 4999 | 4999 | 1583 | 127 | 1 |
8 | 1 | 255 | 5055 | 25123 | 41847 | 25123 | 5055 | 255 | 1
Table 2. The enumeration of fundamental transversal positroids by rank given by $k$ and size of ground set given by $n$. n k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---|---
1 | 1 | 1 |  |  |  |  |  |  |
2 | 1 | 3 | 1 |  |  |  |  |  |
3 | 1 | 7 | 4 | 1 |  |  |  |  |
4 | 1 | 15 | 11 | 5 | 1 |  |  |  |
5 | 1 | 31 | 26 | 16 | 6 | 1 |  |  |
6 | 1 | 63 | 57 | 42 | 24 | 7 | 1 |  |
7 | 1 | 127 | 120 | 99 | 71 | 36 | 8 | 1 |
8 | 1 | 255 | 247 | 219 | 179 | 119 | 55 | 9 | 1
Table 3. The enumeration of paving positroids by rank given by $k$ and size of
ground set given by $n$.

Theorem 2.7 can be implemented, and we can use SageMath [Sag23] to produce
counts of transversal and fundamental transversal postroids which we give in
Table 1 and Table 2 respectively. Note that the dual of a positroid is a
positroid, and also the dual of a fundamental transversal matroid is a
fundamental transversal matroid. Hence, the rows of Table 2 are always
symmetric with respect to the rank of the matroid. However, the dual of a
transversal matroid need not be transversal. From Table 1 we see there do
indeed exist transversal positroids that are not cotransversal.

###  6.2. Counting paving and sparse paving positroids

In Table 3 we show the counts of paving positroids for $1\leq n\leq 8$ and
$0\leq k\leq n$. Notice the rows of this table are not symmetric as the
condition of being a paving matroid is not closed under duality. The columns
for $k=0$ and $k=1$ are trivial as they just count all positroids. The column
$k=2$ counts all loopless positroids since in this case paving means circuits
have size at least $2$. This implies the sequence $1,4,11,26,\dots$ given by
this column just consists of Eulerian numbers counting permutations of $[n]$
with $1$ descent.

######  Proposition 6.1.

The number of rank $2$ paving positroids on $[n]$ is equal to the Eulerian
number counting the number of permutations of $[n]$ with $1$ descent.

###### Proof.

A _decorated permuation_ is a permutation with fixed points colored $1$ or
$-1$. An _anti-exceedence_ of a decorated permutation $\pi$ is an index $i$ so
that $\pi^{-1}(i)>i$ or $\pi^{-1}(i)=i$ with the fixed point $i$ is colored
$-1$. Postnikov [Pos, Section 16] gives a bijection between positroids on
$[n]$ of rank $k$ and decorated permutations with $k$ anti-exceedences where
fixed points colored $1$ or $-1$ are loops or coloops respectively. Hence, for
the column $k=2$ we want all decorated permutations with $2$ anti-exceedences
where all fixed points are colored $-1$. This is simply the number of
permuations of $[n]$ with $2$ _weak anti-exceedences_ (i.e. $2$ positions with
$\pi^{-1}(i)\geq i$). These objects are in bijection with all permutations of
$[n]$ with $1$ descent by [Sta12, Proposition 1.4.3]. ∎

By Corollary 5.13 we find the sparse paving positroids on $[n]$ for any
$1<k<n-1$ are in bijection with subsets of $[n]$ which contain no two
consecutive elements cyclically (i.e. when reduced modulo $n$). We will call
such subset sets of $[n]$ _sparse paving subsets_ and let $s_{n}$ denote the
number of such sets for $n\geq 0$.

Recall, by Proposition 5.5 a paving matroid can have at most one coloop. Since
the dual of a sparse paving matroid is also sparse paving, it follows sparse
paving matroids can have at most one loop. If $k=1$ or $k=n-1$, then the
number of rank $k$ sparse paving positroids is $n+1$. This is because we have
the uniform matroid as well as positroids where exactly one element of $[n]$
is chosen to be a loop or coloop in the $k=1$ and $k=n-1$ cases respectively.
For the remaining cases when $1<k<n-1$ the following proposition will give us
the count of sparse paving positroids.

######  Proposition 6.2.

For $1<k<n-1$, the number of sparse paving subsets satisfies the reccurence
$s_{n}=s_{n-1}+s_{n-2}$ for $n\geq 2$ with $s_{0}=1$ and $s_{1}=2$.

###### Proof.

The only sparse paving subset for $n=0$ is $\\{\\}$. The sparse paving subsets
for $n=1$ are $\\{\\}$ and $\\{1\\}$. This handles the initial conditions.

Now assume $n\geq 2$. Consider an arbitrary sparse paving subset
$A\subseteq[n]$. There are three cases.

  1. (1)

Suppose $n$ is not in $A$ and at most one of $1$ or $n-1$ is in $A$. These
sets are in bijection with sparse paving subsets of $[n-1]$.

  2. (2)

Suppose both $1$ and $n-1$ are in $A$ (and thus $n$ is not in $A$). These are
in bijection with sparse paving subsets of $[n-2]$ which contain $1$, achieved
by adding the element $n-1$ to the set.

  3. (3)

Suppose $n$ is in $A$ (and thus neither $n-1$ nor $1$ is in $A$). These are in
bijection with sparse paving subsets of $[n-2]$ which do not contain $1$,
achieved by adding the element $n$ to the set.

Observe these three cases are disjoint and make up every possible sparse
paving subset of $[n]$. Moreover, case (1) is counted by $s_{n-1}$, while
cases (2) and (3) are counted by $s_{n-2}$.

∎

In light of Proposition 6.2 we can find the enumeration of sparse paving
positroids in the Online Encylopedia of Integer Sequence [OEI23, A169985].
Alternatively, $s_{n}$ is the nearest integer to $\phi^{n}$ where
$\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio.

## References

  * [AF23] Susama Agarwala and Siân Zee Fryer.  A study in $\mathbb{G}_{\mathbb{R},\geq 0}(2,6)$: from the geometric case book of Wilson loop diagrams and SYM $N=4$.  Ann. Inst. Henri Poincaré D, 10(1):159–204, 2023.  doi:10.4171/aihpd/133.
  * [AHBC+16] Nima Arkani-Hamed, Jacob Bourjaily, Freddy Cachazo, Alexander Goncharov, Alexander Postnikov, and Jaroslav Trnka.  Grassmannian geometry of scattering amplitudes.  Cambridge University Press, Cambridge, 2016.  doi:10.1017/CBO9781316091548.
  * [AHTT18] Nima Arkani-Hamed, Hugh Thomas, and Jaroslav Trnka.  Unwinding the amplituhedron in binary.  J. High Energy Phys., (1):016, front matter+40, 2018.  doi:10.1007/jhep01(2018)016.
  * [BdM08] Joseph E. Bonin and Anna de Mier.  The lattice of cyclic flats of a matroid.  Ann. Comb., 12(2):155–170, 2008.  doi:10.1007/s00026-008-0344-3.
  * [BKdM11] Joseph E. Bonin, Joseph P. S. Kung, and Anna de Mier.  Characterizations of transversal and fundamental transversal matroids.  Electron. J. Combin., 18(1):Paper 106, 16, 2011.  doi:10.37236/593.
  * [Bon] Joseph E. Bonin.  A characterization of positroids, with applications to amalgams and excluded minors.  arXiv:2306.06694 [math.CO].  doi:10.48550/arXiv.2306.06694.
  * [BW] Sarah C. Billey and Jordan E. Weaver.  Criteria for smoothness of positroid varieties via pattern avoidance, Johnson graphs, and spirographs.  arXiv:2207.06508 [math.CO].  doi:10.48550/arXiv.2207.06508.
  * [CR70] Henry H. Crapo and Gian-Carlo Rota.  On the foundations of combinatorial theory: Combinatorial geometries. The M.I.T. Press, Cambridge, Mass.-London,,, preliminary edition, 1970\.
  * [EZLT] Chaim Even-Zohar, Tsviqa Lakrec, and Ran J. Tessler.  The amplituhedron BCFW triangulation.  arXiv:2112.02703v5 [math-ph].  doi:10.48550/arXiv.2112.02703.
  * [FNV22] Luis Ferroni, George Nasr, and Lorenzo Vecchi.  Stressed hyperplanes and Kazhdan–Lusztig gamma-positivity for matroids.  International Mathematics Research Notices, pages 1–60, 10 2022\.  doi:10.1093/imrn/rnac270.
  * [FS22] Luis Ferroni and Benjamin Schröter.  Valuative invariants for large classes of matroids.  arXiv preprint arXiv:2208.04893, 2022.
  * [HMM+22] Derek Hanely, Jeremy L Martin, Daniel McGinnis, Dane Miyata, George D Nasr, Andrés R Vindas-Meléndez, and Mei Yin.  Ehrhart theory of paving and panhandle matroids.  arXiv preprint arXiv:2201.12442, 2022.
  * [Ing77] A. W. Ingleton.  Transversal matroids and related structures.  In Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976), volume 31 of NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., pages 117–131. Reidel, Dordrecht-Boston, Mass., 1977.
  * [JK82] Per M. Jensen and Bernhard Korte.  Complexity of matroid property algorithms.  SIAM J. Comput., 11(1):184–190, 1982.  doi:10.1137/0211014.
  * [KLS13] Allen Knutson, Thomas Lam, and David E. Speyer.  Positroid varieties: juggling and geometry.  Compos. Math., 149(10):1710–1752, 2013.  doi:10.1112/S0010437X13007240.
  * [KWZ20] Steven N. Karp, Lauren K. Williams, and Yan X. Zhang.  Decompositions of amplituhedra.  Ann. Inst. Henri Poincaré D, 7(3):303–363, 2020.  With an appendix by Karp, Williams, Zhang and Hugh Thomas.  doi:10.4171/AIHPD/87.
  * [Lus98] George Lusztig.  Introduction to total positivity.  In Positivity in Lie theory: open problems, volume 26 of De Gruyter Exp. Math., pages 133–145. de Gruyter, Berlin, 1998.
  * [Mac18] John Machacek.  Boundary measurement matrices for directed networks on surfaces.  Adv. in Appl. Math., 93:69–92, 2018.  doi:10.1016/j.aam.2017.09.002.
  * [Mar] Cameron Marcott.  Basis shape loci and the positive Grassmannian.  arXiv:1904.13361.  doi:10.48550/arXiv.1904.13361.
  * [Mas71] J. H. Mason.  A characterization of transversal independence spaces.  In Théorie des matroïdes (Rencontre Franco-Britannique, Brest, 1970), Lecture Notes in Math., Vol. 211, pages 86–94. Springer, Berlin, 1971.
  * [MNWW11] Dillon Mayhew, Mike Newman, Dominic Welsh, and Geoff Whittle.  On the asymptotic proportion of connected matroids.  European J. Combin., 32(6):882–890, 2011.  doi:10.1016/j.ejc.2011.01.016.
  * [OEI23] OEIS Foundation Inc.  The On-Line Encyclopedia of Integer Sequences, 2023.  Published electronically at http://oeis.org.
  * [Oxl11] James Oxley.  Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics.  Oxford University Press, Oxford, second edition, 2011.  doi:10.1093/acprof:oso/9780198566946.001.0001.
  * [Par] Hyungju Park.  Excluded minors of interval positroids that are paving matroids.  arXiv:2312.03525 [math.CO].  doi:10.48550/arXiv.2312.03525.
  * [Pos] Alexander Postnikov.  Total positivity, Grassmannians, and networks.  arXiv:math/0609764.  doi:10.48550/arXiv.math/0609764.
  * [PvdP15] Rudi Pendavingh and Jorn van der Pol.  On the number of matroids compared to the number of sparse paving matroids.  Electron. J. Combin., 22(2):Paper 2.51, 17, 2015.  doi:10.37236/4899.
  * [RI80] András Recski and Masao Iri.  Network theory and transversal matroids.  Discrete Appl. Math., 2(4):311–326, 1980.  doi:10.1016/0166-218X(80)90027-X.
  * [Sag23] The Sage Developers.  SageMath, the Sage Mathematics Software System, 2023.  https://www.sagemath.org.
  * [Sta12] Richard P. Stanley.  Enumerative combinatorics. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, second edition, 2012.
  * [Tal08] Kelli Talaska.  A formula for Plücker coordinates associated with a planar network.  Int. Math. Res. Not. IMRN, pages Art. ID rnn 081, 19, 2008.  doi:10.1093/imrn/rnn081.
  * [Wel76] D. J. A. Welsh.  Matroid theory.  LMS Monographs, No. 8. Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976.
  * [Wil05] Lauren K. Williams.  Enumeration of totally positive Grassmann cells.  Adv. Math., 190(2):319–342, 2005.  doi:10.1016/j.aim.2004.01.003.

##  Appendix A Alternative Definition for Paving Matroids

The following results are originally due to the authors of [HMM+22], though
these results did not make it into their article. Simultaneous to [HMM+22],
the authors of [FNV22] put out their paper providing the more general
framework of stressed-hyperplane relaxation to understand paving matroids than
what the following results portray. These previously unpublished results are
inserted here, one for posterity, but also because these results make they aid
us in showing certain matroids in this paper are paving. Since it is not
specifically the work of the authors of this paper and it has not been
published before, we have selected to include it as an appendix rather than in
the main body of this text.

######  Theorem A.1.

Fix a finite set $E$ and let $r\leq|E|$. Let $\SS\subset 2^{E}$ be a set
family satisfying the following conditions:

  1. (1)

$|S|\geq r$ for all $S\in\SS$.

  2. (2)

$\displaystyle\bigcup_{S\in\SS}\binom{S}{r}\neq\binom{E}{r}$ (to avoid
trivialities).

  3. (3)

If $S,S^{\prime}\in\SS$ with $S\neq S^{\prime}$, then $|S\cap S^{\prime}|\leq
r-2$.

Then the family

$\mathcal{B}(E,r,\SS)=\left\\{B\in\binom{E}{r}\leavevmode\nobreak\
\Big{|}\leavevmode\nobreak\ B\not\subseteq S\ \forall S\in\SS\right\\}$

is a matroid basis system for a rank $r$ matroid on ground set $E$.

###### Proof.

Let $B,B^{\prime}\in\mathcal{B}$ and $e\in B\setminus B^{\prime}$. Let
$B^{\prime}\setminus B=\\{f_{1},\dots,f_{t}\\}$. If $t=1$ then
$B^{\prime}=B\setminus e\cup f_{1}$, so the basis exchange condition is
automatically satisfied. Otherwise, to say that the exchange condition fails
is to say that every set of the form $C_{i}=B\setminus e\cup f_{i}$ is
contained in some $S_{i}\in\SS$.

Case I: Two of the $S_{i}$, say $S_{1}$ and $S_{2}$, are distinct. By the
Claim we have $|S_{1}\cap S_{2}|\leq r-2$ by the Claim. On the other hand,
$S_{1}\cap S_{2}\supseteq C_{1}\cap C_{2}=B\setminus e$, and $|B\setminus
e|=r-1$, which is a contradiction.

Case II: All the $S_{i}$ are equal. Then

$S_{1}\supseteq C_{1}\cup\cdots\cup C_{t}=(B\setminus
e)\cup\\{f_{1},\dots,f_{t}\\}\supseteq(B\cap
B^{\prime})\cup(B^{\prime}\setminus B)=B^{\prime}$

which contradicts the assumption $B^{\prime}\in\mathcal{B}$. ∎

######  Theorem A.2.

A matroid $M$ can has the basis system $\mathcal{B}(E,r,\SS)$ if and only if
it is a paving matroid.

###### Proof.

($\implies$): Fix a matroid $M$ with basis system $\mathcal{B}(E,r,\SS)$. Let
$X\in\binom{E}{r-1}$, and let $Y=E\setminus X$. It suffices to show that $X$
is independent in $M$. Suppose otherwise; then every set of the form $X\cup e$
for $e\in Y$ is not a basis, hence is a subset of some $S_{e}\in\SS$. If all
the sets $S_{e}$ are equal (say to $S$) then $S\supseteq\bigcup_{e\in Y}(X\cup
e)=E$, which is absurd (since then $M$ would have no bases). Otherwise, if
$S_{e}\neq S_{f}$ for some $e,f\in Y$, then $S_{e}\cap S_{f}\supset X$, so
$|S_{e}\cap S_{f}|\geq r-1$, contradiction the conditions on $\SS$.

($\impliedby$): Let $M$ be a paving matroid with ground set $E$ and rank $r$,
and let $\SS$ be the set of hyperplanes (flats of rank $r-1$). Certainly, a
$r$-element subset of $E$ is a basis if and only if it is not a subset of any
hyperplane; therefore, it suffices to prove that $\SS$ satisfies condition (2)
of Theorem A.1 (condition (1) is automatic by assumption). Let $H,H^{\prime}$
be distinct hyperplanes in $\SS$; then $G=H\cap H^{\prime}$ is a flat of rank
at most $r-2$. If $|G|>r-2$ then every $(r-1)$-subset of $G$ is dependent,
hence contains a circuit, which contradicts the definition of a paving
matroid. We conclude that condition (2) holds. ∎

##  Appendix B Obstructions and Path Systems

In this section we prove an important Theorem which we use in the proof of
Theorem 5.8. We have included this as an appendix rather than in the main body
of the paper since it is fairely long and computational. Before getting to the
result, we will introduce new notation which will help with the many cases for
the following proof.

######  Definition B.1.

For a set of integers $S$, we let

$S^{+}:=\\{s+1:s\in S\\}$

and

$S^{-}:=\\{s-1:s\in S\\}.$

######  Theorem B.2.

Suppose $f$ is pldc. Then the only disjoint path systems that are not possible
in $D_{k,n}(f)$ are precisely those witnessed by subsets of $H_{i}$ where
$f(i)>0$ or $\hat{H}=H_{1}\cup H_{n}$ when both $f(1)>0$ and $f(n)>0$.

###### Proof.

We show that $B$ is contained in some obstruction set of $D_{k,n}(f)$ if and
only if it can be manifested as a disjoint path system in $D_{k,n}(f)$.

We proceed by induction on $k$. If $k=1$, then there is only one source,
$f(1)+1$. We have demonstrated in the proof which follows Theorem 5.8 why any
path system contained in $H_{i}$ (or $\hat{H}$) will not be possible.

Suppose $k>2$. Fix a set $B\subseteq[n]$. Our strategy will be to find a way
to remove a row from the diagram which will allow us to apply our induction
hypothesis.

First, suppose that $1\in B$. Let $g:[n-1]\to[0,n-k-1]$ defined as follows.
Let $g(1)=f(1)$. Let $g(i)=0$ for $i\in[2,n-k+1]$. If $f(n-k+2)>0$, then we
override the previously assigned value for $g(n-k+2-f(n-k+2))$ to be
$f(n-k+2)$. Finally, let $g(i)=f(i+1)$ for $i\in[n-k+2,n-1]$. Consider the
diagram $D_{k-1,n-1}(g)$. Observe this diagram can be achieved by removing the
first row of $D_{k,n}(f)$. This is shown in Figure 16.

∙& ∙ ∙ ∙ ∙ ∙[1]
∙∙∙∙∙[2]
∙ ∙ ∙ ∙ ∙∙∙∙[3]
∙ ∙ ∙ ∙ ∙ ∙ ∙ [4 5]
[12] [11] [10] [9] [8] [7] [6]

& ∙∙∙∙∙[1]
∙ ∙ ∙ ∙ ∙∙∙∙[2]
∙ ∙ ∙ ∙ ∙ ∙ ∙ [3 4]
[11] [10] [9] [8] [7] [6] [5]

Figure 16. On the left we have $D_{4,12}(f)$ where $f(1)=1$, $f(3)=2$ and
$f(10)=3$. After removing the first row, we get $D_{3,11}(g)$ on the right,
where $g(1)=1$ and $g(7)=3$.

We may mostly assume that $g$ is still pldc with the exception of if
$H_{n-k+2}$ was an obstruction in $D_{k,n}(f)$. If it was, since
$g(n-k+2-f(n-k+2))=f(n-k+2)$. Note $n-k+2-f(n-k+2)$ is the only value of $i$
for which $g(i)\neq 0$ for $i\in[2,n-k+1]$. Thus, we need only check
conditions (1) and (3) to make sure that $g$ is pldc. First, note we have

$g(1)+f(n-k+2)=f(1)+f(n-k+2)\leq n-k,$

where the last equality holds since $f$ is pldc. Rearranging and adding $2$ to
both sides, we have

$g(1)+2\leq n-k+2+f(n-k+2),$

which is condition (1) for $g$ being pldc where $j=n-k+2+f(n-k+2$. Next, let
$j>n-k+2$ so that $f(j)>0$. Consider obstructions $H_{n-k+2}$ and $H_{j}$ in
$D_{k,n}(f)$. By condition (3) for $f$ being pldc, $n-k+2$ for the smaller
index in the condition statement, we have

$f(j)\leq\min(j-(n-k+2)-1,n-k-f(n-k+2)).$

Adding $f(n-k+2)$ gives

$f(n-k+2)+f(j)\leq\min(j-(n-k+2)-1+f(n-k+2),n-k).$

As $g(n-k+2-f(n-k+2))=f(n-k+2)$ and $g(j-1)=f(j)$, we have

$g(n-k+2-f(n-k+2))+g(j)\leq\min(j-1-(n-k+2-f(n-k+2)),n-k),$

which is precisely condition (3) for $g$ being pldc for indexes
$n-k+2-f(n-k+2)$ and $j-1$, which is all we need to check. Thus, $g$ is in
fact pldc.

Now, let $B^{\prime}=(B\setminus\\{1\\})^{-}$. Observe that $B^{\prime}$ is
the sources and sinks in $D_{k-1,n-1}(g)$ which correspond to the sources and
sinks in $B\setminus\\{1\\}$ in $D_{k,n}(f)$. That is, one can witness
$B^{\prime}$ as a disjoint path system in $D_{k-1,n-1}(g)$ if and only if one
can witness $B$ as a disjoint path system in $D_{k,n}(f)$. Thus, if we can
show that $B^{\prime}$ being contained in any obstruction set of
$D_{k-1,n-1}(g)$ is equivalent to $B$ being contained in any obstruction set
of $D_{k,n}(f)$, then we are done by induction. As $1\in B$, the only possible
obstructions of $f$ that could contain $1$ are

  * •

$H_{1}$;

  * •

$H_{j}$, $j>n-k+1$; and

  * •

$\hat{H}=H_{1}\cup H_{n}$.

Because of the definition of $g$, observe that the obstructions of
$D_{k-1,n-1}(g)$ are precisely

  * •

$H_{1}^{\prime}:=(H_{1}\setminus\\{1\\})^{-}$;

  * •

$H_{n-k+2-f(n-k+2)}^{\prime}:=(H_{n-k+2}\setminus\\{1\\})^{-}$;

  * •

$H_{j}^{\prime}:=(H_{1}\setminus\\{1\\})^{-}$, $j>n-k+2$; and

  * •

$\hat{H}^{\prime}:=(\hat{H}\setminus\\{1\\})^{-}$.

Observe we use a ′ symbol to distinguish between obstructions of $D_{k,n}(f)$
and $D_{k-1,n-1}(g)$. Thus, from the above descriptions of obstructions,
observe that $B^{\prime}$ is contained in a obstruction of $D_{k-1,n-1}(g)$ if
and only if $B$ is contained in an obstruction of $D_{k,n}(f)$, and so in the
case where $1\in B$, we are done by induction.

Next, suppose that $1\not\in B$, and let $m$ be the largest valued sink in $B$
and let $s$ be the largest valued source in $D_{k,n}(f)$. We proceed by cases
on the value of $s$ and $m$.

  1. (1)

First, we assume $s$ is less than $m$ and $s\notin B$. We have two subcases.

    1. (a)

If $m$ is the only sink in $B$ larger than $s$, then we claim a path from $s$
to $m$ does not exist if and only if $B\subseteq\hat{H}$. We equivalently
describe when there must be a $\bullet$ above $m$ in the bottom row. There is
such a bullet if and only if $f(n)\geq n-m+1$ if and only if
$[1,k-1]\cup\\{m\\}\subseteq\hat{H}$. We claim $B=[1,k-1]\cup\\{m\\}$ if and
only if $B\subseteq\hat{H}$. The forward direction is immediate. For the
converse, observe that $f$ being pldc implies $f(n)<n-k-f(1)$, and so

$H_{n}\subseteq[1,k-1]\cup\\{s+1,n\\}$

as $n-f(n)+1>k+f(1)+1=s+1$. Since $m$ is the only element of $B$ which is
larger than $s$, so the remaining elements of $B$ must be contained in
$[1,s-1]$, proving our claim. We have now demonstrated a path from $s$ to $m$
does not exist if and only if $B\subseteq H_{n}$, and the fact that $m\notin
H_{1}$ (as otherwise $m\leq s$) implies that this path does not exist if and
only if $B\subseteq\hat{H}$.

As the above argument implies that $B$ can not correspond to a disjoint path
system when $B\subseteq\hat{H}$, we proceed by assuming $B$ is not contained
in $\hat{H}$ (and thus neither $H_{1}$ nor $H_{n}$), and so the path from $s$
to $m$ exists. We will now find a subdiagram of $D_{k,n}(f)$ which allows us
to utilize our induction hypothesis. We define a function
$j:[1,n-1]\to[0,n-k-1]$ so that $j(1)=0$ and $j(i)=f(i)$ for $i\in[2,n-1]$.
Note that $j$ is pldc for the same reasons that $f$ is. Consequently,
$D_{k-1,n-1}(j)$ can be witnessed as the top $k-1$ rows of $D_{k,n}(f)$. See
Figure 17.

Now, note that because $m$ is the only element in $B$ which is bigger then
$s$, all remaining elements of $B$ are smaller than $s$. To this end, let
$B^{\prime}=B\setminus\\{m\\}$. Observe that $B^{\prime}$ is the set of
sources and sinks in $D_{k-1,n-1}(j)$ corresponding to the sources and sinks
in $B\setminus\\{m\\}$ in $D_{k,n}(f)$, that is, finding a disjoint path
system witnessing $B^{\prime}$ in $D_{k-1,n-1}(j)$ would correspond to a
disjoint path system witnessing $B$ in $D_{k,n}(f)$. If we can show that
$B^{\prime}$ is not contained in the corresponding $H_{i}$ for
$D_{k-1,n-1}(j)$, then we will be done by induction.

Note that the obstructions of $D_{k-1,n-1}(j)$ are of the form

       * •

$H_{i}^{\prime}:=H_{i}\setminus\\{\max(H_{i})\\}$, $1<i\leq n-k+1$

       * •

$H_{i}^{\prime}:=(H_{i}\setminus\\{1\\})^{-}$, $n-k+1<i\leq n-1$

We claim it is impossible to have $B^{\prime}\subseteq H_{i}^{\prime}$ and
$B\subseteq H_{i}$ for $i<n-k+1$. Note that the minimum of $H_{i}$ must
satisfy $f(1)+2\leq i$ by condition (1) of $f$ being pldc. This is
consequently also true for $H_{i}^{\prime}$. Since
$B^{\prime}\subseteq[1,s-1]$ and has cardinality $k-1$, its minimum must be at
most

$s-1-(k-1)+1=s-k+1$

Note that $s=f(1)+k$, so this is $f(1)+1$. This means the minimum of both $B$
and $B^{\prime}$ must be at most $f(1)+1$, making it impossible for them to be
contained in $H_{i}$ and $H_{i}^{\prime}$ respectively for $i<n-k+1$.

It is also impossible to have $B\subseteq H_{i}$ and $B^{\prime}\subseteq
H_{i}^{\prime}$ for $n-k+1<i<n$.

Define an integer $\ell$ so that $i=n-k+1+\ell$. Note that condition (1) of
$f$ being pldc states that $f(i)\leq n-k-f(1)$. Thus,

$H_{i}\subseteq[1,\ell]\cup[\ell+f(1)+2,n]$

since

$i-f(i)+1\geq(n-k+1+\ell)-(n-k-f(1))+1=\ell+f(1)+2$

Since $s=f(1)+k$, this means that the number of integers between $\ell+f(1)+2$
and $s-1$ is

$s-1-(\ell+f(1)+2)+1=k-\ell-2.$

Thus, $H_{i}$ has at most $k-2$ integers from $1$ to $s-1$. However, $B$ has
$k-1$ integers in this range, so this is impossible. Consequently, neither $B$
nor $B^{\prime}$ can be contained in $H_{i}$ and $H_{i}^{\prime}$
respectively.

We have shown that both $B$ and $B^{\prime}$ can not be contained in the above
obstructions. Thus, $B^{\prime}$ is contained in an obstruction for
$D_{k-1,n-1}(j)$ if and only if $B\subseteq H_{i}$ is contained in an
obstruction for $D_{k,n}(f)$ (not equal to or contained in $\hat{H}$). Thus,
we may proceed by induction in this case.

& ∙ ∙ ∙ ∙ ∙∙ ∙[1]
∙ ∙ ∙∙∙∙∙∙[2]
∙ ∙ ∙ ∙ ∙∙∙∙[3]
∙ ∙ [9 10] [8] [7] [6] [5] [4]
[12] [11]

& ∙ ∙ ∙ ∙ ∙ ∙ ∙[1]
∙ ∙ ∙∙∙∙∙∙[2]
∙ ∙ ∙ ∙ ∙∙∙∙[3]
[11] [10] [9] [8] [7] [6] [5] [4]

Figure 17. The  $\Gamma$ -diagram on the right is the smaller  $\Gamma$
-diagram obtained from the  $\Gamma$ -diagram on the right in the induction
proof of Theorem B.2. In this case we have $m=12$

    2. (b)

If $m$ is not the only sink in $B$ larger than $s$, then the must be a path
between $1$ and $m$ for us to be able to represent $B$. We demonstrate this
path exists. Suppose $m$ is in column $c_{m}$, where we count our columns from
right to left. So, $c_{m}+1$ labels the box in the top row of this column. If
there is a $\bullet$ is row 1 column $c_{m}$ which can be used to get a path
from $1$ to $m$. If there is not a $\bullet$ is row 1 column $c_{m}$. This may
be part of a contiguous collection of missing $\bullet$s in the first row. Let
$j\geq 1$ be an integer chosen minimally so that $f(c_{m}+1-j)=0$, that is,
row $1$ column $c_{m}-j$ has a $\bullet$. If $j$ does not exist, this means
that $f(2)\geq c_{m}$. In other words,

$B\subseteq[2,c_{m}]\subseteq\\{2,3,\dots,2+k+c_{m}-2\\}\subseteq H_{2}.$

Thus, $B$ is contained in an obstruction and can not be witnessed as a
disjoint path system, in which case we have shown the desired result.

Thus, we assume such a $j$ can be chosen minimally so that $f(c_{m}+1-j)=0$.
In other words, $f(c_{m}+2-j)>0$, and in particular, $f(c_{m}+2-j)>j-1$, by
choice of $j$. We claim there is a $\bullet$ is row $2$ column $c_{m}$, which
offers a path from $1$ to $m$ (as the  $\Gamma$ -diagram conditions require
there to also be a $\bullet$ is row $2$ column $c_{m}+2-j$). If not, then
$f(n-k+2)>n-k-c_{m}+1$. This then implies that

$f(n-k+2)+f(c_{m}+2-j)>n-k-c_{m}+j.$

Note that $c_{m}+2-j\geq 2$, and so $(n-k+1)-(c_{m}+2-j)\leq n-k$. Thus, the
fact that $f$ is pldc requires that

$f(n-k+2)+f(c_{m}+2-j)\leq n-k-c_{m}+j,$

Thus, the aforementioned path from $1$ to $m$ must be possible.

To proceed, we will find an appropriate subdiagram of $D_{k,n}(f)$ for which
we can apply induction. Our strategy will be to find a corresponding function
$g$ for this subdiagram which will also be pldc. Our choices, however, will
depend on the value of $f(1)$. Let us define $g:[1,m-1]\to[c_{m}-1]$ in the
following way. First, let $g(i):=\max(0,f(i-c_{m}+n-k+2)-(n-k-c_{m}+1))$ for
$i\in[c_{m}+1,m-2]$. Next, let $g(c_{m}+1-j)=j$. Finally, let $g(1):=f(1)$. In
this case, observe that $D_{k-1,c_{m}+k-2}(g)$ corresponds to the subdiagram
of $D_{k,n}(f)$ which remains after removing all cells containing or above and
left of the path from $1$ to $n$ (that is, it is the restriction of the right-
most $c_{m}-1$ columns and bottom $k-1$ rows, after removing $\bullet$’s in
cells where our path from $1$ to $m$ reside). This idea is demonstrated in
Figure 18. Note the top row of the new diagram will always have one contiguous
section of $\bullet$’s on the right followed by a contiguous section of blank
cells on the left. In particular, $g(c_{m}+1-j)$ is the only nonzero value of
$g$ in the top row.

& ∙ ∙ ∙ ∙[1]
∙ ∙ ∙∙∙∙∙∙[2]
∙ ∙ ∙ ∙ ∙∙∙∙[3]
∙∙∙∙[4]
[12] [11] [10] [9] [8][7] [6] [5]

& ∙∙ ∙[1]
∙ ∙∙∙∙[2]
∙∙∙∙[3]
[8] [7][6] [5] [4]

Figure 18. The  $\Gamma$ -diagram on the right is the smaller  $\Gamma$
-diagram obtained from the  $\Gamma$ -diagram on the right in the induction
proof of Theorem B.2. In this case we have $m=10$, $c_{m}=6$, and $j=2$.

Our goal is to once again do induction on this new diagram. We start by
showing that $g$ is pldc. Observe that by construction, $g$ will be ldc.

To check that $g$ is pldc, note that condition (3) is automatic since the
corresponding values for $i$ and $j$ in this case are both shifted by $n-k-
c_{m}+1$ by definition of $g$. We may also safely assume the part of condition
(1) which states “$f(1)+f(j)\leq n-k$” and condition (4), for similar reasons.

We will first check condition (2) for $g$ to be pldc, as this will help us
show $g$ also satisfies condition (1) for being pldc. Let $\ell\geq 1$ be an
integer so that $c_{m}+\ell$ corresponds to a marked spot in the left column
(not in the first row). Note that if
$g(c_{m}+\ell)+g(c_{m}+1-j)>\min(\ell+j-1,c_{m}-1),$ then

$\displaystyle f(\ell+n-k+1)+f(c_{m}+2-j)$ $\displaystyle\geq
g(c_{m}+\ell)+n-k-c_{m}+1+g(c_{m}+1-j)$ $\displaystyle>\min(\ell+j-1+n-k-
c_{m}+1,c_{m}-1+n-k-c_{m}+1)$ $\displaystyle>\min(\ell+n-k-c_{m}+j,n-k)$

but this contradicts condition (2) of $f$ being pldc. Thus, $g$ satisfies
condition (2) of being pldc.

We now verify $g$ satisfies condition (1) of being pldc. Since the largest
source is less than $m$, we must have that $f(1)<c_{m}-1$. It is possible
condition (1) for $g$ being pldc is violated in the case where
$f(1)+2=c_{m}+2-j$, as then $g(1)+2=f(1)+2>c_{m}+1-j$ and $g(c_{m}+1-j)\neq
0$. However, we claim that in this case, we can explicitly demonstrate how to
construct $B$ inside $D_{k,n}(f)$, and thus we do not need to appeal to $g$ or
induction to do so. The sources are $1,2,\dots,k-1$, and $k+f(1)$. The fact
that $f(c_{m}+2-j)>j-1$ implies that $B$ could not be contained in

$S:=\\{c_{m}+2-j,c_{m}+3-j,...,c_{m}+1,c_{m}+2,...c_{m}+k\\},$

where note $c_{m}+k=m$ (since $m$ is in column $c_{m}$ and $m$ must be larger
than the largest source). If the path coming from $2$ was forced to intersect
with the path coming from $1$, this conflict occurs in row $2$ column
$c_{m}-j$ (below the spot marked $c_{m}+1-j$). Observe column $c_{m}-j$ is the
column appearing immediately before the largest source. This requires that
$m-j-2$, $m-j-2$,…,$m-j-k+2$ to all be in $B$. In other words,
$B\subseteq[m-j-k+2,m]$. However, since $c_{m}+k=m$, this interval is
$[c_{m}+2-j,c_{m}+k]$, which is precisely $S$. This is impossible, so there
must be a disjoint path system corresponding to $B$.

We now know that $g$ is pldc. Now, define
$B^{\prime}=(B\setminus\\{m\\})^{-}$. As in case 1(a), $B^{\prime}$ is the set
of sources and sinks in $D_{k-1,c_{m}+k-2}(g)$ which correspond to in
$B\setminus\\{m\\}$ in $D_{k,n}(f)$. Thus, witnessing $B^{\prime}$ as a
disjoint path system in $D_{k-1,c_{m}+k-2}(g)$ corresponds to being able to
witness $B$ as a disjoint path system. If we can demonstrate that $B^{\prime}$
is not a subset of any obstruction set in $D_{k-1,c_{m}+k-2}(g)$, then we will
be done by induction.

We will describe the obstruction sets in $D_{k-1,c_{m}+k-2}(g)$ and prove that
$B^{\prime}$ being contained in an obstruction set is equivalent to $B$ being
in an obstruction set for $D_{k,n}(f)$. For clarity, as above, obstruction
sets in $D_{k-1,c_{m}+k-2}(g)$ will be denoted $H_{i}^{\prime}$, in contrast
to $H_{i}$ for $D_{k,n}(g)$. Observe that the only empty cells in the top row
of $D_{k-1,c_{m}+k-2}(g)$ are the left-most $j$ cells. In particular, $g(i)=0$
for $i<c_{m}+1-j$, and $g(c_{m}+1-j)=j$. Thus, one obstruction set for
$D_{k-1,c_{m}+k-2}(g)$ is $H_{c_{m}+1-j}^{\prime}$. Recall that
$f(c_{m}+2-j)>j-1$, and thus $H_{c_{m}+2-j}$ is an obstruction set for
$D_{k,n}(f)$. Observe that $(H_{c_{m}+1-j}^{\prime})^{+}\subseteq
H_{c_{m}+2-j}$. Furthermore, since $f(c_{m}+2-j)>j-1$, $m\in H_{c_{m}+2-j}$.
Thus, $B^{\prime}$ is a subset of $H_{c_{m}+1-j}^{\prime}$ if and only if $B$
is contained in $H_{c_{m}+2-j}$ and has $m$ as its maximum.

Another possible obstruction set is
$H_{1}^{\prime}:=\\{H_{1}\setminus\\{1\\})^{-}$. However, if
$B^{\prime}\subseteq H_{1}^{\prime}$, then all elements of $B\setminus\\{m\\}$
would be less than $s$, but this contradicts our assumption that there are
multiple sinks in $B$ larger than $s$.

A large group of remaining possible obstruction sets are thus appearing in the
left-most column of $D_{k-1,c_{m}+k-2}(g)$ (and not in the first row). Let
$H_{i}^{\prime}$ be such an obstruction. Here, we have $i\in[c_{m}+1,m-2]$.
Then note that $H_{i-c_{m}+n-k+2}$ is an obstruction set for $D_{k,n}(f)$. For
$H_{i}^{\prime}$ to be an obstruction, it must be that $f(i-c_{m}+n-k+2)>n-k-
c_{m}+1$. In particular, the smallest element in $H_{i-c_{m}+n-k+2}$ must
satisfy

$\displaystyle(i-c_{m}+n-k+2)-f(i-c_{m}+n-k+2)+1$
$\displaystyle<(i-c_{m}+n-k+2)-(n-k-c_{m}+1)+1$ $\displaystyle=i+2$

and so this means $[i+1,n]\subseteq H_{i-c_{m}+n-k+2}$. Since $i<m-2$, this
means that we are guaranteed to have $m\in H_{i-c_{m}+n-k+2}$. Furthermore,
observe that since $c_{m}\leq n-k$,

$i-c_{m}+n-1\geq k+i-1.$

Furthermore, note that

$\displaystyle i-g(i)+1$ $\displaystyle=i-f(i-c_{m}+n-k+2)+(n-k-c_{m}+1)+1$
$\displaystyle=i-c_{m}+n-k-f(i-c_{m}+n-k+2)+2$

Thus we have

$\displaystyle(H_{i}^{\prime})^{+}$
$\displaystyle=(\\{i-g(i)+1,...,m-2\\}\cup\\{1,2,\dots,i+k-m\\})^{+}$
$\displaystyle=\\{i-g(i)+2,...m-1\\}\cup\\{1,2,\dots,i+k-m+1\\}$
$\displaystyle=\\{i-c_{m}+n-k-f(i-c_{m}+n-k+2)+3,...m-1\\}\cup\\{1,2,\dots,i+k-m+1\\}$
$\displaystyle\subseteq\\{i-c_{m}+n-k-f(i-c_{m}+n-k+2)+3,...n\\}\cup\\{1,2,\dots,i-c_{m}+n+1)\\}$
$\displaystyle=H_{i-c_{m}+n-k+2}$

Thus, $B^{\prime}\subseteq H_{i}^{\prime}$ if and only if $B\subseteq
H_{i-c_{m}+n-k+2}$ with $m$ as the maximum of $B$.

Finally, it is possible that $\hat{H}$ is an obstruction for $D_{k,n}(f)$. If
$f(n)\leq n-k-c-m+1$, then $H_{n}^{\prime}$ would not be an obstruction in
$D_{k-1,c_{m}+k-2}(g)$. Suppose to the contrary that it is, and thus
$\hat{H}^{\prime}=H_{n}^{\prime}\cup H_{1}^{\prime}$ is an obstruction in
$D_{k-1,c_{m}+k-2}(g)$. In this case, we proceed by partition $B^{\prime}$
into $B_{1}^{\prime}:=B^{\prime}\cap H_{1}$ and
$B_{n}^{\prime}:=(B^{\prime}\setminus H_{1})\cap H_{n}$. Note that
$(B_{1}^{\prime})^{+}\subseteq H_{1}$ and, from the above arguments, we see
that we must have $(B_{n}^{\prime})^{+}\subseteq H_{n}$. Furthermore,
$m\in\hat{H}$ as $m\in H_{n}$. Using a similar partition for $B$, we see that
$B^{\prime}\subseteq\hat{H}$ if and only if $B\subseteq\hat{H}$.

  2. (2)

Now we will assume the largest source is greater than $m$ (and thus, the
largest source must be in $B$). We again choose $c_{m}$ to be the column where
sink $m$ occurs. In particular, note that $f(1)\geq c_{m}-1$. As in case 1(b),
we must have a path between $1$ and $m$, and the argument for 1(b) justifies
why one will exist. We proceed similarly to 1(b). This time, we define
$h:[m-3]\to[c_{m}-1]$ similarly to how we define $g$ above. Specifically, we
let $h(1)=0$, $h(c_{m}+1-j)=j$, and finally, let
$h(i):=max(0,f(i-c_{m}+j+n-k)-(n-k-c_{m}+1))$ for $i\in[c_{m}+2-j,m-3]$. Then
we construct $D_{k-2,c_{m}+k-3}(h)$, which is similar to the subdiagram we
built for $D_{k-1,c_{m}+k-2}(g)$ from $D_{k,n}(f)$ above, but we additionally
remove the bottom row of $D_{k,n}(f)$. See Figure 19. Because the construction
of $h$ is identical to $g$, we will again have that $h$ is pldc. As in case
1(b), let $B^{\prime}=(B\setminus\\{m\\})^{-}$. As before, demonstrating that
$B^{\prime}$ is not contained in the obstruction sets of
$D_{k-1,c_{m}+k-2}(h)$ will allow us to prove by induction that $B$ may be
witnessed as a disjoint set of paths in $D_{k,n}(f)$. However, the arguments
here are identical to those made in 1(b), and it is worth noting that $h(1)=0$
so we need not worry about the case where $H_{1}$ is an obstruction for
$D_{k,n}(f)$. Proceeding as above, we are done by induction.

& ∙ ∙ ∙ ∙[1]
∙ ∙ ∙∙∙∙∙∙[2]
∙ ∙ ∙ ∙ ∙∙∙∙[3]
∙∙ [9 10] [8] [7] [6] [5] [4]
[12] [11]

& ∙∙ ∙[1]
∙ ∙∙∙∙[2]
[7] [6][5] [4] [3]

Figure 19. The  $\Gamma$ -diagram on the right is the smaller  $\Gamma$
-diagram obtained from the  $\Gamma$ -diagram on the right in the induction
proof of Theorem B.2. In this case we have $m=10$, $c_{m}=6$, and $j=2$.

Thus, we have verified that $g$ is pldc, and since $D_{k-1,c_{m}+k-2}(g)$ as
$k-1$ sources, we may construct disjoint paths between the necessary sources
and sinks to construct $B\setminus\\{1,m\\}$. These paths also exist in
$D_{k,n}(f)$, and avoid our path from $1$ to $m$, and so we have witnessed $B$
as a disjoint set of paths. ∎