# Excluded minors of interval positroids that are paving matroids

Hyungju Park

###### Abstract.

We prove that every paving matroid that is an excluded minor of interval
positroids can be reduced to one of three fundamental families of excluded
minors of interval positroids by relaxing dependent hyperplanes. Using this
result, we classify all non-positroid excluded minors of interval positroids
that are paving matroids. Additionally, we provide a criterion that
characterizes all excluded minors of interval positroids that are paving
positroids.

##  1\. Introduction

_Positroids_ are matroids introduced and studied by Postnikov [1] and, under
the name “base-sortable matroids”, by Blum [2]. The term “positroid” is used
to refer to two slightly different objects in the literature. A positroid
might indicate a matroid $M$ on the totally ordered set
$[n]:=\\{1,\ldots,n\\}$ that is represented by a real matrix with $n$ columns
and nonnegative maximal minors, by the correspondence associating each
$i\in[n]$ with the $i$th column. A matroid that is isomorphic to a positroid,
according to the previous description, is also called a positroid. To avoid
confusion, the positroid in the former sense will be called an _ordered
positroid_. Postnikov [1] found various combinatorial objects that bijectively
correspond to ordered positroids such as Grassmann necklaces, decorated
permutations,  $\Gamma$ -diagrams, and move-equivalence classes of reduced
plabic graphs.

Ardila et al. [3] observed that the class of positroids is closed under taking
minors and direct sum. Since the class of positroids is minor-closed, it is
natural to consider excluded minors for the class of positroids. Oh [4,
Section 4] showed that an ordered matroid is an ordered positroid if and only
if it avoids a minor with bases $\\{ij,jk,kl,il\\}$, $\\{ij,jk,kl,il,ik\\}$,
or $\\{ij,jk,kl,il,jl\\}$ on any subset $\\{i,j,k,l\\}\subseteq[n]$ with
$i<j<k<l$. But, excluded minors for the class of (unordered) positroids are
not fully characterized yet. Blum [2] characterized all excluded minors of
positroids of rank three. Bonin [5, Section 5] found several infinite families
of excluded minors for the class of positroids.

_Lattice path matroids_ (LPMs) are a special minor-closed class of matroids
associated with any pair of two noncrossing lattice paths that share the same
initial and terminal points. Oh [6] showed that LPMs are positroids and Bonin
[7] characterized excluded minors of LPMs. _Interval positroids_ , introduced
by Knutson and Lederer [8], constitute a minor-closed subclass of positroids
that include the class of LPMs. We take the first step in studying excluded
minors of interval positroids by characterizing all cases where they are also
paving matroids. In the class of paving matroids, positroids precisely
correspond to matroids with a circular-arc collection of dependent
hyperplanes. Our goal is to characterize all hypergraphs that are collections
of all dependent hyperplanes of a paving excluded minor of interval
positroids.

In Section 2, we review some results on interval and circular-arc hypergraphs,
positroids, and the hyperplane characterization of paving matroids. In Section
3, three families of “relaxation-minimal” paving excluded minors of interval
positroids are classified. These families are relaxation-minimal in the sense
that every other paving excluded minor of interval positroids can be reduced
to one of these three families through relaxation of stressed hyperplanes. In
Section 4, we give a criterion for characterizing paving excluded minors of
interval positroids that are also positroids. In Section 5, every paving, non-
positroid excluded minors of interval positroids with four dependent
hyperplanes is determined. In Section 6, we classify every paving, non-
positroid excluded minors of interval positroids with more than four dependent
hyperplanes. In Section 7, we summarize the results and identify which of
these excluded minors have been discussed in the recent paper by Bonin [5].

##  2\. Background

For notions and terms related to matroids that are not explained here, we
refer to the book by Oxley [9].

###  2.1. Interval hypergraphs and CA hypergraphs

Let us introduce the following terminology.

######  Definition 2.1.

Two sets $A,B$ overlap if their intersection is nonempty and incomparable
($A\not\subset B,B\not\subset A$).

A _hypergraph_ $\mathcal{H}$ is a pair $(V,E)$ of the set of vertices $V$ and
the set of edges $E$ which is a collection of subsets of $V$. A hypergraph is
a _clutter_ if any distinct two edges are incomparable. A _partial hypergraph_
of the hypergraph $\mathcal{H}=(V,E)$ is some hypergraph
$\mathcal{H}^{\prime}=(V,E^{\prime})$ where the set of edges $E^{\prime}$ is
contained in the original set of edges $E$. A _subhypergraph_ of a hypergraph
is the hypergraph $\mathcal{H}$ obtained by removing some vertices of a
partial hypergraph of $\mathcal{H}$. A _partial clutter_ is a partial
hypergraph that is a clutter. A vertex $x\in V$ is _isolated_ if it is not
contained in any edge.

A hypergraph with $n$ vertices is an _interval hypergraph_ if there is a
bijection from $V$ to the set $\\{1,\ldots,n\\}$ such that the image of every
edge under this bijection is an interval $[i,j]$ for some $1\leq i\leq j\leq
n$. Such a bijection will be called an _interval ordering_ of the hypergraph.
A hypergraph with $n$ vertices is a _circular-arc_ (or _CA_ for brevity)
hypergraph if there is a bijection from $V$ to the set $\\{1,\ldots,n\\}$ such
that the image of every edge under this bijection is a cyclic interval $[i,j]$
or $[1,i]\cup[j,n]$ for some $1\leq i\leq j\leq n$. Such a bijection will be
called an _arc ordering_ of the hypergraph. A partial hypergraph or a
subhypergraph of an interval (resp. CA) hypergraph is also an interval (resp.
CA) hypergraph. Ding [10, Theorem 2] classified forbidden partial clutters for
the class of interval clutters whose Venn diagrams are drawn in Figure 1 with
dots to indicate nonempty sets.

######  Proposition 2.1.

([10, Theorem 2])

A clutter $\mathcal{H}=(V,E)$ is non-interval if and only if some partial
clutter of $\mathcal{H}$ is one of the following five types of clutters:

  1. (1)

$A,B,C\in E$ such that $(A\cap B)\setminus C,(B\cap C)\setminus A$ and $(A\cap
C)\setminus B$ are all nonempty.

  2. (2)

$A,B,C\in E$ such that $A\setminus(B\cup C),B\setminus(A\cup
C),C\setminus(A\cup B)$ and $A\cap B\cap C$ are all nonempty.

  3. (3)

$A,B,C,D\in E$ such that $(A\cap B)\setminus(C\cup D),(B\cap C)\setminus(D\cup
A),(C\cap D)\setminus(A\cup B),(D\cap A)\setminus(B\cup C)$ and $A\cap B\cap
C\cap D$ are all nonempty.

  4. (4)

$A,B,C,D\in E$ such that $A\cap B,B\cap C$ and $A\cap C$ are empty and $A\cap
D,B\cap D$ and $C\cap D$ are nonempty.

  5. (5)

For $m\geq 4$, $A_{1},\ldots,A_{m}\in E$ such that $A_{i}\cap
A_{j}\neq\emptyset$ if and only if $i=j$ or $i=j\pm 1\mod m$.

(a) Type $1$ (b) Type $2$ (c) Type $3$ (d) Type $4$ (e) Type $5$

Figure 1. Forbidden partial clutters of interval clutters

Throughout the paper, we will refer to clutters described in Proposition 2.1
as non-interval clutters of type 1, 2, 3, 4, and 5. Note that non-interval
clutters of type 2,3, and 4 are not CA. Therefore, the following corollary is
a direct consequence of Proposition 2.1.

######  Corollary 2.1.

A non-interval, CA clutter $\mathcal{H}=(V,E)$ contains a partial non-interval
clutter of type 1 or 5.

The following two lemmas on CA clutters will be used in next sections.

######  Lemma 2.1.

Let $\mathcal{H}$ be a clutter with four edges $A,B,C,D$ such that:

  1. (1)

$A\cap D$, $B\cap D$, and $C\cap D$ are all nonempty;

  2. (2)

$A\setminus D$, $B\setminus D$, and $C\setminus D$ are pairwise disjoint.

Then $\mathcal{H}$ is non-interval.

###### Proof.

Suppose that there is an arc ordering of $\mathcal{H}$ such that $A,B,C,D$ are
all cyclic intervals. Since $D$ is a cyclic interval and $A\cap D$ is
nonempty, $A\setminus D$ is a nonempty cyclic interval adjacent to $D$. By the
same reason, $B\setminus D$ and $C\setminus D$ are nonempty cyclic intervals
adjacent to $D$. This is impossible since $A\setminus D$, $B\setminus D$, and
$C\setminus D$ are pairwise disjoint.

∎

######  Lemma 2.2.

Let $\mathcal{H}=(V,E=\\{A_{1},\ldots,A_{m}\\})$ be a non-interval CA clutter
with every vertex contained in at most two edges. Then, every intersection
$A_{i}\cap A_{i+1}$ and every set of isolated points
$A_{i}\setminus(A_{i-1}\cup A_{i+1})$ map to cyclic intervals for all
$i\in[m]$ by every arc ordering $f:V\to[n]$ of $\mathcal{H}$. Moreover, the
cyclic intervals appear in the following order up to rotation and reversal:
$f(A_{1}\cap A_{m}),f(A_{1}\setminus(A_{m}\cup A_{2})),f(A_{1}\cap
A_{2}),f(A_{2}\setminus(A_{1}\cup A_{3})),\ldots,f(A_{m}\setminus(A_{m-1}\cup
A_{1}))$.

###### Proof.

For an arc ordering $f:V\to[n]$, the collection of all images $f(A_{i})$ is a
collection cyclic interval. Since $\mathcal{H}$ is not an interval clutter,
$m\geq 3$. Therefore, for each $i\in[m]$, $f(A_{i-1}),f(A_{i}),f(A_{i+1})$ are
distinct cyclic intervals of the set $[n]$. Since both $f(A_{i-1})\cap
f(A_{i})$ and $f(A_{i+1})\cap f(A_{i})$ are nonempty and disjoint, they are
cyclic intervals at each end of $f(A_{i})$. It follows that
$f(A_{i}\setminus(A_{i-1}\cup A_{i+1}))$ is the cyclic interval in the middle
obtained by removing both $f(A_{i-1})\cap f(A_{i})$ and $f(A_{i+1})\cap
f(A_{i})$ from $f(A_{i})$.

∎

###  2.2. Positroids

A _positroid_ is a $\mathbb{R}$-representable matroid that is representable by
a matrix whose maximal minors are all nonnegative. As mentioned in the
introduction, a positroid on the set $[n]$, represented by a nonnegative
maximal minor matrix with the correspondence $i\mapsto$ the $i$th column, will
be called an _ordered positroid_. Ardila et al. [3] observed that a matroid is
an ordered positroid with the given order of $[n]$ if and only if every
connected component is a positroid with the induced order and the collection
of connected components forms a noncrossing partition of the set $[n]$.
Therefore, every excluded minor of positroids is connected.

The matroid polytope of a matroid $M$ on the set $[n]$ is defined by the
convex hull of all vectors $e_{B}\in\mathbb{R}^{n}$ where $e_{B}=\sum_{i\in
B}e_{i}$. For a connected matroid, each facet of its matroid polytope
containing some interior point of the hypersimplex $\Delta_{d,n}$ is called a
_split facet_. Each split facet of a connected matroid is determined by a
dependent flat $F$ of $M$ and the inequality $\sum_{i\in F}x_{i}\leq
r_{M}(F)$, see [11, Propsition 7]. The flat that corresponds to a split facet
is called the _split flacet_. Positroids can be characterized in terms of
matroid polytope. A matroid is an ordered positroid with the given order if
and only if its matroid polytope is a subpolytope of the hypersimplex
$\Delta_{d,n}$ that is determined by inequalities of the form
$x_{i}+x_{i+1}+\cdots x_{j}\leq k$, where $[i,j]$ is a cyclic interval of the
set $[n]$, see [3, Proposition 5.7]. Thus, a connected matroid is an ordered
positroid if and only if all split flacets are cyclic intervals. Therefore, a
connected matroid $M$ is a positroid if and only if the collection of every
split flacets of $M$ is a CA hypergraph.

An (ordered) _interval positroid_ is characterized by a matroid whose matroid
polytope is the subpolytope of the hypersimplex $\Delta_{d,n}$ that is
determined by inequalities of the form $x_{i}+x_{i+1}+\cdots x_{j}\leq k$,
where $[i,j]$ is an interval of the set $[n]$, introduced by Knutson and
Lederer [8]. Any matroid that is isomorphic to an ordered interval positroid
will be called an interval positroid. The class of interval positroids is
closed under taking minors but not under taking the dual.

###  2.3. Hypergraphic characterization of paving matroids

A _paving matroid_ can be characterized in several different ways. For our
purpose, the most suitable approach is to characterize all hypergraphs that
can be the set of hyperplanes of a paving matroid. Hartmanis [12] introduced
the notion of $d$-partition, which generalizes the usual set partition. A
hypergraph with the vertex set $[n]$ is the collection of hyperplanes of a
paving matroid of rank $d$ if and only if it is a $(d-1)$-partition of the set
$[n]$.

######  Definition 2.2.

([9, Proposition 2.1.24])

A matroid $M$ of rank $d\geq 2$ on the set $[n]$ is paving if and only if the
collection of hyperplanes $\mathcal{H}$ of $M$, considered as a hypergraph
with the vertex set $[n]$, satisfies the following conditions:

  * •

Every edge of $\mathcal{H}$ has cardinality at least $d-1$.

  * •

Every subset of $[n]$ of cardinality $d-1$ is contained in exactly one edge of
$\mathcal{H}$.

It is worth mentioning that this definition has recently been extended to
introduce a new class of matroids known as elementary split matroids by Bérczi
et al. [13, Theorem 6]. The collection of hyperplanes of cardinality $d-1$ of
a paving matroid is the collection of all subsets of $[n]$ of cardinality
$d-1$ that is not contained in any hyperplane of cardinality greater than
$d-1$. Therefore, the collection of hyperplanes of a paving matroid is
determined by the collection of all hyperplanes of cardinality greater than
$d-1$, or equivalently dependent hyperplanes. The following definition
describes paving matroids in terms of dependent hyperplanes.

######  Definition 2.3.

A matroid $M$ of rank $d\geq 2$ on the set $[n]$ is paving if and only if the
collection of dependent hyperplanes $\mathcal{H}$ of $M$ is a hypergraph with
the set of vertices $[n]$, satisfying the following conditions:

  * •

Every edge of $\mathcal{H}$ has cardinality at least $d$.

  * •

For any two distinct edges $A,B$ of $\mathcal{H}$, the cardinality of the
intersection $A\cap B$ is at most $d-2$.

A paving matroid will be identified with the hypergraph formed by its
dependent hyperplanes, which is always a clutter, together with its rank $d$.
This clutter will just be called the clutter of the paving matroid. We use the
terms “edge” and “dependent hyperplane” interchangeably for a paving matroid.
Moreover, a clutter that is the clutter of some paving matroid of rank $d$
will be called a $d$-_paving clutter_. Dependent hyperplanes are precisely the
split flacets of a paving matroid. Thus, a paving matroid of rank $d$ is a
positroid (resp. interval positroid) if and only if its clutter is a CA
$d$-paving clutter (resp. an interval $d$-paving clutter). We will say an edge
of the clutter of a paving matroid is _small_ if its cardinality is $d$, or
equivalently if it is the circuit-hyperplane of the paving matroid. Any edge
that is not small will be referred to as a _large_ edge.

It is clear that a partial clutter, obtained by removing a dependent
hyperplane of a given paving matroid, is also the set of dependent hyperplanes
of a new paving matroid. This operation is called the _relaxation_ of a
_stressed hyperplane_ introduced by Ferroni et al. [14] which generalizes the
relaxation of a circuit-hyperplane. Since a partial clutter of an interval
clutter remains an interval clutter, the class of paving interval positroids
is closed under taking relaxations.

Notice that a paving matroid contains a loop if and only if the rank of the
matroid is $1$. And a paving matroid contains a coloop $x$ only if it is
either the uniform matroid $U_{n,n}$ or $[n]\setminus\\{x\\}$ is the only
dependent hyperplane. These cases will not appear since every paving matroid
we consider will be of rank at least $2$ with at least three edges. Finally,
the following lemma explains the effects of deletion and contraction
operations on the clutter of a paving matroid.

######  Lemma 2.3.

Let $\mathcal{H}=([n],E)$ be the clutter of a paving matroid $M$ of rank
$d\geq 2$. Suppose that $x$ is not a coloop. The clutter of the paving matroid
$M-x$ is

$\\{H\mid x\notin H,H\in E\\}\cup\\{H-x\mid x\in H,H\in E,|H|>d\\}.$

And the clutter of the contraction $M/x$ is

$\\{H-x\mid x\in H,H\in E\\}.$

###### Proof.

Bases of $M-x$ are bases of $M$ not containing $x$. Therefore, a hyperplane of
the deletion $M-x$ is a subset $H\setminus\\{x\\}$ where $H$ is a hyperplane
of $M$. Since edges of the clutter of $M$ are dependent hyperplanes, the
clutter of $M-x$ is $\\{H\mid x\notin H,H\in E\\}\cup\\{H-x\mid x\in H,H\in
E,|H|>d\\}$. A hyperplane of the contraction $M/x$ is a subset
$H\setminus\\{x\\}$ where $H$ is a hyperplane of $M$ containing $x$.
Therefore, the clutter of $M/x$ is $\\{H-x\mid x\in H,H\in E\\}$.

∎

Therefore, a $d$-paving clutter $(V,E)$ is an excluded minor of interval
positroids if and only if it is not an interval clutter and, for every $x\in
V$, both

$\\{H\mid x\notin H,H\in E\\}\cup\\{H-x\mid x\in H,H\in E,|H|>d\\}$

and

$\\{H-x\mid x\in H,H\in E\\}$

are interval clutters. Moreover, if $M$ is an excluded minor of interval
positroids and some relaxation $M^{\prime}$ of $M$ is not an interval
positroid, then $M^{\prime}$ is also an excluded minor of interval positroids.

##  3\. Relaxation-minimal paving excluded minors of interval positroids

In this section, we show that every paving excluded minor of interval
positroids can be reduced to relatively simple paving excluded minor of
interval positroids through the relaxation of dependent hyperplanes. These
“relaxation-minimal” paving excluded minors of interval positroids are
illustrated in Figure 2.

We first state the following fact.

######  Proposition 3.1.

Any paving matroid of rank $2$ is an interval positroid.

###### Proof.

The clutter of a paving matroid of rank $2$ is a collection of pairwise
disjoint edges since any intersection of a pair of distinct edges has maximal
size $d-2=0$. The result follows since a pairwise disjoint collection of edges
forms an interval clutter.

∎

Consequently, every paving excluded minor of interval positroids must have a
rank of at least $3$. The following theorem provides a characterization of
relaxation-minimal paving excluded minors of interval positroids.

######  Lemma 3.1.

The clutter of any paving excluded minor of interval positroids does not
contain an isolated point and any large edge contains at most one element
exclusively.

###### Proof.

Let $M$ be a paving matroid that is also an excluded minor of interval
positroids. Then, the clutter of $M$ is not an interval clutter and proper
deletion of $M$ is a paving matroid whose clutter is an interval clutter.
Therefore, it is clear that the clutter of $M$ does not have an isolated
point. Suppose that a large edge $A$ of $M$ contains more than one element
exclusively. Choose $x\in A$ that is not contained in any other edge of $M$.
Then, the collection of edges of the deletion $M-x$ consists of all edges of
$M$ not containing $x$ and $A\setminus\\{x\\}$. This implies that $M-x$ is not
an interval positroid. So, a large edge cannot contains more than one element
exclusively.

∎

######  Theorem 3.1.

Let $M$ be a paving excluded minor of interval positroids of rank $d\geq 3$.
Let $\mathcal{H}=(V,E)$ be the clutter of $M$. Then, some relaxation of $M$,
or equivalently, some partial clutter of $\mathcal{H}$ falls into one of the
three types of non-interval clutters described below:

  1. (1)

For $m\geq 3$, let $1\leq a_{1},\ldots,a_{m}\leq d-2$ be positive integers
such that there are no three consecutive indices $i,i+1,i+2\mod m$ satisfying
two inequalities

$a_{i}+a_{i+1}>d,\ a_{i+1}+a_{i+2}>d.$

The $d$-paving clutter $O_{a_{1},\ldots,a_{m};d}$ is defined by the clutter
with $m$ edges $A_{1},\ldots,A_{m}$ satisfying the following conditions:

    1. (a)

No vertex is isolated.

    2. (b)

Every vertex is contained in at most two edges.

    3. (c)

$|A_{i}\cap A_{i+1}|=a_{i}$ where indices are taken modulo $m$.

    4. (d)

Each vertex in an edge with a cardinality greater than $d$ is also included in
another edge with a cardinality of $d$.

  2. (2)

For nonnegative integers $0\leq a,b\leq d-3$, $Y_{a,b;d}$ is the $d$-paving
clutter with three edges $A,B,C$ satisfying the following conditions:

    1. (a)

No vertex is isolated.

    2. (b)

$\displaystyle|A|=|B|$ $\displaystyle=d,\quad|C|\geq d$ $\displaystyle|A\cap
C\setminus B|$ $\displaystyle=a,\quad|C\cap B\setminus A|=b,\quad|A\cap
B\setminus C|=0$ $\displaystyle|C\setminus(A\cup B)|$
$\displaystyle>0,\quad|A\cap B\cap C|=1$

    3. (c)

$|C|>d$ only if $C\setminus(A\cup B)$ contains exactly one element.

  3. (3)

For positive integers $1\leq a,b,c\leq d-2$, a,b,c;d is the $d$-paving clutter
with four edges $A,B,C,D$ satisfying the following conditions:

    1. (a)

No vertex is isolated.

    2. (b)

$\displaystyle|A|$ $\displaystyle=|B|=|C|=d,\quad|D|\geq d$
$\displaystyle|A\cap D|$ $\displaystyle=a,\quad|B\cap D|=b,\quad|C\cap D|=c.$

    3. (c)

$A,B,C$ are pairwise disjoint.

    4. (d)

$|D|>d$ only if $a+b+c=|D|$.

###### Proof.

Every non-interval partial clutter of $\mathcal{H}$ is also an excluded minor
of interval positroids. Thus, a non-interval partial clutter cannot have an
isolated vertex by Lemma 3.1.

Since $\mathcal{H}$ is not interval, there is a partial clutter of
$\mathcal{H}$ that is one of five non-interval clutter listed in Proposition
2.1. Suppose that the clutter of $M$ has a partial clutter of type 1. So,
there are three edges $A,B,C$ such that $(A\cap B)\setminus C,(B\cap
C)\setminus A$ and $(A\cap C)\setminus B$ are all nonempty. The contraction of
the set $A\cap B\cap C$ is a paving matroid with a partial clutter consisting
of three edges $A\setminus(A\cap B\cap C),B\setminus(A\cap B\cap C)$ and
$C\setminus(A\cap B\cap C)$ which remains a non-interval clutter of type 1.
Therefore, $M$ is not an excluded minor of interval positroids unless $A\cap
B\cap C$ is empty. If the edge $A$ is large and $A\setminus(B\cup C)$ is
nonempty, then for $x\in A\setminus(B\cup C)$, the deletion $M-x$ has three
edges $A\setminus\\{x\\},B,C$ which is again a non-interval clutter of type 1.
Thus, $A\subset B\cup C$ if $A$ is large. If both $A,B$ are large, then $C$
contains $(A\cup B)\setminus(A\cap B)$ by the previous argument. Then, either
$|A\cap B|>1$ or $2d\leq|A\cup B|-|A\cap B|=|C|$. If the latter case is true,
then $A,B,C$ are all large. And some intersections of two distinct edges must
contain more than one element. So, for both cases, two large edges share more
than one element. Let $x$ be an element in the intersection of two large edges
sharing more than one element. The deletion $M-x$ contains the partial clutter
with three edges $A\setminus\\{x\\},B\setminus\\{x\\},C\setminus\\{x\\}$ which
remains a non-interval clutter of type 1. Therefore, at most one edge can be
large, and the partial clutter $(V,\\{A,B,C\\})$ is the clutter
$O_{a_{1},a_{2},a_{3};d}$ with $a_{1}=|A\cap B|,a_{2}=|B\cap C|,a_{3}=|C\cap
A|$.

Let $A,B,C\in E$ form a partial clutter of type 2. So, $A,B,C$ share a common
point, and each of these contains an element exclusively. If all three sets
$(A\cap B)\setminus C$, $(B\cap C)\setminus A$ and $(A\cap C)\setminus B$ are
nonempty, then the contraction $M/(A\cap B\cap C)$ contains a partial clutter
with three edges $A\setminus(A\cap B\cap C)$, $B\setminus(A\cap B\cap C)$, and
$C\setminus(A\cap B\cap C)$ which is a non-interval clutter of type $1$. By
symmetry, we may assume that $(A\cap B)\setminus C$ is empty. If there is more
than one element in the intersection $A\cap B\cap C$, then the contraction of
an element $x$ contained in $A\cap B\cap C$ will be a paving matroid with the
partial clutter $A\setminus\\{x\\}$, $B\setminus\\{x\\}$, $C\setminus\\{x\\}$
which remains a non-interval clutter of type $2$. Hence, $|A\cap B\cap C|=1$.
Since the partial clutter with three edges $A,B,C$ is a $d$-paving clutter,
the following inequality holds:

$|A\setminus(B\cup C)|=|A|-|A\cap B|\geq 2.$

This implies that $A$ must be a small edge by Lemma 3.1. By symmetry, the edge
$B$ is also small. And $|C|>d$ only if $|B\setminus(A\cup C)|=1$ also by Lemma
3.1. Thus, the partial clutter $(V,\\{A,B,C\\})$ is $Y_{a,b;d}$ where
$a=|(A\cap C)\setminus B|$, $b=|(C\cap B)\setminus A|$.

Suppose that there are four edges $A,B,C,D$ of $\mathcal{H}$ that form a non-
interval clutter of type 3. Contracting common points of $A,B,C,D$, the
partial clutter remains non-interval since it contains the non-interval CA
subhypergraph $\\{12,23,34,41\\}$.

If there is a non-interval partial clutter of type $4$, the condition

$1\leq|A\cap D|,\ |B\cap D|,\ |C\cap D|\leq d-2$

immediately follows from the fact that $A,B,C,D$ form a $d$-paving clutter.
The inequality $|A\setminus(B\cup C\cup D)|=|A\setminus D|>1$ implies that $A$
is small by Lemma 3.1. By symmetry, the other two edges $B,C$ are also small.
If $D$ is large and $D$ contains some element $x$ not contained in $A\cup
B\cup C$, then the deletion $M-x$ will contain the partial clutter
$(V,\\{A,B,C,D\setminus\\{x\\}\\})$ which remains the non-interval clutter of
type 4. Therefore, $D$ can be possibly large only if every element of $D$ is
also contained in one of $A,B,C$. Hence, the partial clutter $A,B,C,D$ is the
clutter a,b,c;d.

Finally, for some $m\geq 4$, suppose that there are $A_{1},\ldots,A_{m}\in E$
such that $A_{i}\cap A_{j}\neq\emptyset$ if and only if $i=j\pm 1\mod m$ which
is a non-interval clutter of type 5. Let $x$ be a vertex that is contained in
only large edges. Since every vertex is contained in at most two edges, it is
either contained in a large edge exclusively or it is contained in the
intersection of two large edges. If $x$ is contained in only one large edge
$A_{i}$, the deletion $M-x$ contains the non-interval partial clutter
$A_{1},\ldots,A_{i}\setminus\\{x\\},\ldots,A_{m}$ of type 5. This is a
contradiction since $M$ is an excluded minor of interval positroids. Now,
suppose that $x$ is contained in the intersection $A_{i}\cap A_{i+1}$ and
$A_{i},A_{i+1}$ are both large. If $|A_{i}\cap A_{i+1}|>1$, then the deletion
$M-x$ contains the partial clutter
$A_{1},\ldots,A_{i}\setminus\\{x\\},A_{i+1}\setminus\\{x\\},\ldots,A_{m}$
which is a non-interval clutter of type 5. So, the intersection $A_{i}\cap
A_{i+1}$ contains exactly one element. Since it is a $d$-paving clutter, the
inequality $|A_{i}\cap A_{i-1}|\leq d-2$ holds, which implies that the set
$A_{i}\setminus(A_{i-1}\cup A_{i+1})$ is nonempty. This goes back to the
previous case and yields a contradiction. Therefore, any vertex contained in a
large edge is contained in another small edge. So the partial clutter
$(V,\\{A_{1},\ldots,A_{m}\\})$ is $O_{a_{1},\ldots,a_{m};d}$ for
$a_{i}=|A_{i}\cap A_{i+1}|$.

∎

$a_{1}$$a_{2}$$a_{3}$$a_{4}$ (a) $O_{a_{1},\ldots,a_{n};d}$ DABC$a$$b$$c$ (b)
a,b,c;d $\emptyset$$a$$d-b-1$$b$$A$$d-a-1$$C$$B$ (c) $Y_{a,b;d}$

Figure 2. Relaxation-minimal list of paving excluded minors of positroids

######  Remark 3.1.

Every paving excluded minor of interval positroids characterized in 3.1 is
“relaxation-minimal”, meaning that further relaxation leads to an interval
positroid.

##  4\. Paving excluded minors of interval positroids that are positroids

Suppose that $M$ is a paving positroid that is an excluded minor of interval
positroids. Then, the clutter of $M$ is a CA clutter. We provide a criterion
for testing whether a given paving positroid $M$ is an excluded minor of
interval positroids.

######  Definition 4.1.

A non-interval CA clutter with three edges is a triangle.

######  Definition 4.2.

A clutter with three edges $A,B,C$ will be called a triangle with a common
point if $A\cap B\cap C\neq\emptyset$, $A\cap C\not\subset B$, and
$B\subsetneq A\cup C$.

It is clear that a clutter $\mathcal{H}$ with three edges $A,B,C$ with a
common point $x\in A\cap B\cap C$ is CA if and only if at least one of $A,B,C$
contains no element exclusively. If $B$ is contained in $A\cup C$, then
$\mathcal{H}$ is non-interval if and only if $A\cap C\not\subset B$. Hence, a
clutter with three edges $A,B,C$, and the nonempty intersection $A\cap B\cap
C$ is a triangle if and only if it is a triangle with a common point,
explaining the terminology.

######  Proposition 4.1.

A paving positroid $M$ of rank $d$ is an excluded minor of interval positroids
if and only if the clutter $\mathcal{H}=(V,E)$ of $M$ satisfies the following
conditions:

  1. (1)

$\mathcal{H}$ is a non-interval, CA $d$-paving clutter.

  2. (2)

If a partial clutter of $\mathcal{H}$ with three edges is a non-interval CA
clutter, then it is not a triangle with a common point and at most one of the
three edges is large.

  3. (3)

Let $A,B$ be two (not necessarily distinct) large edges with the nonempty
intersection $A\cap B$. If $C,D$ are edges overlapping with $A\cup B$ such
that $(A\cup B)\cap C,(A\cup B)\cap D$ are incomparable, then $A\cup B\subset
C\cup D$.

###### Proof.

The first condition is clear since $\mathcal{H}$ is the clutter of a paving
positroid that is not an interval positroid. Since a triangle with two large
edges or a common point is not an excluded minor of interval positroids by
Theorem 3.1, it is necessary that every partial clutter of $\mathcal{H}$ that
is a triangle has at most one large edge without a common point. Now, suppose
that $A,B$ are large edges with a nonempty intersection. Fix an arc-ordering
$f:V\to[n]$ and we identify each vertex and edge with its image under $f$.
Then, the union $A\cup B$ is a cyclic interval. Let $C,D$ are edges
overlapping with the cyclic interval $A\cup B$. If two intersections $(A\cup
B)\cap C,(A\cup B)\cap D$ are incomparable, then both endpoints of $A\cup B$
is contained in $C\cup D$. Assume, for a contradiction, that $C\cup D$ does
not contain $A\cup B$. Then, the following two cases are possible.

  1. (1)

There is an element $x\in A$ not contained in $B\cup C\cup D$ (or $x\in B$ not
contained in $A\cup C\cup D$ by symmetry).

  2. (2)

There is an element $x\in A\cup B$ not contained in $C\cup D$ and $|A\cup
B|\geq 2$.

Suppose that the first condition does not hold. If $|A\cap B|=1$, then
$|A\setminus B|\geq d,|B\setminus A|\geq d$ since $A,B$ are large. The clutter
$\mathcal{H}$ is a paving $d$-clutter and therefore $|(A\cup B)\cap C|,\
|(A\cup B)\cap D|\leq d-2$ which implies that $(A\setminus B)\cup(B\setminus
A)$ can not be contained in $C\cup D$. This is a contradiction since the first
condition does not hold. Thus, either the first or the second condition holds.
Now, $\mathcal{H}$ remains non-interval after deleting an element $x\in A$ not
contained in $B\cup C\cup D$ or $x\in A\cup B$ not contained in $C\cup D$ when
$|A\cap B|\geq 2$.

Conversely, suppose that the contraction $M/x$ is a non-interval, CA
hypergraph for some $x\in V$. By Lemma 2.3, the edges of the clutter of $M/x$
is the collection of all sets $H\setminus\\{x\\}$ where $H\in E$ and $x\in H$.
Therefore, the collection $\mathcal{H}_{x}$ of all edges of $\mathcal{H}$
containing $x$ is a non-interval and CA partial clutter. This implies that
there are more than two edges in the clutter $\mathcal{H}_{x}$. By Corollary
2.1, the clutter $\mathcal{H}_{x}$ contains a non-interval partial clutter of
type 1 or 5. But edges of the type $5$ clutters can not share a vertex in
common. Hence, there is a partial clutter of type 1 with three edges in
$\mathcal{H}_{x}$ that is a CA clutter sharing a point $x$. This is a triangle
with a common point.

Now, assume that the clutter $\mathcal{H}-x$ of the deletion $M-x$ is not an
interval clutter for some $x\in[n]$. Again, by Corollary 2.1, this is
equivalent to some partial clutter of $\mathcal{H}-x$ is a non-interval
clutter of type 1 or 5. Then, there are the following four possibilities:

  1. (1)

$x$ is contained in some three large edges covering the vertex set $V$ and
forming a non-interval clutter of type 1.

  2. (2)

There is a non-interval partial clutter of type 1 such that $x$ is exactly
contained in two adjacent large edges of the partial clutter.

  3. (3)

There is a non-interval partial clutter of type 5 such that $x$ is exactly
contained in two adjacent large edges of the partial clutter.

  4. (4)

There is a non-interval partial clutter of type 1 or 5 such that $x$ is
exactly contained in one large edge of the partial clutter.

The first case is impossible if there is no partial clutter which is a
triangle with a common point. The second case is impossible if there is no
partial clutter which is a triangle with two large edges. The third and fourth
cases cannot occur unless the large edges $A$ and $B$ containing $x$ violate
the third condition. Therefore, the three given conditions are sufficient.

∎

##  5\. Paving excluded minors of interval positroids with four dependent
hyperplanes

In this section, we classify all paving, non-positroid excluded minors of
interval positroids with four dependent hyperplanes. By Theorem 3.1, it is
either the clutter a,b,c;d, or a $d$-paving clutter obtained by adding one
edge to $Y_{a,b;d}$ or $O_{a_{1},a_{2},a_{3};d}$.

######  Theorem 5.1.

Let $M$ be a paving matroid of rank $d$ with exactly four edges
$A,B,C_{1},C_{2}$. If the partial clutter $(V,E=\\{A,B,C_{1}\\})$ is
$Y_{a_{1},b_{1};d}$ with the common point $v$, then $M$ is an excluded minor
of interval positroids if and only if one of the following statements hold:

  1. (1)

$|C_{1}|=d+1$ and $C_{2}=(A\setminus C_{1})\cup(C_{1}\setminus(A\cup
B))\cup(B\setminus C_{1})$.

  2. (2)

The partial clutter $(V,E=\\{A,B,C_{2}\\})$ is $Y_{a_{2},b_{2};d}$ where
$|(A\cap C_{2})\setminus\\{v\\}|=a_{2},|(B\cap C_{2})\setminus\\{v\\}|=b_{2}$
with the same common point $v$, and the clutter
$(V\setminus\\{v\\},\\{A\setminus\\{v\\},B\setminus\\{v\\},C_{1}\setminus\\{v\\},C_{2}\setminus\\{v\\}\\})$
is an interval $(d-1)$-paving clutter.

These clutters will be denoted by
$Y_{a_{1},b_{1};d}^{\prime},Y_{a_{1},a_{2},b_{1},b_{2};d}$ respectively.

###### Proof.

Checking whether these clutters are indeed excluded minors is omitted.

####  Case 1: $v\notin C_{2}$.

If $C_{2}$ is contained in $A\cup C_{1}$, then the partial clutter with three
edges $A,C_{1},C_{2}$ is a triangle with a common point. Hence, the
intersection $C_{2}\cap(A\setminus C_{1})$ is nonempty. By symmetry, the
intersection $C_{2}\cap(B\setminus C_{1})$ is also nonempty. If there is an
element $x\in C_{1}\setminus(A\cup B)$ not contained in the edge $C_{2}$, then
the matroid $M-x$ has three edges $A,B,C_{2}$ which is a non-interval clutter
of type 1. Therefore, the set $C_{1}\setminus(A\cup B)$ must be contained in
$C_{2}$. For the same reason, both $A\setminus C_{1}$ and $B\setminus C_{1}$
are contained in $C_{2}$. Now, if there is an element $x$ contained in $A\cap
C_{1}\cap C_{2}$, then the contraction $M/x$ is a non-interval clutter of type
1. Therefore, $A\cap C_{1}\cap C_{2}$ is empty. By symmetry, $B\cap C_{1}\cap
C_{2}$ is also empty. Hence, $C_{2}$ must be $(A\setminus
C_{1})\cup(C_{1}\setminus(A\cup B))\cup(B\setminus C_{1})$.

If $|C_{2}|>d$, for $x\in A\setminus C_{1}$, $M/x$ has three edges
$B,C_{1},C_{2}\setminus\\{x\\}$ which is a non-interval clutter of type 1.
Hence, $|C_{2}|=d$. If $|A|=|B|=|C_{1}|=d$, then $a+b=|C_{1}\cap(A\cup B)|\leq
d-2$ since $C_{1}\setminus(A\cup B)$ is nonempty. But

$\displaystyle|C_{2}|$ $\displaystyle=d$ $\displaystyle=|A\setminus
C_{1}|+|C_{1}\setminus(A\cup B)|+|B\setminus C_{1}|$
$\displaystyle=(d-a-1)+(d-a-b-1)+(d-b-1)$ $\displaystyle=3(d-1)-2a-2b$

implies that $2d=2a+2b+3$ which is a contradiction since $a+b\leq d-2$.
Finally, assume that the edge $C_{1}$ is large. This implies that
$|C_{1}\setminus(A\cup B)|=1$ and $a+b=|C_{1}|-2\geq d-1$ by Theorem 3.1. But,
we have

$\displaystyle|C_{2}|$ $\displaystyle=d$ $\displaystyle=|A\setminus
C_{1}|+|C_{1}\setminus(A\cup B)|+|B\setminus C_{1}|$
$\displaystyle=(d-a-1)+1+(d-b-1)$ $\displaystyle=2d-a-b-1.$

This implies that $a+b=d-1$ and $|C_{1}|=d+1$. This gives us the first case in
the list.

####  Case 2: $v\in C_{2}$.

Let $X^{\prime}$ be the set $X\setminus\\{v\\}$ for edges $X=A,B,C_{1},C_{2}$.
Since $v\in C_{2}$, the contraction $M/v$ has four edges
$A^{\prime},B^{\prime},C_{1}^{\prime},C_{2}^{\prime}$ which must be an
interval clutter. If both $A^{\prime}\setminus C_{1}^{\prime}$ and
$B^{\prime}\setminus C_{1}^{\prime}$ share an element with $C_{2}^{\prime}$,
then $C_{2}^{\prime}$ must contain $C_{1}^{\prime}$ which is impossible since
$(V,\\{A,B,C_{1},C_{2}\\})$ is a clutter. Hence, $C_{2}^{\prime}$ is properly
contained in either $A^{\prime}\cup C_{1}^{\prime}$ or $B^{\prime}\cup
C_{1}^{\prime}$. By symmetry, we may assume that $C_{2}^{\prime}\subsetneq
B^{\prime}\cup C_{1}^{\prime}$. To avoid a triangle with a common point as a
partial clutter, the intersection $B^{\prime}\cap C_{1}^{\prime}$ is contained
in $C_{2}^{\prime}$. If there is an element $x\in C_{1}\setminus(A\cup B)$ not
contained in $C_{2}$, then the clutter of the deletion
$M-(C_{1}\setminus(A\cup B\cup C_{2}))$ is the clutter
$Y_{0,|C_{2}^{\prime}\cap B^{\prime}|;d}$ with three edges $A,B,C_{2}$ which
is not interval. Hence, $C_{2}^{\prime}$ contains the set
$C_{1}\setminus(A\cup B)$. Thus, the partial clutter $A,B,C_{2}$ is the
clutter $Y_{|A^{\prime}\cap C_{2}^{\prime}|,|C_{2}^{\prime}\cap
B^{\prime}|;d}$ with $C_{1}\setminus(A\cup B)=C_{2}\setminus(A\cup B)$.

∎

Before classifying paving excluded minors of interval positroids obtained by
adding an edge to the clutter $O_{a_{1},a_{2},a_{3};d}$, we introduce the
following notation for convenience. Edges of $O_{a_{1},a_{2},a_{3};d}$ will be
denoted by $A,B,C$ and let

$\displaystyle S$ $\displaystyle=A\setminus(B\cup C),S^{\prime}=B\cap C,$
$\displaystyle T$ $\displaystyle=B\setminus(C\cup A),T^{\prime}=C\cap A,$
$\displaystyle U$ $\displaystyle=C\setminus(A\cup B),U^{\prime}=A\cap B,$
$\displaystyle a$ $\displaystyle=|S^{\prime}|,b=|T^{\prime}|,c=|U^{\prime}|.$

Notice that if $|A|=|B|=|C|=d$, then $|S|=a+k$, $|T|=b+k$, and $|U|=c+k$ for
some $k\geq-\min\\{a,b,c\\}$. Throughout the paper, the variable $k$ will
consistently represent this difference in cardinality.

######  Theorem 5.2.

Let $M$ be a paving excluded minor of interval positroids of rank $d$ with
exactly four dependent hyperplanes $A,B,C,D$. Suppose that the partial clutter
$(V,E=\\{A,B,C\\})$ is $O_{a,b,c;d}$. If $M$ is not a positroid, then
$|A|=|B|=|C|=d$, and the fourth edge $D$ of the clutter $\mathcal{H}$ of $M$
is one of the following two possibilities:

  1. (1)

$k=0$ and $D=S\cup T\cup U$.

  2. (2)

$D=S^{\prime}\cup T^{\prime}\cup U^{\prime}$ for $a,b,c,k$ satisfying

$2\leq|S|=a+k\leq a,\ 2\leq|T|=b+k\leq b,\ 2\leq|U|=c+k\leq c.$

The first clutter will be denoted by $\Delta_{a,b,c}^{1}$ and the second
clutter will be denoted by $\Delta_{a,b,c;k}^{2}$.

###### Proof.

Verifying that these two clutters are indeed excluded minors of interval
positroids is straightforward. So, we focus on proving that these are only
possibilities.

####  Case 1: No element of $\mathcal{H}$ is contained in three edges.

Hence, $D$ is contained in the set $S\cup T\cup U$. If $A$ is large, then $B$
and $C$ are small and $A\subset B\cup C$ by Theorem 3.1. Therefore, the
cardinality of the set $S\cup T\cup U$ is $|B|+|C|-|A|-|S|<2d-|A|\leq d-1$.
This is a contradiction since $d\leq|D|$. Therefore $A,B,C$ are small. Since
$D\subseteq S\cup T\cup U$ and $d=a+b+c+k,\ |S\cup T\cup U|=a+b+c+3k$, $k$
must be some nonnegative integer. This implies that $S$, $T$, and $U$ are all
nonempty. Since $\mathcal{H}$ is a clutter, $D$ is not contained in any of
$S$, $T$, and $U$. By symmetry, we may assume that $S\cap D$ and $T\cap D$ are
nonempty. If there is an element $x\in U$ not contained in $D$, then the
clutter of the deletion $M-x$ has three edges $A$, $B$, and $D$ which is a
non-interval clutter of type 1 since every pairwise intersection is nonempty.
Therefore, it follows that $U\subset D$, and similarly, both $S$ and $T$ are
also contained in $D$. Thus, we have shown that $D=S\cup T\cup U$. It remains
to show that $D$ is small. Note that $D$ is large if and only if $k>0$. If $D$
is large, then for any element $x\in U$, the clutter of the deletion $M-x$
contain three edges $A$, $B$, and $D\setminus\\{x\\}$. The clutter with three
edges $A$, $B$, and $D\setminus\\{x\\}$ is a non-interval clutter of type 1.
Therefore, $M-x$ is not an interval positroid if $D$ is large. So, $k=0$ and
$|S|=a,|T|=b,|U|=c$, and $D=S\cup T\cup U$.

####  Case 2: Some element $v\in S^{\prime}$ is contained in $D$, and $D\cap
T^{\prime}$ and $D\cap U^{\prime}$ are empty.

#### Step 1: Three edges $A$, $B$, and $C$ are small.

If $A$ is large, then $S=\emptyset$ which implies that $D$ is contained in
$S^{\prime}\cup T\cup U$. Since $B,C$ are small, $|S^{\prime}|+|T|+|U|<d$.
This is a contradiction because $D$ is contained in $S\cup S^{\prime}\cup
T\cup U$. If $B$ is large, then $B=S^{\prime}\sqcup U^{\prime}$. This implies
that $1<|S^{\prime}|,|U^{\prime}|$ since $|S^{\prime}|,|U^{\prime}|\leq d-2$.
Thus, $D\cap S$ is nonempty since $D$ is not contained in $C$. For an element
$x\in U^{\prime}$, the clutter of the deletion $M-x$ consists of three edges
$B\setminus\\{x\\}$, $C$, and $D$ sharing the element $v$. Elements of
$U^{\prime}\setminus\\{x\\}$, $T^{\prime}$, and $D\cap S$ are exclusively
contained in the edges $B\setminus\\{x\\}$, $C$, and $D$ respectively.
Therefore, the clutter of $M-x$ is not an interval clutter. By symmetry, the
edge $C$ can not be large either.

#### Step 2: $D=S\cup T\cup U\cup S^{\prime}$.

The intersection $D\cap S$ must be nonempty because if not, $D$ is contained
in the set $B\cup C$, which implies that either $\mathcal{H}$ is interval, or
the partial clutter with edges $B$, $C$, and $D$ forms a triangle with a
common point. Then, the partial clutter obtained by removing the edge $B$ is
non-interval. Therefore, $T$ must be entirely contained in $D$; otherwise, we
could delete an element from $T\setminus D$ to obtain a proper minor with
three edges $A,C,D$. By symmetry, $U$ is also contained in $D$. If there is an
element $x\in S^{\prime}$ not contained in $D$, then the clutter of the
contraction $M/v$ consists of three edges $B\setminus\\{v\\}$,
$C\setminus\\{v\\}$, and $D\setminus\\{v\\}$ with
$((B\setminus\\{v\\})\cap(C\setminus\\{v\\}))\setminus(D\setminus\\{v\\})$
nonempty. This leads to the false conclusion that $M/v$ has three edges
$B\setminus\\{v\\}$, $C\setminus\\{v\\}$, and $D\setminus\\{v\\}$ which form a
non-interval clutter of type 1. So, $S^{\prime}$ is also contained in $D$.
Finally, if there is an element $x\in S$ not contained in $D$, then the
clutter of the deletion $M-x$ has three edges $B,C,D$ which form a non-
interval clutter of type 2 in Proposition 2.1. Therefore, $D=S\cup T\cup U\cup
S^{\prime}$. The cardinality of $D$ is $|S|+|T|+|U|+|S^{\prime}|=a+b+c+3k+1$.
Since $d\leq|D|$ and $d=a+b+c+k$, $k$ must be some nonnegative integer.
Therefore, $D$ is large. Then, for any $x\in T$, the deletion $M-x$ has three
edges $A,C,D\setminus\\{x\\}$ which is non-interval. Therefore, this case is
impossible.

####  Case 3: $S^{\prime}\cap D$ and $T^{\prime}\cap D$ are nonempty and
$U^{\prime}\cap D$ is empty.

Since the partial clutter $A$, $B$, and $D$ is a non-interval clutter of type
1, $U$ is contained in $D$. If $D$ is contained in $A\cup C$, then either
$\mathcal{H}$ is an interval clutter or the partial clutter $A,C,D$ is a
triangle with a common point. Hence, the intersection $D\cap T$ is nonempty.
By symmetry, the intersection $D\cap S$ is also nonempty. Since the edge $C$
is not contained in $D$, either $S^{\prime}\not\subset D$ or
$T^{\prime}\not\subset D$. If $S^{\prime}\not\subset D$, then the contraction
$M/v$ of an element $v\in D\cap S^{\prime}$ has three edges
$B\setminus\\{v\\},C\setminus\\{v\\},D\setminus\\{v\\}$ which form a non-
interval clutter of type 1. Therefore, this case is impossible.

####  Case 4: $S^{\prime}\cap D$, $T^{\prime}\cap D$, and $U^{\prime}\cap D$
are all nonempty.

If some element of $S^{\prime}$ is not contained in $D$, then the clutter of
the contraction $M/x$ of an element $x\in S^{\prime}\cap D$ is a non-interval
clutter of type 1. Hence $S^{\prime}$ is contained in the edge $D$. By
symmetry, the set $S^{\prime}\cup T^{\prime}\cup U^{\prime}$ is contained in
the edge $D$.

#### Step 1: Three edges $A,B,C$ are small.

If $A$ is large, then $A=T^{\prime}\sqcup U^{\prime}$. Therefore $A$ is
contained in $D$ by the above observation. By symmetry, $A,B,C$ are all small.

#### Step 2: $D=S^{\prime}\cup T^{\prime}\cup U^{\prime}$.

Since edges $A,B,C$ are not contained in the edge $D$, there are elements
$x\in S,y\in T,z\in U$ that are not contained in $D$. Now, if there is an
element in $S$ contained in $D$, then the clutter of the deletion $M-x$
consists of three edges $B,C,D$ sharing vertices in $S^{\prime}$, and each of
which contains an element exclusively. Thus, three edges $B,C,D$ form a non-
interval clutter of type 2. Hence, $D$ must be $S^{\prime}\cup T^{\prime}\cup
U^{\prime}$.

#### Step 3: $2\leq|S|\leq a$, $2\leq|T|\leq b$, $2\leq|U|\leq c$.

$|S|=a+k,|T|=b+k,|U|=c+k$ because $A,B,C$ are small. Since $d=a+b+c+k$ and
$|D|=a+b+c$, $k$ is not positive. Moreover, the cardinality of the set
$S=A\setminus D$ is at least $2$ since $\mathcal{H}$ is a $d$-paving clutter.
By symmetry, the given inequalities hold.

∎

In summary, Figure 3 illustrates all non-positroid, paving matroids with four
edges that are excluded minors of interval positroids. The fourth edge is
indicated by blue arcs and segments.

DABC$a$$b$$c$ (a) a,b,c;d
$\emptyset$$a_{1}$$d-a_{1}-1$$b_{1}$$A$$C$$B$$d-b_{1}-1$ (b)
$Y^{\prime}_{a_{1},b_{1};d}$ for $a_{1}+b_{1}=d-1$
$\emptyset$$A$$a_{1}$$b_{1}$$C_{1}$$\neq\emptyset$$v$$B$ (c)
$Y_{a_{1},a_{2},b_{1},b_{2};d}$ aAbBcC$a$$b$$c$ (d) $\Delta_{a,b,c}^{1}$
$a+k$$A$$b+k$$B$$c+k$$C$abc (e) $\Delta_{a,b,c;k}^{2}$ for $k\leq 0$

Figure 3. Non-positroid paving excluded minors of interval positroids with
four edges

##  6\. Paving, non-positroid excluded minors of interval positroids with more
than five edges

In this section, we classify all paving excluded minors of interval positroids
with more than four edges. Again, we focus on paving excluded minors of
interval positroids that are not positroids.

###  6.1. Local compatibility implies global compatibility for CA clutters

Let $\mathcal{H}=(V,E=\\{A_{1},\ldots,A_{m}\\})$ be a non-interval CA clutter
with every vertex is contained in at most two edges throughout this
subsection. By Lemma 2.2, every arc ordering of $\mathcal{H}$ maps each
intersection $A_{i}\cap A_{i+1}$ and each set of isolated points
$A_{i}\setminus(A_{i-1}\cup A_{i+1})$ to disjoint cyclic intervals. These
cyclic intervals will be called the “blocks” of $\mathcal{H}$. These blocks
appear in the order $A_{1}\cap A_{m},A_{1}\setminus(A_{m}\cup A_{2}),A_{1}\cap
A_{2},\ldots,A_{m}\cap A_{m-1},A_{m}\setminus(A_{1}\cup A_{m-1})$ for every
arc ordering. Let $T_{1},T_{2},\ldots,T_{2m}$ be these blocks in the given
order. Let $\mathcal{H}+B$ denote the hypergraph obtained by adding a new edge
$B$ to the hypergraph $\mathcal{H}$. We state the necessary and sufficient
condition for $\mathcal{H}+B$ to be a CA clutter in the following lemma.

######  Lemma 6.1.

Let $\mathcal{H}=(V,E=\\{A_{1},\ldots,A_{m}\\})$ be a non-interval CA clutter
such that every vertex is contained in at most two edges. The hypergraph
$\mathcal{H}+B$, obtained by adjoining another edge $B$, is also a CA clutter
if and only if

  1. (1)

for some unique $i$, $A_{i}\cap A_{i+1}\subset B\subset A_{i}\cup A_{i+1}$;

  2. (2)

the set of indices $I:=\\{i\in[2m]\mid T_{i}\cap B\neq\emptyset\\}$ is a
cyclic interval of $[2m]$ and $B$ and $T_{i}$ overlap only if $i$ is one of
the two endpoints of $I$.

###### Proof.

The sufficiency of two conditions is clear since every arc-ordering of
$\mathcal{H}$ maps each block $T_{1},\ldots,T_{2m}$ to disjoint cyclic
intervals in the given order by Lemma 2.2. The necessity of the second
condition also follows from this fact. Now, it remains to prove the necessity
of the first condition.

Suppose that an arc ordering of $\mathcal{H}$ is given such that $B$ is a
cyclic interval. If $B$ contains four consecutive blocks, then $B$ contains
$A_{i}$ for some $i$ which is a contradiction. If the cyclic interval $B$
contains no block, then $B$ is contained in some $A_{i}$ which is also a
contradiction.

Now, if the cyclic interval $B$ contains exactly one block $T_{j}$, then $B$
is contained in the union of three consecutive blocks $T_{j-1}\cup T_{j}\cup
T_{j+1}$. Therefore $T_{j}$ must be some intersection $A_{i}\cap A_{i+1}$
because otherwise $B$ is contained in some edge $A_{i}$. If $B$ contains
exactly two consecutive blocks, then one of the two blocks must be the
intersection of two edges $A_{i}\cap A_{i+1}$. Finally, if $B$ contains three
consecutive blocks, then the middle block must be some intersection $A_{i}\cap
A_{i+1}$ since $B$ does not contain some $A_{i}$. For all these cases, it is
clear that $B$ is contained in the union $A_{i}\cup A_{i+1}$.

∎

The next lemma characterizes three possible cases of adding two edges to
construct a new CA clutter from $\mathcal{H}$.

######  Lemma 6.2.

Let $\mathcal{H}_{12}:=(V,E\cup\\{B_{1},B_{2}\\})$ be a clutter obtained by
adding two edges to $\mathcal{H}$. Let $\mathcal{H}_{i}:=(V,E\cup\\{B_{i}\\})$
be the clutter obtained by only adding one edge $B_{i}$. Suppose that
$\mathcal{H}_{i}$ is CA for $i=1,2$. The clutter $\mathcal{H}_{12}$ is CA if
and only if one of the following three cases holds.

  1. (1)

There is some intersection $A_{i}\cap A_{i+1}$ contained in both $B_{1}$ and
$B_{2}$, and $A_{i}\cap B_{1}\subset A_{i}\cap B_{2},\ A_{i+1}\cap
B_{2}\subset A_{i+1}\cap B_{1}$.

  2. (2)

$B_{1}$ and $B_{2}$ contain $A_{i-1}\cap A_{i}$ and $A_{i}\cap A_{i+1}$
respectively. And, either $B_{1}$ and $B_{2}$ are disjoint, or the set
$A_{i}\setminus(A_{i-1}\cup A_{i+1})$ is contained in the union $B_{1}\cup
B_{2}$.

  3. (3)

$B_{1}$ and $B_{2}$ contain $A_{i-1}\cup A_{i}$ and $A_{i+1}\cap A_{i+2}$
respectively. And, either $B_{1}$ and $B_{2}$ are disjoint, or the set
$A_{i}\cap A_{i+1}$ is contained in the union $B_{1}\cup B_{2}$.

###### Proof.

Let $A_{i}\cap A_{i+1}\subset B_{1}\subset A_{i}\cup A_{i+1}$ and $A_{j}\cap
A_{j+1}\subset B_{2}\subset A_{j}\cup A_{j+1}$ by Lemma 6.1. Let
$T_{l,-},T_{l,+}$ be the blocks that have nonempty intersections with $B_{l}$
at each end of $B_{l}$. An arc ordering of $\mathcal{H}_{l}$ is determined by
orders of $T_{l,-}$, $T_{l,+}$ such that $B_{l}\cap T_{l,-}$ (resp. $B_{l}\cap
T_{l,+}$) is an interval sharing the largest (resp. smallest) endpoint with
$T_{l,-}$ (resp. $T_{l,+}$). The clutter $\mathcal{H}_{12}$ is CA if and only
if there is a common arc ordering of $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$.
Therefore, no such common arc ordering exists if and only if

  1. (1)

$T=T_{1,-}=T_{2,-}$, and $B_{1}\cap T,B_{2}\cap T$ are incomparable;

  2. (2)

$T=T_{1,+}=T_{2,-}$, and $B_{1}\cap B_{2}\cap T\neq\emptyset$,
$T\neq(B_{1}\cap T)\cup(B_{2}\cap T)$.

$T=T_{1,-}=T_{2,-}$ is possible only if $i=j$. So in this case a common
interval ordering of $T$ exists if and only if $A_{i}\cap B_{1}\subset
A_{i}\cap B_{2}$ (or $A_{i}\cap B_{1}\supset A_{i}\cap B_{2}$). Since
$B_{1},B_{2}$ are incomparable, this implies that $A_{i+1}\cap B_{2}\subset
A_{i+1}\cap B_{1}$ (or $A_{i+1}\cap B_{2}\supset A_{i+1}\cap B_{1}$).

$T=T_{1,+}=T_{2,-}$ is possible only if $j=i+1,\ T=A_{i+1}\setminus(A_{i}\cup
A_{i+2})$ or $j=i+2,\ T=A_{i+1}\cap A_{i+2}$. This follows that case 2 or 3
must be true if there is a common arc ordering of $\mathcal{H}_{1}$ and
$\mathcal{H}_{2}$.

∎

######  Lemma 6.3.

Let $V$ be a finite set of cardinality $n$. Suppose that there are two flags
$A_{1}\subset A_{2}\subset\cdots\subset A_{m}$ and $B_{1}\supset
B_{2}\supset\cdots\supset B_{p}$ of subsets of $V$. For any $i\in[m]$ and
$j\in[p]$, assume that

(1) $A_{i}\cap B_{j}\neq\emptyset\Rightarrow A_{i}\cup B_{j}=V.$

Then, there is an interval ordering of the hypergraph $\mathcal{H}$ with the
set of vertices $V$ and edges $E=\\{A_{1},\ldots,A_{m},B_{1},\ldots,B_{p}\\}$
that maps each $A_{i}$ to the initial interval $[1,|A_{i}|]$ and each $B_{j}$
to the terminal interval $[n-|B_{j}|+1,n]$.

###### Proof.

Suppose that $|A_{i+1}\setminus A_{i}|>1$. Choose $x\in A_{i+1}\setminus
A_{i}$ that is contained in $B_{j}$ for $j=\max\\{l\mid A_{i+1}\cap
B_{l}\neq\emptyset\\}$. By adjoining $A_{i+1}\setminus\\{x\\}$ to the original
flag $A_{1}\subset\cdots\subset A_{m}$, the assumption (1) is preserved for
this new flag. Therefore, it is possible to complete both flags while
maintaining the property (1). Assuming both flags are complete, the bijection
sending the unique element of $A_{i}\cap B_{n-i+1}$ to $i$ meets all
requirements.

∎

Now, we prove the following theorem, which roughly states that “local
compatibility implies global compatibility for CA clutters”.

######  Theorem 6.1.

Let $\mathcal{H}^{\prime}=(V,E=\\{A_{1},\ldots,A_{m},B_{1},\ldots,B_{p}\\})$
be a clutter with the partial clutter
$\mathcal{H}=(V,\\{A_{1},\ldots,A_{m}\\})$ that is a non-interval, CA clutter
with every vertex contained in at most two edges. If the partial clutter
$(V,\\{A_{1},\ldots,A_{m},B_{r},B_{s}\\})$ is CA for all $r,s\in[p]$, then the
clutter $\mathcal{H}$ is CA.

###### Proof.

By Lemma 6.1, the set $\\{B_{1},\ldots,B_{p}\\}$ of edges can be partitioned
into subsets $\mathcal{B}_{i}:=\\{B_{r}\mid A_{i}\cap A_{i+1}\subset
B_{r}\subset A_{i}\cup A_{i+1}\\}$ for $i=1,\ldots,m$. Since the clutter
$(V,\\{A_{1},\ldots,A_{m},B_{r},B_{s}\\})$ is CA for every
$B_{r},B_{s}\in\mathcal{B}_{i}$, $A_{i}\cap B_{r}\subset A_{i}\cap B_{s}$ and
$A_{i+1}\cap B_{s}\subset A_{i+1}\cap B_{r}$ by Lemma 6.2. Therefore, the
collection of intersections $\mathcal{F}_{i}(T):=\\{B_{r}\cap T\mid
B_{r}\in\mathcal{B}_{i}\\}$ is a flag of $T$ for each block $T$.

Suppose that $T=A_{i}\cap A_{i+1}$. Then only nontrivial flags are
$\mathcal{F}_{i-1}(T)$ and $\mathcal{F}_{i+1}(T)$. By the third case of Lemma
6.2, these two flags satisfy the assumption of Lemma 6.3. By Lemma 6.3, there
is an order of $T$ such that $\mathcal{F}_{i-1}(T)$ is a flag of initial
intervals and $\mathcal{F}_{i+1}(T)$ is a flag of terminal intervals. If
$T=A_{i}\setminus(A_{i-1}\cup A_{i+1})$, then only nontrivial flags are
$\mathcal{F}_{i}(T)$ and $\mathcal{F}_{i+1}(T)$. Again by Lemma 6.3, there is
an order of $T$ sending $\mathcal{F}_{i}(T)$ to a flag of initial intervals
and $\mathcal{F}_{i+1}(T)$ to a flag of terminal intervals. Hence, the
original hypergraph has an arc ordering obtained by cyclically concatenating
the linear orders of each block.

∎

###  6.2. Paving, non-positroid excluded minor of interval positroids with
more than four edges

First, we prove that Theorem 6.1 holds in a stronger sense for paving clutters
that are excluded minors of interval positroids.

######  Lemma 6.4.

Let $M$ be a paving excluded minor of interval positroids with a partial
clutter $O_{a_{1},\ldots,a_{m};d}$. Suppose that for every edge $B$ of $M$,
the clutter $O_{a_{1},\ldots,a_{m};d}+B$ is CA. Then, the clutter of $M$ is CA
and therefore $M$ is a positroid.

###### Proof.

By Lemma 6.2, it is enough to prove that the clutter obtained by adjoining two
edges to $O_{a_{1},\ldots,a_{m};d}$ is CA. Suppose that the clutter
$O_{a_{1},\ldots,a_{m};d}+B_{1}+B_{2}$ is not CA for some $A_{i}\cap
A_{i+1}\subset B_{1},B_{2}\subset A_{i}\cup A_{i+1}$. Then, there is some
block $T$ of $O_{a_{1},\ldots,a_{m};d}$ such that $T\cap B_{1}$ and $T\cap
B_{2}$ are incomparable. Without losing generality, suppose that $T$ is
contained in $A_{i}\setminus A_{i+1}$. The contraction $M/(A_{i}\cap A_{i+1})$
contains four edges $A_{i}^{\prime}$, $A_{i+1}^{\prime}$, $B_{1}^{\prime}$,
and $B_{2}^{\prime}$ where $X^{\prime}:=X\setminus(A_{i}\cap A_{i+1})$. Since
$B_{1}^{\prime}$ and $B_{2}^{\prime}$ are not contained in $A_{i}^{\prime}$,
both intersections $B_{1}^{\prime}\cap A_{i+1}^{\prime}$ and
$B_{2}^{\prime}\cap A_{i+1}^{\prime}$ are nonempty. If $B_{1}^{\prime}\cap
B_{2}^{\prime}\cap A_{i+1}^{\prime}$ is nonempty, then the partial clutter
$A_{i}^{\prime}$, $B_{1}^{\prime}$, and $B_{2}^{\prime}$ is a non-interval
clutter of type 1 which is a contradiction. Thus, we may assume that
$B_{1}^{\prime}\cap A_{i+1}^{\prime}$ and $B_{2}^{\prime}\cap
A_{i+1}^{\prime}$ are disjoint. For the same reason, $B_{1}^{\prime}\cap
A_{i}^{\prime}$ and $B_{2}^{\prime}\cap A_{i}^{\prime}$ must be disjoint.
Thus, the four edges $B_{1}^{\prime}$, $B_{2}^{\prime}$, $A_{i}^{\prime}$, and
$A_{i+1}^{\prime}$ form a non-interval clutter of type 5. Therefore, the
contraction $M/(A_{i}\cap A_{i+1})$ is not an interval positroid which is a
contradiction.

Now, suppose that the clutter $O_{a_{1},\ldots,a_{m};d}+B_{1}+B_{2}$ is not
CA, and for some $i\neq j$, $A_{i}\cap A_{i+1}\subset B_{1}\subset A_{i}\cup
A_{i+1}$ and $A_{j}\cap A_{j+1}\subset B_{1}\subset A_{j}\cup A_{j+1}$. Then,
there is a block $T$ such that $B_{1}\cap B_{2}\cap T$ is nonempty and $T$ is
not contained in $B_{1}\cup B_{2}$. Then, the clutter of the deletion
$M-(T\setminus(B_{1}\cup B_{2}))$ is non-interval which is a contradiction.
Therefore, $O_{a_{1},\ldots,a_{m};d}+B_{1}+B_{2}$ is CA for every
$B_{1},B_{2}$. This implies that the original matroid is a positroid.

∎

######  Corollary 6.1.

Let $M$ be a paving excluded minor of interval positroids satisfying the
following conditions:

  1. (1)

Edges of $M$ are $A_{1},\ldots,A_{m},B_{1},\ldots,B_{p}$ for $p\geq 2$.

  2. (2)

The partial clutter consisting of edges $A_{1},\ldots,A_{m}$ is
$O_{a_{1},\ldots,a_{m};d}$.

  3. (3)

$M$ is not a positroid.

Then, for some $r\in[p]$, the matroid obtained by relaxation of $B_{r}$ is a
paving excluded minor of interval positroids that is not a positroid.

###### Proof.

If the relaxation of $B_{r}$ is a positroid for all $r\in[p]$, then every
partial clutter $A_{1},\ldots,A_{m},B_{s}$ is CA for all $s\in[p]$. Hence, the
clutter of the original matroid $M$ is CA by Lemma 6.4. Therefore, some
relaxation of $B_{r}$ is a paving excluded minor of interval positroids that
is not a positroid.

∎

Therefore, any paving, non-positroid excluded minor of interval positroids
with five edges can be obtained either by adding one edge to
$O_{a_{1},\ldots,a_{4};d}$ or by adding one edge to non-positroid paving
excluded minors with four edges in FIGURE 3. The next three propositions rule
out three possibilities.

######  Proposition 6.1.

Suppose that $M$ is a non-positroid, paving excluded minor of interval
positroids of rank $d$ with edges $A_{1},\ldots,A_{m},B$ for some $m\geq 4$.
Then, the partial clutter obtained by removing one edge $B$ is not
$O_{a_{1},\ldots,a_{m};d}$.

###### Proof.

Suppose that the partial clutter obtained by removing $B$ is
$O_{a_{1},\ldots,a_{m};d}$.

First, assume that $B$ is contained in $A_{1}\cup A_{2}$. If $A_{1}\cap A_{2}$
is not contained in $B$, then three edges $A_{1},A_{2},B$ form a non-interval
CA clutter. Since any element $x\in A_{3}\cap A_{4}$ is not contained in
$A_{1},A_{2},B$, the deletion $M-x$ is not an interval positroid. Hence,
$A_{1}\cap A_{2}\subset B$. Since $M$ is not a positroid, we may assume that
$B$ and $A_{2}\setminus(A_{1}\cup A_{3})$ overlap and $B\cap A_{2}\cap
A_{3}\neq\emptyset$. Then $A_{2},A_{3},B$ have a common point and each has
exclusive elements which implies that $B,C,D_{2}$ is a partial clutter of type
2. Since $A_{1}$ is not contained in $B$ there is an element $x$ of $A_{1}$
not contained in $A_{2}\cup A_{3}\cup B$. Therefore, the deletion $M-x$ is not
an interval positroid which is a contradiction.

Now, suppose that $B$ contains some element of $A_{1}\cap A_{2}$ and is not
contained in $A_{1}\cup A_{2}$. Then, either three edges $A_{1},A_{2},B$ form
a non-interval partial clutter of type 2, or we may assume that
$A_{2}\setminus A_{1}$ is contained in $B$ by symmetry. If $A_{1},A_{2},B$
form a non-interval partial clutter of type 2, then $B$ must contain all
elements not contained in $A_{1}\cup A_{2}$. Especially, $B$ contains
$A_{3}\cap A_{4}$. And if $A_{2}\setminus A_{1}$ is contained in $B$, then
$A_{2}\cap A_{3}$ is contained in $B$. Therefore, it can be assumed that $B$
contains some intersection $A_{1}\cap A_{2}$ and not contained in $A_{1}\cup
A_{2}$ after reindexing if necessary. Thus, $B$ must contain all elements not
contained in $A_{1}\cup A_{2}$. This implies that $A_{3}\cap A_{4}$ is
contained in $B$ and therefore $B$ must contain all elements not contained in
$A_{3}\cup A_{4}$. If $m\neq 4$, this implies that $A_{1}$ is contained in $B$
which is a contradiction. So, assume that $m=4$. Since $A_{1},A_{2}$ are not
contained in $B$, there are some element $x\in A_{2}\cap A_{3}$ and $y\in
A_{1}\cap A_{4}$ not contained in $B$. This implies that $A_{2},A_{3},B$ is a
non-interval, CA partial clutter. Thus, the deletion $M-y$ is not an interval
positroid. This is a contradiction.

Therefore, $B$ must not contain an element contained in some intersection
$A_{i}\cap A_{i+1}$. If $B$ contains elements of $A_{i}$ and $A_{i+1}$, then
$A_{i},A_{i+1},B$ form a non-interval, CA clutter. Then, the deletion
$M-(A_{i+2}\cap A_{i+3})$ is not an interval positroid. Thus, we may assume
that $B$ contains an element of $A_{1}$ and some other $A_{i}$ for $i\neq
2,m$. Let $\alpha$ be the smallest index such that $i\neq 1,A_{i}\cap
B\neq\emptyset$ and $\beta$ be the largest index such that $A_{i}\cap
B\neq\emptyset$. If $m>4$, then either the non-interval clutter of type 5
$A_{1},\ldots,A_{\alpha},B$ or $A_{1},A_{m},A_{m-1},\ldots,A_{\beta},B$ does
not cover the vertex set $V$. This contradicts that $M$ is an excluded minor
of interval positroids. Finally, suppose that $m=4$. Then,
$A_{1},A_{2},A_{3},B$ form a non-interval CA clutter. Hence, $A_{4}$ must be
contained in $A_{1}\cup A_{3}$. By symmetry, $A_{2}$ is also contained in
$A_{1}\cup A_{3}$. Therefore, $A_{1}\cup A_{3}$ contains three disjoint edges
$A_{2}$, $A_{4}$, and $B$. This forces one of two edges $A_{1},A_{3}$ to be
large. But, any large edge of $O_{a_{1},a_{2},a_{3},a_{4};d}$ can not contain
an element exclusively. Therefore, $B$ is contained in either $A_{1}$ or in
$A_{3}$ which is a contradiction.

∎

######  Proposition 6.2.

Suppose that $M$ is a non-positroid, paving excluded minor of interval
positroids with five distinct edges $A,B,C,D_{1},D_{2}$. Then, the partial
clutter obtained by removing one edge $D_{2}$ is not a,b,c;d.

###### Proof.

Suppose that the partial clutter consisting of four edges $A,B,C,D_{1}$ is
a,b,c;d.

####  Case 1: $D_{2}$ contains some element $x\in D_{1}\setminus(A\cup B\cup
C)$.

Since $D_{2}$ is not contained in $D_{1}$, we may assume that
$D_{2}\cap(A\setminus D_{1})$ is nonempty due to symmetry. Consequently, $A$,
$D_{1}$, and $D_{2}$ form a triangle unless $A\cap D_{1}\subset D_{2}$.
Therefore, we have two possibilities: either $A\cap D_{1}\subset D_{2}$, or
$B\setminus D_{1}$ and $C\setminus D_{1}$ are subsets of $D_{2}$.

In the case where $A\cap D_{1}\subset D_{2}$, there exists an element $y\in
A\setminus D_{1}$ that is not contained in $D_{2}$, as $A$ is not entirely
contained in $D_{2}$. Consequently, the deletion $M-y$ results in a clutter
with four edges: $B$, $C$, $D_{1}$, and $D_{2}$. This clutter is non-interval
by Lemma 2.1.

If $B\setminus D_{1}$ and $C\setminus D_{1}$ are subsets of $D_{2}$, then
$B\cap D_{1}$ is not contained in $D_{2}$. This implies that the partial
clutter $B,D_{1},D_{2}$ forms a triangle. Consequently, $A\setminus D_{1}$ is
contained in $D_{2}$. Thus, three disjoint small edges—$A$, $B$, and $C$—are
contained in the union $D_{1}\cup D_{2}$. This implies that either $D_{1}$ or
$D_{2}$ is large. However, this leads to a contradiction, as the deletion
$M-x$ would then have four edges forming a clutter of type 4, which is
impossible.

####  Case 2: $D_{2}$ contains some element $x\in A\cap D_{1}$ and contained
in $A\cup D_{1}$.

Since $A,D_{1},D_{2}$ do not cover the entire vertex set, they cannot form a
triangle. Consequently, $A\cap D_{1}$ must be contained in $D_{2}$. Let $x$ be
an element in $A$ that is not contained in $D_{1}$ because $A$ is not included
in $D_{2}$. The deletion $M-x$ results in a set of four edges:
$B,C,D_{1},D_{2}$. Once again, this clutter is non-interval by Lemma 2.1.

####  Case 3: $D_{2}$ contains some element $x\in A\cap D_{1}$ and not
contained in $A\cup D_{1}$.

Let $y\in B\setminus D_{1}$ is contained in $D_{2}$. The partial clutter
$B,D_{1},D_{2}$ is non-interval unless $B\cap D_{1}$ is contained in $D_{2}$.
Therefore, either $B\cap D_{1}$ or $(A\cup C)\setminus D_{1}$ is contained in
$D_{2}$.

Suppose $B\cap D_{1}$ is contained in $D_{2}$. Then, there is an element $x$
of $B$ not contained in $D_{2}$. Previous cases imply that $D_{2}$ is not
contained in $B\cup D_{1}$. Hence, $D_{2}$ contains an element in $(A\cup
C)\setminus D_{1}$. Then, the partial clutter $B,D_{1},D_{2}$ is a clutter of
type 2. Therefore, $(A\cup C)\setminus D_{1}$ is contained in $D_{2}$.

Now, it remains to prove that $((A\cup C)\setminus D_{1})\subset D_{2}$
induces a contradiction. The partial clutter with four edges $A,C,D_{1},D_{2}$
is non-interval, as it has a subhypergraph that is a square. Therefore
$B\setminus D_{1}$ is also contained in $D_{2}$. Since $A,B,C$ are not
contained in $D_{2}$, $A\cap D_{2},B\cap D_{2},C\cap D_{2}$ are not entirely
contained in $D_{2}$. Again, either $D_{1}$ or $D_{2}$ is large. If $D_{1}$ is
large, at least one of the three intersections $A\cap D_{1},B\cap D_{1},C\cap
D_{1}$ contains more than one element because $d\geq 3$. Suppose that
$1<|A\cap D_{1}|$. The deletion $M-y$ by an element in $y\in(A\cap
D_{1})\setminus D_{2}$ results in a paving matroid with four edges
$B,C,D_{1}\setminus\\{y\\},D_{2}$ which is not an interval positroid. By
symmetry, the same contradiction is induced if $D_{2}$ is large.

####  Case 4: $D_{1}\cap D_{2}=\emptyset$.

Combining three previous cases, the only remaining possibility is when $D_{1}$
and $D_{2}$ are disjoint. The edge $D_{2}$ must have nonempty intersection
with at least two edges among $A,B,C$, as $D_{2}$ is not contained in another
edge. Let us assume that $A\cap D_{2}$ and $B\cap D_{2}$ are nonempty. Then,
the partial clutter obtained by removing $C$ is a non-interval CA clutter.
Therefore, $C\setminus D_{1}$ is also contained in $D_{2}$. By the same
argument, $A\setminus D_{1}$ and $B\setminus D_{1}$ are also contained in
$D_{2}$. Therefore, $V=A\cup B\cup C=D_{1}\cup D_{2}$. This implies that
either $D_{1}$ or $D_{2}$ is large. This induces a contradiction by the same
argument as in case 3.

∎

######  Proposition 6.3.

Suppose that $M$ is a non-positroid, paving excluded minor of interval
positroids with five distinct edges $A,B,C_{1},C_{2},D$. Then, the partial
clutter obtained by removing one edge $D$ is not $Y^{\prime}_{a,b;d}$.

###### Proof.

Suppose that the partial clutter with three edges $A,B,C_{1}$ is $Y_{a,b;d}$
and $C_{2}=(A\setminus C_{1})\sqcup(C_{1}\setminus(A\cup B))\sqcup(B\setminus
C_{1})$. Then, the partial clutter with four edges $A,B,C_{1},D$ is also a
paving, non-positroid excluded minor of interval positroids. By Theorem 5.1,
$D$ is either $(A\setminus C_{1})\sqcup(C_{1}\setminus(A\cup
B))\sqcup(B\setminus C_{1})$ or $A,B,D$ form a clutter
$Y_{a^{\prime},b^{\prime};d}$. Since $D$ is not equal to $C_{2}$, the latter
case must hold. Now, the partial clutter with four edges $A,B,C_{2},D$ is also
a paving, non-positroid excluded minor of interval positroids. Since $C_{2}$
does not contain the common point, $C_{2}$ must be $(A\setminus
D)\sqcup(D\setminus(A\cup B))\sqcup(B\setminus D)$ which implies that
$D=C_{1}$. This is a contradiction.

∎

Next theorem characterizes all non-positroid, paving excluded minor of
interval positroids obtained by adding edges to $Y_{a,b;d}$.

######  Theorem 6.2.

Suppose that $M$ is a paving excluded minor of interval positroids of rank $d$
with edges $A,B,C_{1},C_{2},\ldots,C_{m}$ for some $m\geq 3$. The partial
clutter obtained by removing edges $C_{2},\ldots,C_{m}$ is $Y_{a_{1},b_{1};d}$
with the common point $v$ if and only if following conditions hold:

  1. (1)

The partial clutter $A,B,C_{i}$ is the clutter $Y_{a_{i},b_{i};d}$ for each
$i=1,\ldots,m$.

  2. (2)

The clutter
$(V\setminus\\{v\\},\\{A\setminus\\{v\\},B\setminus\\{v\\},C_{1}\setminus\\{v\\},\ldots,C_{m}\setminus\\{v\\}\\})$
is an interval $(d-1)$-paving clutter.

###### Proof.

The proof of sufficiency is omitted as it can be checked routinely.

The partial clutter with four edges $A,B,C_{1},C_{i}$ must be
$Y_{a_{1},a_{i},b_{1},b_{i};d}$ for $i=2,\ldots,m$ by Theorem 5.1 and
Proposition 6.3. Hence, the first condition holds. The second condition
follows from the fact that the contraction $M/v$ is an interval positroid of
rank $d-1$.

∎

######  Notation 6.1.

The excluded minor above will be denoted by
$Y_{a_{1},\ldots,a_{m},b_{1},\ldots,b_{m};d}$ where $a_{i}=|A\cap
C_{i}|-1,b_{i}=|B\cap C_{i}|-1$.

Now, we classify paving, non-positroid, $O_{a_{1},a_{2},a_{3};d}$-base
excluded minors of interval positroids. Recall the notation

$\displaystyle S$ $\displaystyle=A\setminus(B\cup C),S^{\prime}=B\cap C,$
$\displaystyle T$ $\displaystyle=B\setminus(C\cup A),T^{\prime}=C\cap A,$
$\displaystyle U$ $\displaystyle=C\setminus(A\cup B),U^{\prime}=A\cap B,$
$\displaystyle a$ $\displaystyle=|S^{\prime}|,b=|T^{\prime}|,c=|U^{\prime}|.$

######  Theorem 6.3.

Suppose that $M$ is a non-positroid, paving excluded minor of interval
positroids with five distinct edges $A,B,C,D_{1},D_{2}$. If the partial
clutter obtained by removing one edge $D_{2}$ is $\Delta_{a,b,c}^{1}$, then
$D_{2}$ must be $S^{\prime}\cup T^{\prime}\cup U^{\prime}$. This paving
excluded minor of interval positroids will be denoted by $\Delta_{a,b,c}^{3}$.

###### Proof.

If the partial clutter $A,B,C,D_{2}$ is not a CA clutter, then $D_{2}$ must be
either $S^{\prime}\cup T^{\prime}\cup U^{\prime}$ or $S\cup T\cup U$ by
Theorem 5.2. Since $D_{2}$ is not $D_{1}$, it must be $S^{\prime}\cup
T^{\prime}\cup U^{\prime}$.

Now, assume that the partial clutter with four edges $A,B,C,D_{2}$ is CA. By
symmetry and Lemma 6.1, we may assume the inclusion relations
$S^{\prime}\subset D_{2}\subset B\cup C$. If $D_{2}$ is the complement of the
edge $A$, the matroid is $\Delta_{a,b,c}^{3}$. f $D_{2}$ is not the complement
of the edge $A$, we can assume that the edge $D_{2}$ contains some elements
$x\in T$ and $y\in T^{\prime}$. Then $D_{2}$ contains two consecutive blocks
$S^{\prime}$ and $U$. Then, the partial clutter with three edges
$B,D_{1},D_{2}$ is a clutter of type 2. Hence, $D_{2}$ must contain
$T^{\prime}=A\cap C$. This implies that $C\subset D_{2}$ which is a
contradiction.

∎

$a$$A$$b$$B$$c$$C$abc Figure 4. $\Delta_{a,b,c;d}^{3}$

Similarly, $\Delta^{3}_{a,b,c}$ is the only possible case if some relaxation
is $\Delta_{a,b,c;k}^{2}$.

######  Theorem 6.4.

Suppose that $M$ is a non-positroid, paving excluded minor of interval
positroids with five distinct edges $A,B,C,D_{1},D_{2}$. If the partial
clutter obtained by removing one edge $D_{2}$ is $\Delta_{a,b,c;k}^{2}$, then
$k=0$ and $D_{2}$ must be $S\cup T\cup U$. Therefore, $M$ is
$\Delta^{3}_{a,b,c}$

###### Proof.

If the partial clutter $A,B,C,D_{2}$ is not a CA clutter, then $D_{2}$ must be
either $S^{\prime}\cup T^{\prime}\cup U^{\prime}$ or $S\cup T\cup U$ (assuming
$k=0$) by Theorem 5.2. Since $D_{2}$ is not equal to $D_{1}$, $D_{2}$ must be
$S\cup T\cup U$ and $k=0$.

Now, assume that the partial clutter with four edges $A,B,C,D_{2}$ is CA.
Assume that $S^{\prime}\subset D_{2}\subset B\cup C$. Then $B,C,D_{1},D_{2}$
is a non-interval clutter of type 3. Since $S$ is nonempty, the deletion $M-S$
is a proper minor of $M$ that is not an interval positroid.

∎

Finally, we end this section by showing that
$Y_{a_{1},\ldots,a_{m},b_{1},\ldots,b_{m};d},m\geq 3$ are only possible
paving, non-positroid excluded minors of interval positroids with more than
five edges. By Proposition 6.1, no such excluded minor is obtained by adding
an edge to $O_{a_{1},\ldots,a_{m};d}$. Moreover, Corollary 6.1 implies that
some relaxation of such excluded minor remains non-positroid. Therefore, it is
enough to prove that no new excluded minor is obtained by adding an edge to
$\Delta_{a,b,c}^{3}$, as $\Delta_{a,b,c}^{3}$ and
$Y_{a_{1},a_{2},a_{3},b_{1},b_{2},b_{3};d}$ are only non-positroid paving
excluded minor of interval positroids with five edges.

######  Proposition 6.4.

Let $M$ be a non-positroid, paving excluded minors of interval positroids with
six distinct edges $A,B,C,D_{1},D_{2},D_{3}$. Then, the partial clutter
$A,B,C,D_{1},D_{2}$ is not $\Delta_{a,b,c}^{3}$.

###### Proof.

Suppose that the partial clutter $A,B,C,D_{1},D_{2}$ is $\Delta_{a,b,c}^{3}$
with $D_{1}=S\cup T\cup U$ and $D_{2}=S^{\prime}\cup T^{\prime}\cup
U^{\prime}$. By Theorem 6.3, the partial clutter $A,B,C,D_{1},D_{3}$, which is
also a paving, non-positroid excluded minor of interval positroids, must be
$\Delta_{a,b,c}^{3}$. Thus $D_{3}$ must be $S^{\prime}\cup T^{\prime}\cup
U^{\prime}$ which is a contradiction since $D_{2}$ is not equal to $D_{3}$.

∎

##  7\. Summary and further remarks

To summarize, we list all paving, non-positroid excluded minors of interval
positroids in Table 1.

Number of edges or dependent hyperplanes |  non-positroid paving excluded minors of interval positroids
---|---
3 |  $Y_{a,b;d}$
4 |  $Y^{\prime}_{a,b;d},Y_{a_{1},a_{2},b_{1},b_{2};d},\Delta_{a,b,c}^{1},\Delta_{a,b,c;k}^{2}$
5 |  $Y_{a_{1},a_{2},a_{3},b_{1},b_{2},b_{3};d},\Delta_{a,b,c}^{3}$
6 |  $Y_{a_{1},\ldots,a_{m},b_{1},\ldots,b_{m};d}$ for $m\geq 4$
Table 1. Non-positroid paving excluded minors of interval positroids

A paving, non-positroid excluded minors of interval positroids is also an
excluded minor of positroids. Moreover, while the dual of these excluded
minors is not necessarily an excluded minor of interval positroids, it remains
an excluded minor of positroids. The excluded minor $\Delta_{a,b,c}^{1}$,
which is self-dual, is a special case of the example found by Bonin [5,
Example 4,5]. The dual of the excluded minor $Y_{a,b;d}$, when the edge $C$ is
small, is a special case of the three-circuit case of the example [5, Example
9]. The excluded minors of positroids
$Y_{a_{1},\ldots,a_{m},b_{1},\ldots,b_{m};d}$ (for $m\geq 2$ or with some
large $C_{i}$), $Y^{\prime}_{a,b;d},\Delta_{a,b,c;k}^{2},\Delta_{a,b,c}^{3}$
and their duals are new excluded minors of positroids that have not appeared
in the literature.

## References

  * Postnikov [2006] Alexander Postnikov.  Total positivity, Grassmannians, and networks.  http://www-math.mit.edu/~apost/papers/tpgrass.pdf, 2006.
  * Blum [2001] Stefan Blum.  Base-sortable matroids and Koszulness of semigroup rings.  _European J. Combin._ , 22(7):937–951, 2001.
  * Ardila et al. [2016] Federico Ardila, Felipe Rincón, and Lauren Williams.  Positroids and non-crossing partitions.  _Trans. Amer. Math. Soc._ , 368(1):337–363, 2016\.
  * Oh [2009] Suho Oh.  Combinatorics of positroids.  In _21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)_ , Discrete Math. Theor. Comput. Sci. Proc., AK, pages 721–732. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2009.
  * Bonin [2023] Joseph E. Bonin.  A characterization of positroids, with applications to amalgams and excluded minors, 2023.  arXiv:2306.06694 [math.CO].
  * Oh [2011] Suho Oh.  Positroids and Schubert matroids.  _J. Combin. Theory Ser. A_ , 118(8):2426–2435, 2011.
  * Bonin [2010] Joseph E. Bonin.  Lattice path matroids: the excluded minors.  _J. Combin. Theory Ser. B_ , 100(6):585–599, 2010\.
  * Knutson and Lederer [2014] Allen Knutson and Mathias Lederer.  Interval positroid varieties and a deformation of the ring of symmetric functions.  In _26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)_ , volume AT of _Discrete Math. Theor. Comput. Sci. Proc._ , pages 923–933. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2014.
  * Oxley [2011] James Oxley.  _Matroid theory_ , volume 21 of _Oxford Graduate Texts in Mathematics_.  Oxford University Press, Oxford, second edition, 2011.
  * Ding [2002] Guoli Ding.  On interval clutters.  _Discrete Math._ , 254(1-3):89–102, 2002.
  * Joswig and Schröter [2017] Michael Joswig and Benjamin Schröter.  Matroids from hypersimplex splits.  _J. Combin. Theory Ser. A_ , 151:254–284, 2017.
  * Hartmanis [1959] Juris Hartmanis.  Lattice theory of generalized partitions.  _Canadian J. Math._ , 11:97–106, 1959.
  * Bérczi et al. [2023] Kristóf Bérczi, Tamás Király, Tamás Schwarcz, Yutaro Yamaguchi, and Yu Yokoi.  Hypergraph characterization of split matroids.  _J. Combin. Theory Ser. A_ , 194:Paper No. 105697, 15, 2023\.
  * Ferroni et al. [2022] Luis Ferroni, George D Nasr, and Lorenzo Vecchi.  Stressed Hyperplanes and Kazhdan–Lusztig Gamma-Positivity for Matroids.  _International Mathematics Research Notices_ , page rnac270, 10 2022\.