# Positroids are 3-colorable

Lamar chidiac  Winfried Hochstättler

(November 2022)

###### Abstract

We show that every positroid of rank $r\geq 3$ has a positive coline. Using
the definition of the chromatic number of oriented matroid introduced by J.
Nešetřil, R. Nickel, and W. Hochstättler, this shows that every orientation of
a positroid is 3-colorable.

Fakultät für Mathematik und Informatik,
FernUniversität in Hagen, Germany,
<EMAIL_ADDRESS>

##  1 Introduction

A classical algebraic way to analyze the chromatic number of a graph is to
study Nowhere-Zero(NZ)-tensions, which we will call NZ-coflows, as they form a
concept dual to NZ-flows. Flows and coflows immediately generalize to regular
oriented matroids and Hochstättler [14] presented a generalization of
Hadwiger’s famous conjecture that any graph which is not $k$-colorable must
have a $K_{k+1}$-minor to regular oriented matroids. Goddyn and Hochstättler
[8] proved that this conjecture is equivalent to Tutte’s 4-Flow conjecture for
$k=4$, Tutte’s 5-flow conjecture for $k=5$ and Hadwiger’s conjecture for
$k\geq 6$.

A matroid is regular if and only if it does not have $U_{2,4}$, the four point
line, as a minor. A first idea to generalize the theory of NZ-coflows to
general oriented matroids would be, to require that summing the coflow-values
along any cycle, taking the signs of the elements into account, evaluates to
zero. Alas, one has to cope with the fact that using this definition no
orientation of $U_{2,4}$ admits a non-trivial coflow, in particular, there is
no NZ-coflow. Therefore, one needs to take another approach to define the NZ-
coflows for general oriented matroids. The coflow space may dually be defined
as the linear hull of signed characteristic vectors of cocircuits. Using this
and ideas of Hochstättler and Nešetřil [11], Hochstättler and Nickel [12, 13]
initiated a chromatic theory of oriented matroids. Lacking the total
unimodularity of the matrix defining the cocircuit space, they considered the
integer lattice (chain group) generated by the signed characteristic vectors
of the cocircuits instead. It seems possible that the generalization of
Hadwiger’s Conjecture to regular oriented matroids might be true even for
general orientable matroids.

While the case $k=2$ still is trivial for general oriented matroids, already
the case $k=3$, which was proven by Hadwiger in the graphic (and regular)
case, is open in general. The graphic case is easily proved observing the fact
that a simple graph without $K_{4}$-minor always has a vertex of degree at
most $2$. Therefore Goddyn, Hochstättler and Neudauer [9], introduced the
class of generalized series parallel ($GSP$) oriented matroids, which is an
$M(K_{4})$-free class, requiring that the coflow-lattice of every minor
contains a vector with at most two non-zero entries which must be $+1$ or
$-1$. This class is easily seen to be 3-colorable in the sense of Hochstättler
and Nickel, if the matroid is loopless. In general, the class of
$M(K_{4})$-free matroids is not well understood [7]. If every such orientable
matroid could be proven to be $GSP$, then Hadwiger’s conjecture would hold for
oriented matroids in the case $k=3$. A large class of orientable matroids
without $M(K_{4})$-minor is formed by the gammoids. Unfortunately, they are
only slightly better understood.

One possibility to prove membership in the class $GSP$ is to find two
compatible cocircuits in the oriented matroid with symmetric difference of
cardinality at most two. The existence of such a pair is guaranteed for any
orientation if there exists a coline with more simple than multiple copoints.
Here, a copoint $H$ (a hyperplane in the underlying matroid) is simple with
respect to the coline $L$ if $|H\setminus L|=1$. Call such a coline a positive
coline. Goddyn et al. showed in [9] that every simple bicircular matroid of
rank at least $2$ has a positive coline. Bicircular matroids are transversal
matroids, and the smallest class under minors that contains transversal
matroids is the class of gammoids. Therefore they conjectured in the same work
that the same holds for every simple gammoid of rank at least $2$. Albrecht
and Hochstättler [2, 1] later proved this to be true for rank $3$. However,
Guzman-Pro and Hochstättler recently proved in [10] that not every simple
gammoid of rank at least $2$ has a positive coline, disproving by that the
conjecture of Goddyn et al. [9].

Every loopless oriented matroid of rank $3$ not containing $M(K_{4})$ is
3-colorable [13]. In addition, until now bicircular matroids of rank $\geq 2$
[9] and simple lattice path matroids of rank $\geq 2$[3] were shown to be
$3$-colorable by proving the existence of a positive coline in each one of
them. In this paper, we add in the same way, simple positroids of rank $\geq
3$ to this list.

We assume basic familiarity with matroid theory and oriented matroids. The
standard references are [15, 5].

##  2 Preliminaries

In this work we consider matroids to be pairs $M=(E,\mathcal{B})$ where
$E=[n]=\\{1,2,...n\\}$ and present them as their set of bases. For simplicity
sake, we omit curly brackets and commas when writing subsets. So rather than
$\mathcal{B}=\\{\\{1,2\\},\\{1,3\\}\\}$, we write $\mathcal{B}=\\{12,13\\}$. A
_path_ in $D=(V,A)$ is a non-empty and non-repeating sequence $p_{1}p_{2}\dots
p_{n}$ of vertices $p_{i}\in V$ such that for each $1\leq i<n$,
$(p_{i},p_{i+1})\in A$. By convention, we shall denote $p_{n}$ by $p_{-1}$.
Furthermore, the set of vertices traversed by a path $p$ shall be denoted by
$p=\\{p_{1},p_{2},\dots,p_{n}\\}$.

As mentioned in the introduction, gammoids are the main motivation behind this
work, however they are not very well understood. In this section we define
gammoids and positroids, and show that positroids are actually gammoids. For
that we are going to need the following definition.

######  Definition 2.1.

Let $D=(V,A)$ be a digraph, and $X,Y\subseteq V$. A _routing_ from $X$ to $Y$
in $D$ is a family of paths $R$, such that:

  * •

for each $x$ in $X$ there is some $p\in R$ with $p_{1}=x$

  * •

for all $p\in R$ the end vertex $p_{-1}\in Y$, and

  * •

for all $p,q\in R$, either $p=q$ or $p\cap q=\emptyset$

A routing $R$ is called _linking_ from $X$ to $Y$, if it is a routing onto
$Y$, i.e. whenever $Y=\\{p_{-1}\>|\>p\in R\\}$. We write $X\rightrightarrows
Y$ whenever there is a routing from $X$ to $Y$. Furthermore, we say that $v$
is linked to $w$ in a directed graph, whenever there exists a directed path
from $v$ to $w$ or from $w$ to $v$.

######  Definition 2.2 (Gammoids).

Let $D=(V,A)$ be a digraph, $E\subseteq V$, and $T\subseteq V$. The _gammoid_
represented by $(D,T,E)$ is defined to be the matroid
$\Gamma(D,T,E)=(E,\mathcal{I})$ where

$\mathcal{I}=\\{X\subseteq E\;|\;\text{there is a routing}\;X\rightrightarrows
T\;\text{in D}\\}.$

Positroids were originally defined in [16] as the column sets coming from
nonzero maximal minors of a matrix such that all maximal minors are
nonnegative. Thus positroids are matroids representable over the reals and
therefore orientable. However in this paper, we will use an equivalent
definition using  L -graphs.

######  Definition 2.3 (  L -diagram).

A  L -_diagram_ is a lattice path with a finite collection of boxes lying
above it, arranged in left-justified rows, with the row lengths in non-
increasing order, where some of the boxes are filled with dots in such a way
that the  L -_property_ is satisfied: There is no empty box which has a dot
above it in the same column and a dot to its left in the same row.

######  Definition 2.4 (  L -graph).

Starting from a  L -diagram we apply the following steps:

  * •

place nodes in the middle of each edge of this lattice path and label them
from $1$ to $n$ starting at the Northeast corner of the path and ending at the
Southwest corner.

  * •

Add edges directed to the right between any two consecutive nodes that lie in
the same row.

  * •

Add edges directed upwards between any two consecutive nodes that lie in the
same column.

A  L -_graph_ $G=(V,A)$ is the graph obtained from a  L -diagram following the
above steps, where $V$ is the set vertices formed by the internal vertices
(nodes inside boxes) and the external vertices (nodes placed on the lattice
path), and $A$ is the set of directed edges added to the  L -diagram
previously. Edges between external vertices are not in $A$. The  L -property
implies that $G$ is always planar.

The following provides an example of a  L -diagram and a  L -graph.

••••• Figure 1: A

L

-diagram $D$

1234567•••••••••••• Figure 2: The corresponding

L

-graph obtained from $D$

According to [16], the following definition of positroids is equivalent to all
of the definitions of positroids found there.

######  Definition 2.5 (Positroids).

Let $B$ be the set of sinks of a  L -graph, that is the set of external
vertices labeling vertical edges of the lattice path and let $L$ be the set of
all external vertices (sources and sinks of the  L -graph). Let
$\mathcal{P}\subseteq$ $L\choose r$ consist of $B$ together with all sets
$I\in$ $L\choose r$ such that there exists a linking from $I\backslash B$ to
$B\backslash I$ in the  L -graph. This collection of subsets is a _positroid_.
All positroids may be realized uniquely in this way.

For example, the positroid built from the previous  L -graph is

$\mathcal{P}=\\{235,236,245,246,256,257,267,356,357,367,456,457,467\\}.$

It is easy to see that positroids are actually gammoids. Since there is a
linking from $I\backslash B$ to $B\backslash I$, this means there is also a
linking between $I$ and $B$ since $I$ and $B$ are of same size, and thus a
routing between $X\in I$ and $B$. Therefore a positroid is a gammoid with
representation $(D,B,E)$ with $\Gamma(D,B,E)=(E,\mathcal{I})$ where

$\mathcal{I}=\\{X\subseteq E\;|\;\text{there is a routing}\;X\rightrightarrows
B\;\text{in}\;D\\}$

######  Remark 2.1 (Rank of a subset of a positroid).

In order to understand the proof of our main theorem, it is crucial to
understand how we can compute the rank of an arbitrary subset of a positroid
using the  L -graph. As you already know, the rank of a set $I$ is the size of
the biggest independent subset in $I$ and since independent sets are the
subsets of the bases, we will have to find them using the same method we use
to find a basis in the positroid, i.e. searching for vertex-disjoint walks and
counting them. An arbitrary subset $I$ of a positroid, that contains $x$
vertical edges of the lattice path ($x$ sinks), is of rank at least $x$. The
rank of $I$ is $x+t$, such that $t$ is the number of all vertex-disjoint walks
from $I\backslash B$ to $B\backslash I$.

In this work we show that simple positroids are 3-colorable, by proving the
existence of a positive coline. For that, we recall the following definitions.

######  Definition 2.6 (Copoints and Colines).

Let $M$ be a matroid. A _copoint_ of $M$ is a flat of codimension $1$, that is
a hyperplane. A _coline_ is a flat of codimension 2. If $L$ is a coline of
$M$, $H$ a copoint of $M$ and $L\subseteq H$, then we say that $H$ is a
_copoint on_ $L$. The copoint is _simple_ (with respect to $L$) if
$|H\backslash L|=1$, otherwise it is _multiple_. A coline is _positive_ if
there are more simple than multiple copoints on $L$.

##  3 Loops, coloops and parallel elements in a  L -graphs

In the  L -graph, a loop of the positroid is represented by a source (an
external vertex labelling a horizontal edge of the lattice path) that is not
linked to anything. A coloop is represented by a sink (an external vertex
labelling a vertical edge of the lattice path) that is not linked to anything.
Figure 4 below presents the  L -graph of a positroid containing loops and a
coloop.

Since the set of all sinks in the  L -graph is a base of the positroid, a pair
of elements can be parallel if both elements are sources or if one is a source
and the other is a sink. Let $h_{i}$ and $h_{j}$ be two sources in the  L
-graph of a positroid $\mathcal{P}$ such that $h_{i}$ is to the right of
$h_{j}$, and let $w$ be the first internal vertex above $h_{i}$.

1234567••••••••••• Figure 3: The

L

-graph of a positroid in which the sources 1 and 4 are loops, and the sink 5 is a coloop.

1234567••••••••••• Figure 4: The

L

-graph of a positroid in which {3,4} and {6,7} are two parallel pairs.

• $h_{i}$ and $h_{j}$ are parallel if and only if any directed path starting
from $h_{j}$ must go through $w$.

• A source $h$ and a sink $v$ are parallel if and only if $h$ is not linked to
any sink other than $v$.

Figure 4 above presents a  L -graph of a positroid with parallel elements. In
the rest of this work, we consider only simple positroids, i.e. positroids
with no loops and parallel elements. Therefore we assume that each source in
the  L -graph is linked to at least two sinks and no two sources are parallel.

##  4 Connectivity of positroids

In order to characterise connectivity of positroids in  L -graphs, we need the
following definitions.

######  Definition 4.1.

Let $\mathcal{P}$ be a positroid and $D$ its  L -diagram. A _level_ in $D$ is
a collection of consecutive vertical edges of the lattice path with the
consecutive horizontal edges that follows them.

For example, in Figure 4, the edges of the lattice path labelled by $2,3$ and
$4$ form a level and the edges of the lattice path labelled by $5,6$ and $7$
form another level.

######  Definition 4.2.

Let $\mathcal{P}$ be a positroid and $D$ its  L -diagram. An _isolated block_
in $D$ is a level or a collection of levels in which the sources of this block
are only connected to the sinks in it. We can write this formally in the
following way.

$B\text{ is an isolated block in }D\iff\begin{cases}\forall v\text{ a sink}\in
B,\forall h\text{ a source}\notin B,h\text{ is not linked to }v,\text{ and}\\\
\forall h\text{ a source}\in B,\forall v\text{ a sink}\notin B,h\text{ is not
linked to }v.\end{cases}$

The following figures are examples of  L -diagrams with isolated blocks.

123458679•••••••••••••••••

Figure 5: A

L

-diagram with an isolated block formed by one level: edges labelled by 4,5,6 and 7. The other isolated block consists of edges labelled by 1,2,3,8 and 9

123456789••••••••••••••••

Figure 6: A

L

-diagram with two isolated blocks. Block 1: edges labelled by 3,4,5,6,7. Block 2: edges labelled by 1,2,8,9

######  Remark 4.1.

Note that a coloop, just like a loop, is by itself an isolated block.

We next prove that isolated blocks are strongly related to the connectivity of
a positroid.

######  Lemma 4.1.

A positroid $\mathcal{P}$ is connected if and only if there exists no isolated
blocks in its  L -diagram. Equivalently, a positroid $\mathcal{P}$ is not
connected if and only if there exist isolated blocks in its  L -diagram $D$.

###### Proof.

In the following we prove that a positroid is not connected if and only if
there are isolated blocks. We start by the necessary condition. Let
$B_{1},\dots,B_{k}$ be the isolated blocks in $D$. These blocks have disjoint
set of elements and therefore form a partition of the elements of $P$ which
can be written as the direct sum of these blocks, $P=B_{1}\oplus\dots\oplus
B_{k}$. Thus, $P$ is not connected.

For the sufficient condition, we now assume that $P$ is not connected. This
means that $P=P_{1}\oplus\dots\oplus P_{k}$. We now show that the $P_{i}$ s
are the isolated blocks of $D$. Let $B(P_{i})$ (resp. $H(P_{i})$) be the set
of sinks (resp. sources) of the block $P_{i}$. It is well known ([15]) that a
matroid is connected if and only if any pair of elements belong to a common
circuit. This implies that a positroid is not connected if and only if there
exists a pair of elements that do not belong to a common circuit. It is also
known that a circuit in an unconnected matroid is a circuit in only one of its
connected components [15]. Therefore $\forall$ $e\in P_{i}$ and $\forall$
$f\in P_{j}$ with $i\neq j$, $e$ and $f$ do not belong to a common circuit. We
now consider two cases. If $e\in B(P_{i})$, then $\forall f\in H(P_{j})$
($i\neq j$), $f$ is not linked to $e$ because otherwise $e,f$ and all sinks
linked to $f$ form a circuit, which contradicts the fact that $e$ and $f$ do
not belong to a common circuit. Similarly, if $e\in H(P_{i})$, then $\forall
f\in B(P_{j})$ ($i\neq j$), $e$ is not linked to $f$ because otherwise $e,f$
and all sinks linked to $e$ form a circuit. Thus $P_{i}$ is an isolated block
in $D$, $\forall$ $1\leq i\leq k$.

∎

######  Remark 4.2.

In [6], J. Bonin proved that a lattice path matroid $L$ of rank $rk(L)$ is
connected if and only if it has a spanning circuit, that is a circuit of rank
$rk(L)$. Unlike lattice path matroids, a positroid can be connected without
having a spanning circuit. In the following, we present a counterexample
(Figure 7) showing a connected positroid and then prove the absence of a
spanning circuit in it.

1234567••••••••••••• Figure 7: A connected positroid with no spanning circuit.

The positroid in Figure 7 is connected since there are no isolated blocks in
the  L -diagram. Suppose this positroid has a spanning circuit $C$. It is easy
to notice that $C$ must contain simultaneously $6$ and $7$, because if only
one of them was in $C$, then its removal will prevent us from reaching full
rank and therefore the rank of $C$ will decrease after its removal. Similarly,
both $4$ and $5$ must be in $C$. Until now, $C$ contains the set
$\\{4,5,6,7\\}$. However, this set is not independent, it is of rank $3$ and
has $4$ elements. Therefore this set cannot be properly contained in any
circuit, which contradicts our assumption that $C$ is a spanning circuit.

##  5 Main theorem and proof

Before we get into our main theorem and its proof, let us mention the
following propositions, which explain why we assume the connectivity of
positroids in the proof.

######  Proposition 5.1 ([4] Proposition 3.5).

Positroids are closed under taking minors and duals.

######  Proposition 5.2.

If $\mathcal{M}$ is a class of matroids, closed under taking connected
components, such that all its connected members of rank at least $2$ have a
positive coline, then every element of $\mathcal{M}$ has a positive coline.

###### Proof.

Let $M$ be a matroid of rank $r\geq 2$ in $\mathcal{M}$ such that $M$ is not
connected. If $M$ consists solely of coloops all copoints are simple. Thus we
may assume that $M$ can be written as the direct sum $M=M_{1}\oplus M_{2}$ of
two matroids $M_{1}$ of rank $r_{1}$ and $M_{2}$ of rank $r_{2}$ where $M_{1}$
is connected $r_{1}\geq 2$. Thus, $M_{1}$ has a positive coline $L$. It is
easy to see that $L\cup M_{2}$ is a positive coline of $M$, because $L\cup
M_{2}$ is a flat of rank $r-2$ and it is contained in the same number of
simple and multiple copoints of $M_{1}$. Namely, if $C_{1}$ resp. $C_{2}$ is a
simple resp. multiple copoint on $L$, then $C_{1}\cup M_{2}$ resp. $C_{2}\cup
M_{2}$ is simple resp. multiple copoint on $L\cup M_{2}$. ∎

Now, we present and prove our main theorem.

######  Theorem 5.1.

Every simple positroid of rank $r\geq 3$ has a positive coline.

###### Proof.

Due to proposition 5.2, we assume connectivity of the positroids, i.e. there
exists no isolated blocks (in particular, no coloops or loops). Moreover,
since we only consider simple positroids, i.e. positroids with no loops and
parallel elements, each source should be linked to at least two sinks,
otherwise the source and the sink linked to it form a parallel pair.
Therefore, the first two edges of the lattice path in the  L -diagram of the
positroid have to be vertical. During our search for a positive coline we will
only be interested in pairs of consecutive sinks followed by one or more
sources. The closure of the set of all sinks except for these two consecutive
sinks is almost always the positive coline we are looking for. We will shortly
prove that and give the positive coline in the other case. Notice here that we
know at least one such pair exists, namely the first two sinks. Let
$V=\\{v_{1},...,v_{r}\\}$ be the set of sinks and $H=\\{h_{1},...,h_{n-r}\\}$
be the set of sources, and let $v_{i}$ and $v_{i+1}$ be the last two
consecutive sinks of the positroid.

Let us first look at the case where $v_{i}$ and $v_{i+1}$ are $v_{r-1}$ and
$v_{r}$, that is, when $v_{i}$ and $v_{i+1}$ are the last two sinks of the
positroid.

$v_{r-1}$$v_{r}$$h_{i}$$h_{j}$$h_{j+1}$$h_{n-r}$••••••••••••

Figure 8:

$v_{r-1}$$v_{r}$$h_{i}$$h_{j}$$h_{j+1}$$h_{n-r}$••••••••••••

Figure 9:

In this case, we show that $L=cl(v_{1},v_{2},...,v_{r-2})$, the closure of the
first $r-2$ sinks, is a positive coline. Note that $v_{r-1}$ and $v_{r}$ must
be followed by one or several sources $h_{i},\dots,h_{n-r}$, since otherwise
they are coloops. As we can see we have different possibilities for the way
the last sources can be linked. However, there must be a linking from $h_{i}$
to $v_{r}$, otherwise $v_{r}$ is a coloop, as well as a linking from $h_{i}$
to $v_{r-1}$ since $h_{i}$ should be linked to another sink (otherwise $h_{i}$
and $v_{r}$ are parallel elements), and if this sink wasn’t $v_{r-1}$, then
$v_{r-1}$ would be a coloop. To the left of $h_{i}$ we can have other sources
similar to $h_{i}$, meaning sources linked to both $v_{r}$ and $v_{r-1}$ in
the same way $h_{i}$ is. Let $h_{j}$ ($j\geq i$) be the last such source. It
is easy to notice that if a source after $h_{j}$ is not linked to neither
$v_{r}$ nor $v_{r-1}$, but only to higher sinks, then it is included in $L$,
and therefore we may ignore them and assume such sources do not exist. Thus,
after $h_{j}$ we have 3 possibilities. We can have sources linked to $v_{r}$
(Figure 8), or sources only linked to $v_{r-1}$ and not to $v_{r}$ (Figure 9),
or sources linked to both $v_{r}$ and $v_{r-1}$ in the same way $h_{i}$ is. In
other words, $h_{j}$ is the last source. The important thing to notice here,
is that we can’t have some sources linked to $v_{r}$ and the others only
linked to $v_{r-1}$ as in Figure 10 since now $h_{j}$ and $h_{j+1}$ are
parallel elements.

$v_{r-1}$$v_{r}$$h_{i}$$h_{j}$$h_{j+1}$$h_{n-r}$••••••••••••

Figure 10:

We now discuss the 3 possibilities. $L$ is a flat of rank $r-2$, so it is a
coline that contains all sinks except for $v_{r-1}$ and $v_{r}$ with all
sources that are not connected to $v_{r-1}$ and $v_{r}$. Let us now look at
the copoints on $L$.

Possibility 1: All sources are linked to $v_{r}$.
In this case (Figure 8), $L\cup v_{r-1}$ is of rank $r-1$ and a flat because
adding anything to it will increase its rank since all sources are linked to
$v_{r}$. Therefore $L\cup v_{r-1}$ is a simple copoint. Similarly, $L\cup
v_{r}$ is a simple copoint. Additionally, if $j\neq i$, then $L\cup h_{i}$ is
a simple copoint as well since all other sources can get to $v_{r-1}$ with no
intersection with the path from $h_{i}$ to $v_{r}$. The only possible multiple
copoint is $L\cup h_{j}\cup\dots\cup h_{n-r}$ since
$h_{j},h_{j+1},\dots,h_{n-r}$ cannot be linked to $v_{r-1}$ and $v_{r}$
without intersection. If $j=i$, which means that $h_{i}$ is the last source
linked to both $v_{r}$ and $v_{r-1}$ as shown above, then $L\cup h_{i}$ would
not be simple and we would only have two simple copoints. Note that here, the
more we have sources similar to $h_{i}$, in other words the bigger $j$ is, the
more simple copoints we get. So $L$ is a positive coline since it has at least
two simple copoints and at most one multiple copoint.

Possibility 2: There are sources which are only linked to $v_{r-1}$.
In this case (Figure 9), $L\cup v_{r}$ is of rank $r-1$ and a flat because
adding anything to it will increase its rank since all sources can be linked
to $v_{r-1}$. Therefore $L\cup v_{r}$ is a simple copoint. Similarly $L\cup
h_{i}$ and $L\cup h_{j}$ are simple copoints. The only possible multiple
copoint is $L\cup v_{r-1}\cup h_{j+1}\cup\dots\cup h_{n-r}$, where $h_{j+1}$
is the first source which is not linked to $v_{r}$. So $L$ is a positive
coline in this case as well.

Possibility 3: $h_{j}$ is the last source.
If $h_{j}$ is the last source, this means that all sources after $v_{r}$ are
linked to both $v_{r}$ and $v_{r-1}$ in the same way $h_{i}$ is. After similar
calculations to the previous two cases, it is easy to deduce that in this
case, we would only have simple copoints, namely $L\cup v_{r-1}$, $L\cup
v_{r}$, $L\cup h_{i},\dots,L\cup h_{n-r}$ and no multiple copoint.

In fact, $L$ can still be a positive coline of the positroid, even if $v_{i}$
and $v_{i+1}$ were not the last two sinks of the positroid. We next explain
when and why.

Suppose $v_{i}$ and $v_{i+1}$ are not the last two sinks of the positroid.

$v_{i}$$v_{i+1}$$h_{j}$$v_{i+2}$$v_{i+3}$$h_{j+1}$$h_{j+3}$••••••••••••••••

Figure 11:

$v_{i}$$v_{i+1}$$h_{j}$$v_{i+2}$$v_{i+3}$$h_{j+3}$$h_{j+5}$••••••••••••••••••••••

Figure 12:

As we just saw previously, no matter how the sources directly following
$v_{r}$ are linked, the closure of all sinks except for $v_{i}$ and $v_{i+1}$
is always a positive coline. The problems only arise when something similar to
Figure 10 happens. As mentioned before, we can’t have at the same time,
sources linked to $v_{r}$ and others only linked to $v_{r-1}$, if these
sources are on the same level, as in Figure 10. However, this case can happen
when such sources are on different levels. We can notice in figure 11 that
$h_{j+1}$ is linked to $v_{i+1}$ (and intersects the path from $h_{j}$ to
$v_{i+1}$) and $h_{j+3}$ is only linked to $v_{i}$. This will not allow the
closure $cl(V-\\{v_{i},v_{i+1}\\})$ to be a positive coline since $L\cup
v_{i+1}$ is the only simple copoint and $L\cup v_{1}\cup h_{j+3}$ and $L\cup
h_{j}\cup h_{j+1}\cup h_{j+2}$ are the multiple copoints. Nonetheless, we
prove in this case, that the closure $L=cl(V-\\{v_{i},v_{i+2}\\})$ is a
positive coline. We notice here that any source linked to $v_{i+2}$ is also
linked to $v_{i}$, which makes $L\cup v_{i+2}$ a simple copoint. Moreover, any
other source next to $h_{j+1}$ and on the same level (if it exists) will also
be linked to $v_{i}$ without intersecting the path from $h_{j+1}$ to
$v_{i+2}$, no matter how the linking is, because otherwise it will form a
parallel pair with $h_{j+1}$. This leads to $L\cup h_{j+1}$ and $L\cup
h_{j+2}$ being simple copoints as well. The only multiple copoint in this case
is $L\cup v_{i}\cup h_{j}\cup h_{j+3}$, which in a more general case, will
include all sources linked to $v_{i}$ and not to $v_{i+2}$. This may also
include $h_{j+2}$, if it was not linked to $v_{i+2}$. Note here, that if
$h_{j+1}$ is not linked to $v_{i+1}$, then we are back to the first case,
where $L=cl(V-\\{v_{i},v_{i+1}\\})$ is the positive coline.

It is important to mention as well that if 3 or more sources following
$v_{i+1}$ on the same level are linked to $v_{i+1}$ and $v_{i}$ the same way
$h_{j}$ is (Figure 12), then $L=cl(V-\\{v_{i},v_{i+1}\\})$ would also be a
positive coline. ∎

######  Corollary 5.1.1.

Some positive coline of a simple positroid of rank $\geq 3$ is either
$L=cl(V-\\{v_{i},v_{i+1}\\})$ or $L=cl(V-\\{v_{i},v_{i+2}\\})$, or both, where
$v_{i}$ and $v_{i+1}$ are the last two consecutive sinks of the positroid.

We put this result in the context of the results from Goddyn et al.[9] and
recall the definition of a GSP oriented matroid that was introduced there. We
say that an oriented matorid $\mathcal{O}$ is a _generalized series-parallel_
(GSP) if every simple minor of $\mathcal{O}$ has a $\\{0,\pm 1\\}$-valued
coflow which has at most two nonzero entries. In the same work, the authors
show that every GSP-oriented matroid with no loops has a NZ-3 coflow, i.e. is
3-colorable. Additionally, they proved the following lemma.

######  Lemma 5.2 ([9] Lemma 6).

If an orientable matroid $M$ has a positive coline, then every orientation
$\mathcal{O}$ of $M$ has a $\\{0,\pm 1\\}$-valued coflow which has exactly two
nonzero entries.

Since positroids are closed under taking minors, Lemma 5.2 along with Theorem
5.1 imply that the class of simple positroids is a subclass of the class of
GSP-oriented matroids. Thus, the main result follows immediately.

######  Theorem 5.3.

Simple positroids are 3-colorable.

##  6 Conclusion

Originally our plan was to prove that every simple gammoid of rank at least
$2$ is 3-colorable by proving the existence of a positive coline, but as
mentioned in the introduction, this was proven to be false by Guzman-Pro and
Hochstättler in [10]. Nevertheless, the authors showed in the same work that
we don’t necessarily need a positive coline to prove the 3-colorability of an
oriented matroid, we only need a coline with at least two simple copoints, and
in this way they proved that cobicircular matroids are 3-colorable. This leads
to the following question which, if answered positively, would prove the
3-colorability of gammoids since gammoids are closed under minors.

######  Question 1.

Does every simple gammoid have a coline with at least two simple copoints?

### Acknowledgements

The authors would like to thank and acknowledge the anonymous referee whose
report helped to improve this work and to detect an error in a previous proof
of Theorem 5.1.

## References

  * [1] Immanuel Albrecht.  Contributions to the Problems of Recognizing and Coloring Gammoids.  PhD thesis, FernUniversität in Hagen.  2018\.
  * [2] Immanuel Albrecht and Winfried Hochstättler.  Simple gammoids of rank 3 have positive colines.  Technical report, FernUniversität in Hagen, 2018.
  * [3] Immanuel Albrecht and Winfried Hochstättler.  Lattice path matroids are 3-colorable.  Technical report, FernUniversität in Hagen, 2018.
  * [4] Federico Ardila, Felipe Rincón, and Lauren Williams.  Positroids and non-crossing partitions.  Trans. Amer. Math. Soc., 368(1):337–363, 2016.
  * [5] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler.  Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, second edition, 1999.
  * [6] Joseph E. Bonin.  An introduction to transversal matroids.  2010\.
  * [7] Jim Geelen.  Matroids with no $M(K_{4})$-minor, 2013 (accessed April 30, 2015).  http://matroidunion.org/?p=139.
  * [8] Luis Goddyn and Winfried Hochstättler.  Nowhere-zero flows in regular matroids and hadwiger’s conjecture.  Seminarberichte der Mathematik – FernUniversität in Hagen, 87:97 – 102, 2015.
  * [9] Luis Goddyn, Winfried Hochstättler, and Nancy Ann Neudauer.  Bicircular matroids are 3-colorable.  Discrete Mathematics, 339(5):1425–1429, 2016.
  * [10] Santiago Guzmán-Pro and Winfried Hochstättler.  Oriented cobicircular matroids are $gsp$.  arXiv:2209.06591 [math.CO], 2022.
  * [11] Winfried Hochstättler and Jaroslav Nešetřil.  Antisymmetric flows in matroids.  Eur. J. Comb., 27(7):1129–1134, 2006.
  * [12] Winfried Hochstättler and Robert Nickel.  The flow lattice of oriented matroids.  Contrib. Discrete Math., 2(1):67–85, 2007.
  * [13] Winfried Hochstättler and Robert Nickel.  On the chromatic number of an oriented matroid.  J. Combin. Theory Ser. B, 98(4):698–706, 2008.
  * [14] Winfried Hochstättler.  A hadwiger conjecture for hyperplane arrangments.  Technical report, FernUniversität in Hagen, 2009.
  * [15] James Oxley.  Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics.  Oxford University Press, Oxford, second edition, 2011.
  * [16] Alexander Postnikov.  Total positivity, grassmannians, and networks.  Technical report, arXiv, 10 2006.  arXiv:math/0609764.