# Rainbow and monochromatic circuits and cuts in binary matroids

Kristóf Bérczi MTA-ELTE Momentum Matroid Optimization Research Group and MTA-
ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd
University, Budapest, Hungary. Email<EMAIL_ADDRESS>Tamás
Schwarcz MTA-ELTE Momentum Matroid Optimization Research Group, Department of
Operations Research, Eötvös Loránd University, Budapest, Hungary. Email:
<EMAIL_ADDRESS>
###### Abstract

Given a matroid together with a coloring of its ground set, a subset of its
elements is called rainbow colored if no two of its elements have the same
color. We show that if an $n$-element rank $r$ binary matroid $M$ is colored
with exactly $r$ colors, then $M$ either contains a rainbow colored circuit or
a monochromatic cut. As the class of binary matroids is closed under taking
duals, this immediately implies that if $M$ is colored with exactly $n-r$
colors, then $M$ either contains a rainbow colored cut or a monochromatic
circuit. As a byproduct, we give a characterization of binary matroids in
terms of reductions to partition matroids.

Motivated by a conjecture of Bérczi et al., we also analyze the relation
between the covering number of a binary matroid and the maximum number of
colors or the maximum size of a color class in any of its rainbow circuit-free
colorings. For simple graphic matroids, we show that there exists a rainbow
circuit-free coloring that uses each color at most twice only if the graph is
$(2,3)$-sparse, that is, it is independent in the $2$-dimensional rigidity
matroid. Furthermore, we give a complete characterization of minimally rigid
graphs admitting such a coloring.

Keywords: Binary matroids, Rainbow circuit-free colorings, Covering number

##  1 Introduction

Matroids play a crucial role in optimization problems due to their high level
of abstraction that enables them to represent various combinatorial objects.
In many cases, however, the underlying matroidal structure is still difficult
to work with, and a simpler matroid is required that provides a ‘good’
approximation of the original one. In this paper, we consider colorings of
matroids that defines simpler partition matroids providing such an
approximation.

Given a matroid together with a coloring of its ground set, a subset of its
elements is called rainbow colored if it does not contain two elements of the
same color. Accordingly, a coloring is called rainbow circuit-free or rainbow
cut-free if no circuit or cut is rainbow colored, respectively.

Every loopless matroid of rank $r$ has a rainbow circuit-free coloring with
exactly $r$ colors by the following construction: for $i=r,r-1\dots,1$, let
$S_{i}$ be a cut of the matroid $M|(S-\bigcup_{j>i}S_{j})$, where $|$ denotes
the restriction operator. Note that this way $S_{i}$ is a cut of the rank $i$
matroid $M|(S_{1}\cup\dots\cup S_{i})$, motivating the reversed ordering of
the indices. We call colorings obtained by this construction
standard.111Standard colorings were previously defined for graphs in [8]; we
extend this notion for arbitrary matroids. We show in Section 3.1 that
standard colorings are indeed rainbow circuit-free. Obviously, if the matroid
contains a loop then no rainbow circuit-free coloring exists. Therefore every
matroid considered in the paper is assumed to be loopless without explicitly
mentioning this. Nevertheless, parallel elements might exist.

It is worth mentioning that not every rainbow circuit-free coloring is
standard. To illustrate this, consider the uniform matroid $U_{2,4}$ of rank
two on four elements. As every circuit consists of three elements, any
coloring of the matroid with two colors is rainbow circuit-free. However, if
both color classes contain two elements then no monochromatic cut exists, so
the coloring cannot be obtained by the above algorithm.

#### Previous work

Simplifications of matroids appeared already in the late 60’s when Crapo and
Rota [3] introduced the notion of weak maps. Following the terminology of [2],
given two matroids $N$ and $M$ on the same ground set, $N$ is said to be a
reduction of $M$ if every independent set of $N$ is also independent in $M$.
If, furthermore, the rank of $N$ coincides with that of $M$, then $N$ is a
rank-preserving reduction of $M$. In terms of weak maps, a reduction
corresponds to the identity weak map on the common ground set of the two
matroids.

Lucas [13, 14] studied rank-preserving reductions of binary matroids together
with the behavior of certain invariants under reductions, such as the Tutte
polynomial, Whitney numbers, or the Möbius function. For further results and
remarks on weak images, we refer the interested reader to [10].

Hoffman et al. [8] considered rainbow cycle-free edge colorings of finite
graphs. They proved that every rainbow cycle-free coloring of a connected
graph on $n$ vertices with $n-1$ colors implies a monochromatic edge cut in
$G$. They also showed that every such coloring can be obtained by taking and
removing cuts from the graph sequentially – in an analogous way as described
in the introduction.

In a recent paper, Im et al. [9] studied the so-called matroid intersection
cover problem, a special case of set cover where the sets are derived from the
intersection of matroids. Their approach is based on partition decompositions
of matroids, a generalization of reductions to partition matroids. They gave
polynomial-time algorithms to compute such partition decompositions for
several matroid classes that commonly arise in combinatorial optimization
problems.

In an independent work [2], Bérczi et al. investigated the list coloring
number of the intersection of two matroids. A key tool in their approach was
finding a reduction of a matroid to a partition matroid without increasing its
coloring number too much. They proved that such a reduction exists for paving,
graphic matroids, and gammoids – for all those cases, they verified the
existence of a reduction into a partition matroid with coloring number at most
twice that of the original matroid.

#### Our results

Rank-preserving reductions define a natural partial order on the set of
matroids. It is not difficult to check that the minimal elements with respect
to this partial order correspond to partition matroids with upper bounds one
on the partition classes, therefore the structurally simplest approximations
of any matroid fall in this class. This motivates the investigation of
reductions from an arbitrary matroid to a partition matroid; we will see that
reductions of such form correspond to rainbow circuit-free colorings. In this
paper, we concentrate on binary matroids.

Our first main result is the following alternative theorem.

######  Theorem 1.

Let $M$ be an $n$-element binary matroid of rank $r$.

  1. 1.

If the ground set of $M$ is colored with exactly $r$ colors, then $M$ either
contains a rainbow circuit or a monochromatic cut.

  2. 2.

If the ground set of $M$ is colored with exactly $n-r$ colors, then $M$ either
contains a rainbow cut or a monochromatic circuit.

As a consequence, we show that the structure of rainbow circuit-free and
rainbow cut-free colorings is rather restricted.

######  Corollary 2.

Let $M$ be an $n$-element binary matroid of rank $r$.

  1. 1.

If the ground set of $M$ is colored with exactly $r$ colors and $M$ has no
rainbow circuit, then one of the color classes is a cut of $M$.

  2. 2.

If the ground set of $M$ is colored with exactly $n-r$ colors and $M$ has no
rainbow cut, then one of the color classes is a circuit of $M$.

######  Corollary 3.

Every rainbow circuit-free coloring of a rank $r$ binary matroid with $r$
colors is standard. In particular, one of the color classes consists of
parallel elements.

Somewhat surprisingly, the reverse implication also holds, therefore we get a
characterization of binary matroids.

######  Theorem 4.

A matroid of rank $r$ is binary if and only if each of its rainbow circuit-
free colorings with exactly $r$ colors is standard.

We provide several applications of the above results. As a local counterpart
of strongly base orderability, we introduce the notion of locally strongly
base orderable basis-pairs and characterize those for binary matroids.

######  Theorem 5.

Let $M$ be a binary matroid and let $B_{1}$ and $B_{2}$ be bases of $M$ such
that $S=B_{1}\cup B_{2}$. Then $B_{1}$ and $B_{2}$ are locally strongly base
orderable if and only if $M/(B_{1}\cap B_{2})$ has a standard coloring with
color classes of size two. In particular, if $B_{1}$ and $B_{2}$ are disjoint
and $M$ is simple, then no such bijection exists.

Note that the assumption $S=B_{1}\cup B_{2}$ is not restrictive as the
restriction of $M$ to $B_{1}\cup B_{2}$ is also binary.

An interesting problem of matroidal optimization is to cover the ground set of
two matroids by a minimum number of common independent sets. Recently, several
works attempted to attack this problem through rainbow circuit-free colorings
with small color classes. We focus on the relation between the covering number
of a matroid and the maximum size of a color class, where the covering number
of the matroid is defined as the minimum number of independent sets needed to
cover its ground set.

######  Theorem 6.

For every positive integer $g$, there exists a $2$-coverable binary matroid
$M$ such that in any rank-preserving rainbow circuit-free coloring of $M$, one
of the colors is used at least $g$ times.

We also prove a general statement that provides lower and upper bounds on the
number of colors used in a rainbow circuit-free coloring with bounded sized
color classes.

######  Theorem 7.

Let $M$ be a matroid, $g\geq 3$ be a positive integer, and $\mathcal{C}$ be a
family of circuits of $M$ such that for every $0\leq i\leq g-1$ and for every
$X\subseteq S,|X|=i$ we have $|\\{C\in\mathcal{C}:\ |X\cap C|\geq 2\\}|\leq
i-1$. Then in any rainbow circuit-free coloring of $M$ such that each color is
used at most $(g-1)$-times, the number of different colors is between
$|\mathcal{C}|/(g-2)$ and $|S|-|\mathcal{C}|$.

As a consequence, we show that if every color can occurs at most three times
then the number of colors used in a rainbow circuit-free coloring might be
only a fraction of the rank of the original matroid.

######  Corollary 8.

Given any positive integer $r$, there exists a $2$-coverable connected binary
matroid of rank $r$ such that in any rainbow circuit-free coloring of $M$ such
that each color is used at most three times, the number of colors is at most
$\lceil 6/7\cdot r\rceil$.

Finally, we consider rainbow circuit-free colorings that do not increase the
covering number of the matroid. For simple graphic matroids, we show that
there exists a rainbow circuit-free coloring that uses each color at most
twice only if the graph is independent in the $2$-dimensional rigidity
matroid.

######  Theorem 9.

If a simple graphic matroid has a rainbow circuit-free coloring such that each
color is used at most twice, then the corresponding graph is $(2,3)$-sparse.

Furthermore, we give a complete characterization of minimally rigid graphs
that admit such a coloring in terms of Henneberg operations.

######  Theorem 10.

Let $G=(V,E)$ be a simple graph such that $|E|=2\cdot|V|-3$. Then the graphic
matroid of $G$ has a rainbow circuit-free coloring using each color at most
twice if and only if $G$ can be constructed from $K_{2}$ by a sequence of (H0)
operations.

##  2 Preliminaries

#### General notation

Let $G=(V,E)$ be an undirected graph, $X\subseteq V$ be a subset of vertices,
and $F\subseteq E$ be a subset of edges. We denote the set of edges spanned by
$X$ by $E[X]$, while the set of edges incident to a vertex $v\in V$ is denoted
by $\delta(v)$. The graphs obtained by deleting $X$ or $F$ are denoted by
$G-X$ and $G-F$, respectively. An inclusionwise minimal subset of edges whose
deletion increases the number of connected components of $G$ is called an
elementary cut.

Given a ground set $S$ together with subsets $X,Y\subseteq S$, the difference
of $X$ and $Y$ is denoted by $X-Y$. If $Y$ consists of a single element $y$,
then $X-\\{y\\}$ and $X\cup\\{y\\}$ are abbreviated as $X-y$ and $X+y$,
respectively.

#### Matroids

Matroids were introduced as abstract generalizations of linear independence by
Whitney [19] and independently by Nakasawa [16]. A matroid $M=(S,\mathcal{I})$
is defined by its ground set $S$ and its family of independent sets
$\mathcal{I}\subseteq 2^{S}$ that satisfies the independence axioms: (I1)
$\emptyset\in\mathcal{I}$, (I2) $X\subseteq Y,\ Y\in\mathcal{I}\Rightarrow
X\in\mathcal{I}$, and (I3) $X,Y\in\mathcal{I},\ |X|<|Y|\Rightarrow\exists e\in
Y-X\ s.t.\ X+e\in\mathcal{I}$. The maximum size of an independent subset of a
set $X$ is the rank of $X$ and is denoted by $r_{M}(X)$. The maximal
independent subsets of $S$ are called bases. A circuit is an inclusionwise
minimal non-independent set, while a loop is a circuit consisting of a single
element. The matroid is connected if for any two elements $e,f\in S$ there
exists a circuit containing both. A cut is an inclusionwise minimal set
$X\subseteq S$ that intersects every basis. Although in general a cut and a
circuit can intersect each other in an odd number of elements, the size of
their intersection cannot be one. Two non-loop elements $e,f\in S$ are
parallel if $r_{M}(\\{e,f\\})=1$. A set $X\subseteq S$ is closed or is a flat
if $r_{M}(X+e)>r_{M}(X)$ for every $e\in S-X$. A flat of rank $r_{M}(S)-1$ is
called a hyperplane.

The restriction of a matroid $M=(S,\mathcal{I})$ to a subset
$S^{\prime}\subseteq S$ is again a matroid
$M|S^{\prime}=(S^{\prime},\mathcal{I}^{\prime})$ with independence family
$\mathcal{I}^{\prime}=\\{I\in\mathcal{I}:\ I\subseteq S^{\prime}\\}$. The
contraction of a flat $S^{\prime\prime}\subseteq S$ results in a matroid
$M/S^{\prime\prime}=(S-S^{\prime\prime},\mathcal{I}^{\prime\prime})$ where
$\mathcal{I}^{\prime\prime}=\\{I\in\mathcal{I}:\ I\subseteq
S-S^{\prime\prime},|I|=r_{M}(S^{\prime\prime}\cup
I)-r_{M}(S^{\prime\prime})\\}$. A matroid $N$ that can be obtained from $M$ by
a sequence of restrictions and contractions is called a minor of $M$; in this
case $M$ contains $N$ as a minor. The dual of $M$ is the matroid
$M^{*}=(S,\mathcal{I}^{*})$ where $\mathcal{I}^{*}=\\{X\subseteq S:\ S-X\
\text{contains a basis of $M$}\\}$. The direct sum $M_{1}\oplus M_{2}$ of
matroids $M_{1}=(S_{1},\mathcal{I}_{1})$ and $M_{2}=(S_{2},\mathcal{I}_{2})$
on disjoint ground sets is a matroid $M=(S_{1}\cup S_{2},\mathcal{I})$ whose
independent sets are the disjoint unions of an independent set of $M_{1}$ and
an independent set of $M_{2}$.

The minimum size of a circuit is called the girth, while the minimum size of a
cut is called the co-girth of the matroid. It is not difficult to check that a
circuit of a matroid $M$ is a cut in the dual matroid $M^{*}$ and vice versa,
thus the girth and co-girth of $M$ are the same as the co-girth and girth of
$M^{*}$, respectively.

For non-negative integers $r\leq n$, the uniform matroid $U_{r,n}$ is defined
on an $n$-element set by setting every set of size at most $r$ to be
independent. A matroid is binary if there exists a family of vectors from a
vector space over the finite field $GF(2)$ whose linear independence relation
is the same as that of the matroid. Binary matroids form a minor-closed class
that is also closed for taking dual. Tutte [17, 18] gave the following
forbidden minor characterization of binary matroids.

######  Theorem 11 (Tutte).

A matroid is binary if and only if it has no $U_{2,4}$-minor.

A partition matroid is a matroid $N=(S,\mathcal{J})$ such that
$\mathcal{J}=\\{X\subseteq S:\ |X\cap S_{i}|\leq 1\ \text{for
$i=1,\dots,q$}\\}$ for some partition $S=S_{1}\cup\dots\cup S_{q}$.222In
general, the upper bounds might be different for the different partition
classes. As all the partition matroids used in the paper have all-ones upper
bounds, we make this restriction without explicitly mentioning it. For a graph
$G=(V,E)$, the graphic matroid $M=(E,\mathcal{I})$ of $G$ is defined as
$\mathcal{I}=\\{F\subseteq E:\ F\ \text{does not contain a cycle}\\}$, that
is, a subset $F\subseteq E$ is independent if it is a forest. The dual of the
graphic matroid is called the co-graphic matroid of $G$. Note that a subset
$F\subseteq E$ is a circuit of the co-graphic matroid if and only if $F$ is an
elementary cut of $G$.

Given two matroids $M=(S,\mathcal{I})$ and $N=(S,\mathcal{J})$ over the same
ground set, we say that $N$ is a reduction of $M$ if every independent set of
$N$ is also independent in $M$, that is, $\mathcal{J}\subseteq\mathcal{I}$. We
denote such a relation by $N\preceq M$. If, furthermore, the rank of $N$
coincides with that of $M$, then $N$ is a rank-preserving reduction of $M$
which is denoted by $N\preceq_{r}M$.

Lucas [13] studied rank-preserving reductions of binary matroids, and proved
the following result that we will rely on.

######  Theorem 12 (Lucas).

Let $M$ and $N$ be binary matroids such that $N\preceq_{r}M$ and $N\neq M$.
Then there is a non-empty flat $F$ of $M$ such that

$N\preceq_{r}M|F\oplus M/F\preceq_{r}M.$

#### Colorings and reducibility

There is a one-to-one correspondence between rainbow circuit-free colorings of
a matroid and its reductions to partition matroids. Indeed, if we pick one
element from each color class of any rainbow circuit-free coloring, then the
resulting set is independent – in other words, the partition matroid defined
by the color classes provides a reduction of the matroid. Vice versa, taking
the partition classes of any reduction to a partition matroid as color classes
gives a rainbow circuit-free coloring. By the above, the terms ‘rainbow
circuit-free colorings’ and ‘reductions to partition matroids’ are
interchangeable and are used alternatingly throughout the paper depending on
the context. In particular, a rank-preserving rainbow circuit-free coloring
corresponds to a rank-preserving reduction to a partition matroid.

##  3 Rainbow circuit-free colorings

###  3.1 Standard colorings

Recall that a coloring was defined to be standard if, after possibly
reindexing the color classes, $S_{i}$ is a cut of the matroid
$M|(S_{1}\cup\dots\cup S_{i})$ for $i=1,\dots,r$. We show that every standard
coloring is rainbow circuit-free, together with some equivalent formulations
of standard colorings which will be used later.

######  Lemma 13.

Let $M$ be a matroid of rank $r$ and $S=S_{1}\cup\dots\cup S_{r}$ be partition
of its ground set into $r$ color classes. The followings are equivalent:

  1. (i)

$S_{i}$ is a cut of $M|(S_{1}\cup\dots\cup S_{i})$ for $i=1,\dots,r$,

  2. (ii)

the coloring is rainbow circuit-free and $r_{M}(S_{1}\cup\dots\cup S_{i})=i$
for $i=1,\dots r$,

  3. (iii)

each $S_{i}$ is non-empty and $S_{1}\cup\dots\cup S_{i}$ is closed in $M$ for
$i=1,\dots,r$.

###### Proof.

First we show that (i) implies (ii). As the deletion of a cut decreases the
rank of a matroid by exactly one, $r_{M}(S_{1}\cup\dots\cup S_{i})=i$ indeed
holds for $i=1\dots,r$. For any circuit $C$ of $M$, let $i$ be the largest
index for which $C\cap S_{i}$ is non-empty. Then $C\subseteq
S_{1}\cup\dots\cup S_{i}$ and $S_{i}$ is a cut of $M|(S_{1}\cup\dots\cup
S_{i})$, hence $|C\cap S_{i}|\geq 2$. Therefore no circuit $C$ is rainbow
colored.

Assume next that (ii) holds. For every $i=1,\dots,r$ and $s\in
S-\bigcup_{j=1}^{i}S_{j}$, exactly $i+1$ colors appear in $S_{1}\cup\dots\cup
S_{i}\cup\\{s\\}$, hence $r_{M}(S_{1}\cup\dots\cup S_{i}\cup\\{s\\})\geq i+1$
as each rainbow set is independent. Then $r_{M}(S_{1}\cup\dots\cup
S_{i}\cup\\{s\\})>r_{M}(S_{1}\cup\dots\cup S_{i})$, hence $S_{1}\cup\dots\cup
S_{i}$ is closed, proving that (ii) implies (iii).

Finally, suppose that (iii) holds. As $S_{1}\subset(S_{1}\cup
S_{2})\subset\dots\subset(S_{1}\cup\dots\cup S_{r})$ is a strictly increasing
chain of flats, we have $1\leq r_{M}(S_{1})<r_{M}(S_{1}\cup
S_{2})<\dots<r_{M}(S_{1}\cup\dots\cup S_{r})=r$, hence
$r_{M}(S_{1}\cup\dots\cup S_{i})=i$ for $i=1,\dots,r$. As $S_{1}\cup\dots\cup
S_{i-1}$ is also a closed set of $M|(S_{1}\cup\dots\cup S_{i})$, $S_{i}$ is
the complement of a hyperplane of $M|(S_{1}\cup\dots\cup S_{i})$, that is,
$S_{i}$ is a cut of this matroid, proving that (iii) implies (i). ∎

Note that (iii) provides the following algorithm for constructing standard
colorings: For $i=1,\dots,r$, pick an element $s_{i}\in S-(S_{1}\cup\dots\cup
S_{i-1})$, and let $S_{i}$ be the closure of $S_{1}\cup\dots\cup
S_{i-1}\cup\\{s_{i}\\}$ in $M$. As flats of rank 1 are exactly the classes of
parallel elements, the following is yet another way to formulate this
algorithm: Let $S_{i}$ be a class of parallel elements in
$M/(S_{1}\cup\dots\cup S_{i-1})$ for $i=1,\dots,r$.

###  3.2 Rainbow and monochromatic circuits and cuts

Based on Lucas’ theorem, we turn to the proof of our first result.

See 1

###### Proof.

As the class of binary matroids is closed under taking duals and the cuts of a
matroid coincide with the circuits of the dual matroid, it suffices to prove
the first statement. We proceed by induction on the size of the ground set $S$
of $M$. Let $N$ be the partition matroid defined by the coloring of $M$.
Recall that $N\preceq_{r}M$ holds. If $N=M$, then each color class is a
monochromatic cut of $M$. Otherwise, by Theorem 12 there exists a non-empty
flat $F$ of $M$ such that $N\preceq_{r}M|F\oplus M/F\preceq_{r}M$. From
$N\preceq M|F\oplus M/F$ it follows that $N|F\preceq M|F$ and $N|(S-F)\preceq
M/F$. This implies that

$\displaystyle r{}$ $\displaystyle{}=r_{N}(S)$ $\displaystyle{}\leq
r_{N}(F)+r_{N}(S-F)$ $\displaystyle{}\leq r_{M}(F)+r_{M/F}(S-F)$
$\displaystyle{}=r_{M}(S)=r,$

hence $r_{N}(F)=r_{M}(F)$ and $r_{N}(S-F)=r_{M/F}(S-F)$. Therefore we get
$N|F\preceq_{r}M|F$ and $N|(S-F)\preceq_{r}M/F$. Applying the induction
hypothesis to the reduction $N|(S-F)\preceq_{r}M/F$, we get a monochromatic
cut of $M/F$. As each cut of $M/F$ is also a cut of $M$, the original matroid
$M$ has a monochromatic cut as well. ∎

See 2

###### Proof.

By duality it suffices to prove the first statement. If $M$ has no rainbow
circuit, then by Theorem 1 it has a cut $C$ and a color class $C^{\prime}$
such that $C\subseteq C^{\prime}$. If $C\subsetneq C^{\prime}$, then each
color class intersects $S-C$. As rainbow colored sets of size $r$ are bases of
$M$, this implies that there is a basis of $M$ which is disjoint from the cut
$C$, a contradiction. Hence $C=C^{\prime}$, that is, the color class
$C^{\prime}$ is a cut of $M$. ∎

See 3

###### Proof.

As the restriction of a binary matroid is binary again, Corollary 2 implies
that the color classes $S_{1},\dots,S_{r}$ can be indexed in such a way that
$S_{i}$ is a cut of $M|(S-\bigcup_{j>i}S_{j})$. In particular, the color class
$S_{1}$ consists of parallel elements of $M$. ∎

###  3.3 Characterization of binary matroids

The aim of this section is to prove Theorem 4. The proof is based on the
excluded-minor characterization of binary matroids, so we first prove two
lemmas about standard colorings of minors of matroids.

######  Lemma 14.

Consider a standard coloring of a matroid $M$ and let $Z\subseteq S$ be a
subset such that exactly $r_{M}(Z)$ colors appear in $Z$. Then the coloring
restricted to $Z$ is a standard coloring of $M|Z$.

###### Proof.

Let $S_{1},\dots,S_{r}$ denote the color classes such that $S_{1}\cup\dots\cup
S_{i}$ is closed in $M$ for $i=1,\dots,r$ (such an ordering exists by Lemma
13). Let $1\leq i_{1}<i_{2}<\dots<i_{r_{M}(Z)}\leq r$ denote the indices of
colors appearing in $Z$. Then $(S_{i_{1}}\cap Z)\cup(S_{i_{2}}\cap
Z)\cup\dots\cup(S_{i_{j}}\cap Z)=(S_{1}\cup S_{2}\cup\dots\cup S_{i_{j}})\cap
Z$ is closed in $M|Z$ for $j=1,\dots,r_{M}(Z)$, hence the coloring of $M|Z$
with color classes $Z\cap S_{i_{1}},\dots,Z\cap S_{i_{r_{M}(Z)}}$ is standard.
∎

The proof of Theorem 4 will rely on the following lemma.

######  Lemma 15.

Let $F$ be a flat of a matroid $M$. If either the restriction $M|F$ or the
contraction $M/F$ has a non-standard rank-preserving coloring without rainbow
circuits, then so does $M$.

###### Proof.

Let $N=M/F\oplus M|F$ and $r=r_{M}(S)=r_{N}(S)$. Consider a coloring of either
$M|F$ or $M/F$ provided by the assumption of the lemma and extend it to $S$ by
a standard coloring of $M/F$ or $M|F$, respectively, such that the color sets
used on $M|F$ and $M/F$ are disjoint. This way we get a rainbow circuit-free
coloring of $N$ with exactly $r$ colors. As $N\preceq_{r}M$, this also a
rainbow circuit-free coloring of $M$.

The restriction of the coloring to either $N|F$ or $N|(S-F)$ is non-standard
by the construction, hence, by Lemma 14, it is a non-standard coloring of $N$.
Suppose for contradiction that it is a standard coloring of $M$. By Lemma 13,
there is an ordering $S_{1},\dots,S_{r}$ of the color classes such that
$r_{M}(S_{1}\cup\dots\cup S_{i})=i$ for $i=1,\dots,r$. As $N\preceq M$, this
implies that $r_{N}(S_{1}\cup\dots\cup S_{i})\leq r_{M}(S_{1}\cup\dots\cup
S_{i})=i$. As it is a rainbow circuit-free coloring of $N$, we have
$r_{N}(S_{1}\cup\dots\cup S_{i})\geq i$ as well, thus
$r_{N}(S_{1}\cup\dots\cup S_{i})=i$ for $i=1,\dots,r$. Therefore, it is a
standard coloring of $N$ by Lemma 13, a contradiction. ∎

We are ready to prove the theorem.

See 4

###### Proof.

By Corollary 3, it suffices to show that a non-binary matroid $M$ has a non-
standard rainbow circuit-free coloring with exactly $r$ colors. As $M$ is non-
binary, by Theorem 11, it has a minor isomorphic to $U_{2,4}$. That is, there
exists a flat $F$ of $M$ and a subset $T\subseteq S-F$ such that $(M/F)|T$ is
isomorphic to $U_{2,4}$. Let $G$ denote the closure of $T$ in $M/F$. As $T$
has rank 2 in $M/F$, $N=(M/F)|G$ is a matroid of rank 2. Let
$G=P_{1}\cup\dots\cup P_{q}$ denote the partition of $G$ into classes of
parallel elements of $N$. As $N|T$ is isomorphic to $U_{2,4}$, we have $q\geq
4$. Color $G$ with two colors such that the color classes are $P_{1}\cup
P_{2}$ and $P_{3}\cup\dots\cup P_{q}$. Since $N$ has rank 2 and parallel
elements receive the same color, this is a rank-preserving coloring of $N$
without rainbow circuits. Moreover, neither $P_{1}\cup P_{2}$ nor
$P_{3}\cup\dots\cup P_{q}$ is closed in $N$, hence it is a non-standard
coloring of $N$. Applying Lemma 15 to $M/F$ and to the restriction
$N=(M/F)|G$, we get that $M/F$ has a non-standard rank-preserving coloring
without rainbow circuits (note that $G$ is closed in $M/F$). Now applying
Lemma 15 to $M$ and to the contraction $M/F$, we get that $M$ also has a non-
standard rank-preserving rainbow circuit-free coloring, concluding the proof
of the theorem. ∎

##  4 Consequences

###  4.1 Binary matroids and strongly base orderability

Given two bases $B_{1}$ and $B_{2}$ of a matroid, there exists a bijection
$\varphi:B_{1}\to B_{2}$ with the property that $B_{1}-x+\varphi(x)$ is a
basis for each $x\in B_{1}-B_{2}$ (see e.g. [4, Theorem 5.3.4]). A
strengthening of this observation was given by Greene and Magnanti [6].

######  Theorem 16 (Greene and Magnanti).

Let $B_{1}$ and $B_{2}$ be two bases of a matroid $M$ and let
$\\{X_{1},\dots,X_{q}\\}$ be a partition of $B_{1}$. Then there is a partition
$\\{Y_{1},\dots,Y_{q}\\}$ of $B_{2}$ for which $(B_{1}-X_{i})\cup Y_{i}$ is a
basis for $i=1,\dots,q$.

Let us make two important observations. First, the roles of $B_{1}$ and
$B_{2}$ in Theorem 16 are not symmetric, hence $(B_{2}-Y_{i})\cup X_{i}$ might
not be a basis of $M$ for some $i$. Second, only single exchanges are
possible, hence $(B_{1}-(X_{i}\cup X_{j}))\cup(Y_{i}\cup Y_{j})$ might not be
a basis for some pair $i\neq j$.

Strongly base orderable matroids form a class of matroids with distinguished
structural properties overcoming the above difficulties. A matroid $M$ with
basis-family $\mathcal{B}$ is strongly base orderable if for any two bases
$B_{1},B_{2}\in\mathcal{B}$ there exists a bijection $\varphi:B_{1}\to B_{2}$
with the property that

(SBO) $(B_{1}-X)\cup\varphi(X)\in\mathcal{B}\quad\text{for}\ X\subseteq
B_{1}.$

Several matroid classes that appear in combinatorial optimization problems are
strongly base orderable, such as gammoids (and so partition, laminar, or
transversal matroids), while others do not possess such nice characteristics,
e.g. graphic or paving matroids.

As a local counterpart of strongly base orderability, we say that two bases
$B_{1}$ and $B_{2}$ of a matroid are locally strongly base orderable if there
exists a bijection $\varphi:B_{1}\to B_{2}$ satisfying (SBO). With the help of
Theorem 4, we give a characterization of locally strongly base orderable
basis-pairs of binary matroids.

See 5

###### Proof.

Let $M^{\prime}:=M/(B_{1}\cap B_{2})$ and let us denote the rank of
$M^{\prime}$ by $r^{\prime}$. Assume first that $\varphi:B_{1}\to B_{2}$
satisfies (SBO). Consider the coloring of $M^{\prime}$ with $r^{\prime}$ color
classes of the form $\\{x,\varphi(x)\\}$ for $x\in B_{1}-B_{2}$. By (SBO), if
we pick exactly one element from every color class then the resulting set is a
basis of $M^{\prime}$, therefore the coloring is rainbow circuit-free. As
$M^{\prime}$ is binary, the coloring is standard by Theorem 4.

For the opposite direction, consider a standard coloring of $M^{\prime}$ with
color classes of size two. By Lemma 13, there is an ordering
$S_{1},\dots,S_{r^{\prime}}$ of the color classes such that $S_{j}$ consists
of parallel elements of $M^{\prime}/(\bigcup_{k=1}^{j-1}S_{k})$ for
$j=1,\dots,r^{\prime}$. As both $B_{1}-B_{2}$ and $B_{2}-B_{1}$ are bases of
$M^{\prime}$, we get that $|B_{i}\cap S_{j}|=1$ for $i=1,2$ and
$j=1,\dots,r^{\prime}$. Let $S_{j}=\\{x^{1}_{j},x^{2}_{j}\\}$ where
$x^{i}_{j}\in B_{i}$, and define

$\varphi(x)=\begin{cases}x&\text{if $x\in B_{1}\cap B_{2}$},\\\
x^{2}_{j}&\textit{if $x=x^{1}_{j}$ for some
$j\in\\{1,\dots,r^{\prime}\\}$}.\end{cases}$

We claim that $\varphi$ satisfies (SBO). Indeed, for an arbitrary subset
$X\subseteq B_{1}$, the set $(B_{1}-X)\cup\varphi(X)$ contains exactly one
element from each of the $S_{j}$s plus the intersection $B_{1}\cap B_{2}$. As
the coloring was standard for $M^{\prime}$, these elements form a basis of
$M$.

Now we turn to the second half of the theorem. By the first half, there is a
standard coloring of $M$ in which each color class has size two. By Corollary
2, in every standard coloring of $M$ there exists a color class consisting of
parallel elements. However, the matroid is assumed to be simple, a
contradiction. ∎

###  4.2 Covering number and reduction

The covering number of a matroid $M=(S,\mathcal{I})$ is the minimum number of
independent sets from $\mathcal{I}$ needed to cover the ground set $S$.333The
covering number is sometimes called the _coloring_ or _chromatic number_ of
$M$ in the literature. However, it corresponds to a different concept of
coloring than the one discussed in the present paper, therefore we use the
_covering_ version throughout. We say that a matroid is $k$-coverable if its
covering number is at most $k$. The notion of covering number can be
straightforwardly extended to matroid intersection: given two matroids
$M_{1}=(S,\mathcal{I}_{1})$ and $M_{2}=(S,\mathcal{I}_{2})$ over the same
ground set, the covering number of their intersection is the minimum number of
common independent sets needed to cover $S$.

Bérczi et al. [2] and independently Im et al. [9] investigated the existence
of reductions to partition matroids that increase the covering number by only
a constant factor. In particular, the following conjecture was proposed in [2,
Conjecture 8].

######  Conjecture 17 (Bérczi et al.).

Every $k$-coverable matroid can be reduced to a $2\cdot k$-coverable partition
matroid.

The motivation of the conjecture is multifold, let us mention here only two
illustrious examples. The conjecture would provide a new proof for a
celebrated theorem of Aharoni and Berger [1] stating that the covering number
of the intersection of two matroids $M_{1},M_{2}$ is at most twice the maximum
of the covering number of $M_{1}$ and $M_{2}$ plus one. Furthermore, by
relying on Galvin’s list coloring theorem [5] for bipartite graphs, the
conjecture would imply that even the list covering number of the intersection
of two matroids is at most twice its covering number (see [2] for further
details).

We have already seen that reductions to partition matroids can be identified
with rainbow circuit-free colorings. As the covering number of a partition
matroid is just the maximum size of the partition classes defining it, this
parameter translates into the maximum size of a color class of the coloring.
In order to be consistent with the rest of the paper, we follow the coloring
terminology, but all results can be rephrased in terms of reductions.

We show that the strengthening of Conjecture 17 in which the reduction is
required to be rank-preserving does not hold. In fact, we prove a much
stronger result stating that a constant fraction loss in the rank is
unavoidable in certain situations. It is worth mentioning that the results
hold already for co-graphic matroids, which is in sharp contrast to the
graphic case for which the conjecture was shown to be true even with rank-
preserving reduction and with $2\cdot k-1$ in place of $2\cdot k$ [2, 8, 9].
In general, we are not aware of any $k$-coverable matroid that does not admit
a (not necessarily rank-preserving) $(2\cdot k-1)$-coverable reduction.

First we show that for certain matroids the covering number of each rank-
preserving reduction might be large.

See 6

###### Proof.

Let $M=(S,\mathcal{I})$ be a 2-coverable matroid of co-girth $g$. Such a
matroid exists, as shown by the following construction. Every $4$-edge-
connected graph $G$ contains two disjoint spanning trees by Nash-Williams’
theorem [15]. The complements of these spanning trees are bases of the co-
graphic matroid of $G$ together containing every edge of the graph, thus the
co-graphic matroid is $2$-coverable. The co-girth of this matroid is the
minimum size of a cycle of $G$. As there exist $4$-edge-connected graphs with
arbitrarily large girth (see e.g. [12]), the claim follows.

By Corollary 2 (1), any rank-preserving rainbow-free coloring of $M$ has a
color class that forms a cut of $M$ and thus has size at least $g$, concluding
the proof. ∎

Theorem 6 implies that Conjecture 17 does not hold when restricted to rank-
preserving reductions. Based on the following technical statement, we will
show that even a constant factor of the rank might be lost if the covering
number of the reduction is bounded by $2\cdot k-1$.

See 7

###### Proof.

Let $S_{1},\dots,S_{q}$ denote the color classes of a rainbow circuit-free
coloring of $M$ with $|S_{i}|\leq g-1$ for $i=1,\dots,q$. Define
$\mathcal{C}_{i}:=\\{C\in\mathcal{C}:\ |S_{i}\cap C|\geq 2\\}$. As the
coloring is rainbow circuit-free, for each $C\in\mathcal{C}$ there exists a
color that appears at least twice in $C$, hence
$\mathcal{C}=\mathcal{C}_{1}\cup\dots\cup\mathcal{C}_{q}$. By the assumptions
of the theorem, $|\mathcal{C}_{i}|\leq g-2$, hence

$\displaystyle|\mathcal{C}|{}$
$\displaystyle{}\leq|\mathcal{C}_{1}|+\dots+|\mathcal{C}_{q}|$
$\displaystyle{}\leq(g-2)\cdot q,$

implying the the lower bound $|\mathcal{C}|/(g-2)$ on $q$. Observe that
$|\mathcal{C}_{i}|\leq|S_{i}|-1$, hence

$\displaystyle|\mathcal{C}|{}$
$\displaystyle{}\leq|\mathcal{C}_{1}|+\dots+|\mathcal{C}_{q}|$
$\displaystyle{}\leq|S_{1}|-1+\dots+|S_{q}|-1$ $\displaystyle{}=|S|-q,$

implying the upper bound $|S|-|\mathcal{C}|$ on $q$. ∎

See 8

###### Proof.

For $r\leq 6$ the corollary obviously holds as $\lceil 6/7\cdot r\rceil=r$ and
every rainbow circuit-free coloring of a matroid uses at most $r$ colors.

Hence we may assume that $r=7\cdot q+j-1$ for some $q\geq 1$ and $1\leq j\leq
7$. Let $G=(S,T;E)$ denote the complete bipartite graph on seven vertices with
$|S|=3$ and $|T|=4$. Let $T=\\{u,v,w,z\\}$ denote the vertices in the larger
vertex class. For $q\geq 1$, let us construct a graph $G_{q}$ as follows. Take
$q$ disjoint copies of $G$, where the vertex classes and edge set of the $i$th
copy are denoted by $S_{i},T_{i}=\\{u_{i},v_{i},w_{i},z_{i}\\}$ and $E_{i}$,
respectively. Furthermore, connect the subsequent copies by adding the edges
$w_{i}v_{i+1}$ and $z_{i}u_{i+1}$ to $G_{q}$ for $i=1,\dots,q-1$).
Furthermore, let $G^{j}_{q}$ denote the graph obtained from $G_{q}$ by
attaching $j$ vertices to it through vertices $w_{q},z_{q}$ (see Figure 1).

Figure 1: Construction of the graph $G^{j}_{q}$ for $q=3$ and $j=2$,
corresponding to $r=22$

Observe that $G^{j}_{q}$ is the disjoint union of two spanning trees; this
follows from the construction and from the fact that $G$ is the disjoint union
of two spanning trees. This implies that the co-graphic matroid
$M=(S,\mathcal{I})$ of $G^{j}_{q}$ is connected, $2$-coverable, and has rank
$7\cdot q+j-1=r$. Recall that a circuit of $M$ corresponds to an elementary
cut of $G^{j}_{q}$. Define

$\mathcal{C}:=\big{\\{}\delta(v):\ v\ \text{is a vertex of
$G^{j}_{q}$}\big{\\}}\cup\big{\\{}\\{w_{i}v_{i+1},z_{i}u_{i+1}\\}:\
i=1,\dots,q-1\big{\\}}.$

We claim that $\mathcal{C}$ satisfies the conditions of Theorem 7 with $g=4$.
Indeed, any pair of edges is contained in at most one member of $\mathcal{C}$.
If we consider triples $F$ of edges instead, then $|F\cap C|\geq 2$ can hold
either for two members of $\mathcal{C}$ of the form $\delta(v)$, or a member
of $\mathcal{C}$ of the form $\delta(v)$ and another member of the form
$\\{w_{i}v_{i+1},z_{i}u_{i+1}\\}$. This follows from the facts that the
shortest cycle in $G$ has length $4$ and the end vertices of the edges
participating in the cuts $\\{w_{i}v_{i+1},z_{i}u_{i+1}\\}$ are at a distance
of at least two.

By Theorem 7, the number of colors in any rainbow circuit-free coloring of $M$
is at most

$\displaystyle|S|-|\mathcal{C}|{}$ $\displaystyle{}=[12\cdot
q+2\cdot(q-1)+2\cdot j]-[7\cdot q+j+q-1]$ $\displaystyle{}=6\cdot q+j-1$
$\displaystyle{}\leq\lceil\frac{6}{7}\cdot(7\cdot q+j-1)\rceil$
$\displaystyle{}=\lceil\frac{6}{7}\cdot r\rceil,$

where the last inequality holds by $1\leq j\leq 7$. This concludes the proof
of the corollary. ∎

###  4.3 Graphic matroids

Conjecture 17 was verified for the case of graphic matroids even when the
reduction is required to be rank-preserving and with $2\cdot k-1$ in place of
$2\cdot k$ [2, 9]. However, the characterization of the existence of a (not
necessarily rank-preserving) reduction that does not increase the covering
number of the matroid remains an intriguing open question.

As an easy case, consider a graph $G$ that can be partitioned into $k$
disjoint spanning trees. Let $M$ be the graphic matroid of $G$ and let $r$
denote its rank. Clearly, the covering number of $M$ is $k$. If $M$ has a
rainbow circuit-free coloring that uses each color at most $k$ times, then
every color class must have size exactly $k$. By Lemma 13, there exists an
ordering $S_{1},\dots,S_{r}$ of the color classes such that $S_{i}$ consists
of $k$ parallel edges in the graph obtained from $G$ by contracting the edges
in $S_{1}\cup\dots\cup S_{i-1}$. That is, the graph can be reduced to a single
vertex by a sequence of contractions of $k$ parallel edges. The reverse
direction also holds: if such a sequence of contractions exists for $G$, then
coloring the contracted sets by different colors we get a rainbow circuit-free
coloring of $M$.

The problem becomes significantly more difficult if the graph is not the
disjoint union of spanning trees. In the followings, we give partial results
for the case when the edge set can be decomposed into two forests. A graph
$G=(V,E)$ is $(2,3)$-sparse if $|E[X]|\leq 2\cdot|X|-3$ holds for $X\subseteq
V$, $|X|\geq 2$, and $(2,3)$-tight if, in addition, $|E|=2\cdot|V|-3$ holds.
Let $G_{0}=(V,E_{0})$ denote the complete graph on $V$. The edge sets of
$(2,3)$-sparse subgraphs of $G$ form the independent sets of a matroid on
$E_{0}$, the so-called rigidity matroid of $G_{0}$. The bases of the rigidity
matroid are the $(2,3)$-tight graphs on $V$, the so-called minimally rigid or
Laman graphs. Minimally rigid graphs are exactly the graphs that can be
obtained from $K_{2}$ (an edge) by the so-called Henneberg construction, that
is, by a sequence of the following operations: (H0) adding a new vertex $z$
and edges $uz$, $vz$ for already existing, distinct vertices $u,v$, and (H1)
deleting an already existing edge $uv$, and adding a new vertex $z$ and edges
$uz$, $vz$, $wz$ for already existing, distinct vertices $u,v,w$. [7, 11]

See 9

###### Proof.

Let $G=(V,E)$ be a simple graph such that its graphic matroid $M$ has a
rainbow circuit-free coloring using each color at most twice. Let $X\subseteq
V$ be a subset such that $|X|\geq 2$. As each rainbow colored set is
independent in $M$, at most $r_{M}(E[X])$ colors appear in $E[X]$, thus
$|E[X]|\leq 2\cdot r_{M}(E[X])\leq 2\cdot(|X|-1)=2\cdot|X|-2$. If
$|E[X]|=2\cdot|X|-2$ holds, then we get a rank-preserving rainbow circuit-free
coloring of the restriction $M|E[X]$ such that each color class has size
exactly two. As $M|E[X]$ is simple, this contradicts Corollary 3. Hence
$|E[X]|\leq 2\cdot|X|-3$, and the graph is $(2,3)$-sparse as stated. ∎

By Theorem 9, each simple graph $G=(V,E)$ whose graphic matroid has a rainbow
circuit-free coloring using each color at most twice has at most $2\cdot|V|-3$
edges. The next theorem characterizes simple graphs having such a coloring
with exactly $2\cdot|V|-3$ edges.

See 10

###### Proof.

It is clear that if a graph can be constructed from $K_{2}$ by (H0)
operations, then its graphic matroid has a rainbow circuit-free coloring using
each color at most twice. Indeed, if we apply a (H0) operation to a graph and
with a given rainbow circuit-free coloring and color the two new edges with
the same new color, then we get a rainbow circuit-free coloring of the graphic
matroid of the resulting graph.

To show the reverse direction, let $M$ be the graphic matroid of a simple
graph $G$ which has such a coloring, and let $r$ denote the rank of $M$. As
$|E|=2\cdot|V|-3\geq 2\cdot r-1$ and each color is used at most twice, the
coloring is rank-preserving. Therefore, by Theorem 4 and Lemma 13, there is an
ordering $S_{1},\dots,S_{r}$ of the color classes such that $S_{i}$ consists
of parallel elements of $M/(S_{1}\cup\dots\cup S_{i-1})$. As $M$ is simple,
$|S_{1}|=1$, hence $|S_{2}|=\dots=|S_{r}|=2$. We claim that there is a
labeling $v_{0},v_{1},\dots,v_{r}$ of $V$ such that $S_{1}\cup\dots\cup
S_{i}=E_{G}[\\{v_{0},\dots,v_{i}\\}]$ for $i=1,\dots,r$. Indeed, let
$S_{1}=\\{v_{0}v_{1}\\}$, and if we already defined $v_{0},v_{1},\dots,v_{i}$,
then $S_{i+1}$ consists of two parallel edges of the graph obtained from the
simple graph $G$ by the contraction of the vertices $\\{v_{0},\dots,v_{i}\\}$.
Hence the two edges of $S_{i}$ have a common vertex
$v_{i+1}\not\in\\{v_{0},\dots,v_{i}\\}$ and the other endpoint of these edges
are in $\\{v_{0},\dots,v_{i}\\}$. Therefore, $G$ can be constructed by (H0)
operations from the edge $v_{0}v_{1}$ such that the vertices are added in
order $v_{2},\dots,v_{r}$. ∎

As a consequence, we get that the converse of Theorem 9 does not hold as not
every minimally rigid graph can be constructed using only (H0) operations.

## Acknowledgements

Kristóf Bérczi was supported by the Lendület Programme of the Hungarian
Academy of Sciences – grant number LP2021-1/2021 and by the Hungarian National
Research, Development and Innovation Office – NKFIH, grant number FK128673.
“Application Domain Specific Highly Reliable IT Solutions” project has been
implemented with the support provided from the National Research, Development
and Innovation Fund of Hungary, financed under the Thematic Excellence
Programme TKP2020-NKA-06 (National Challenges Subprogramme) funding scheme.

## References

  * [1] R. Aharoni and E. Berger.  The intersection of a matroid and a simplicial complex.  Transactions of the American Mathematical Society, 358(11):4895–4917, 2006.
  * [2] K. Bérczi, T. Schwarcz, and Y. Yamaguchi.  List colouring of two matroids through reduction to partition matroids.  arXiv preprint arXiv:1911.10485, 2019.
  * [3] H. H. Crapo and G.-C. Rota.  Combinatorial Geometries.  MIT press Cambridge, Mass., 1968.
  * [4] A. Frank.  Connections in combinatorial optimization, volume 38.  OUP Oxford, 2011.
  * [5] F. Galvin.  The list chromatic index of a bipartite multigraph.  Journal of Combinatorial Theory, Series B, 63(1):153–158, 1995\.
  * [6] C. Greene and T. L. Magnanti.  Some abstract pivot algorithms.  SIAM Journal on Applied Mathematics, 29(3):530–539, 1975.
  * [7] L. Henneberg.  Die graphische Statik der starren Systeme.  Teubner, Leipzig, 1911.
  * [8] D. Hoffman, P. Horn, P. Johnson, and A. Owens.  On rainbow-cycle-forbidding edge colorings of finite graphs.  Graphs and Combinatorics, 35(6):1585–1596, 2019.
  * [9] S. Im, B. Moseley, and K. Pruhs.  The matroid intersection cover problem.  Operations Research Letters, 2020.
  * [10] J. P. Kung and H. Q. Nguyen.  Weak maps.  In N. White, G.-C. Rota, and N. M. White, editors, Theory of matroids. Cambridge University Press, Cambridge.
  * [11] G. Laman.  On graphs and rigidity of plane skeletal structures.  Journal of Engineering Mathematics, 4(4):331–340, 1970.
  * [12] J. Liu and H. Zhou.  Graphs and digraphs with given girth and connectivity.  Discrete Mathematics, 132(1-3):387–390, 1994.
  * [13] D. Lucas.  Properties of rank preserving weak maps.  Bulletin of the American Mathematical Society, 80(1):127–131, 1974\.
  * [14] D. Lucas.  Weak maps of combinatorial geometries.  Transactions of the American Mathematical Society, 206:247–279, 1975.
  * [15] C. S. J. Nash-Williams.  Decomposition of finite graphs into forests.  Journal of the London Mathematical Society, 1(1):12–12, 1964.
  * [16] H. Nishimura and S. Kuroda.  A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory.  Springer Science & Business Media, 2009.
  * [17] W. Tutte.  A homotopy theorem for matroids, I.  Transactions of the American Mathematical Society, 88(1):144–160, 1958.
  * [18] W. Tutte.  A homotopy theorem for matroids, II.  Transactions of the American Mathematical Society, 88(1):161–174, 1958.
  * [19] H. Whitney.  On the abstract properties of linear dependence.  In Hassler Whitney Collected Papers, pages 147–171. Springer, 1992\.