# On the Packing/Covering Conjecture of Infinite Matroids

Attila Joó  Attila Joó, University of Hamburg, Department of Mathematics,
Bundesstraße 55 (Geomatikum), 20146 Hamburg, Germany  attila.joo@uni-
hamburg.de Attila Joó, Alfréd Rényi Institute of Mathematics, Set theory and
general topology research division, 13-15 Reáltanoda St., Budapest, Hungary
<EMAIL_ADDRESS>
###### Abstract.

The Packing/Covering Conjecture was introduced by Bowler and Carmesin
motivated by the Matroid Partition Theorem by Edmonds and Fulkerson. A packing
for a family $(M_{i}:i\in\Theta)$ of matroids on the common edge set $E$ is a
system $(S_{i}:i\in\Theta)$ of pairwise disjoint subsets of $E$ where $S_{i}$
is panning in $M_{i}$. Similarly, a covering is a system $(I_{i}:i\in\Theta)$
with $\bigcup_{i\in\Theta}I_{i}=E$ where $I_{i}$ is independent in $M_{i}$.
The conjecture states that for every matroid family on $E$ there is a
partition $E=E_{p}\sqcup E_{c}$ such that $(M_{i}\upharpoonright
E_{p}:i\in\Theta)$ admits a packing and $(M_{i}.E_{c}:i\in\Theta)$ admits a
covering. We prove the special case where $E$ is countable and each $M_{i}$ is
either finitary or cofinitary. The connection between packing/covering and
matroid intersection problems discovered by Bowler and Carmesin can be
established for every well-behaved matroid class. This makes possible to
approach the problem from the direction of matroid intersection. We show that
the generalized version of Nash-Williams’ Matroid Intersection Conjecture
holds for countable matroids having only finitary and cofinitary components.

###### Key words and phrases:

infinite matroid, packing, covering, matroid intersection

###### 2020 Mathematics Subject Classification:

Primary: 05B35, 05B40

The author would like to thank the generous support of the Alexander von
Humboldt Foundation and NKFIH OTKA-129211

##  1\. Introduction

Rado asked in 1966 (see Problem P531 in [rado1966abstract]) if it is possible
to extend the concept of matroids to infinite without loosing duality and
minors. Based on the works of Higgs (see [higgs1969matroids]) and Oxley (see
[oxley1978infinite] and [oxley1992infinite]) Bruhn, Diestel, Kriesell,
Pendavingh and Wollan settled Rado’s problem affirmatively in
[bruhn2013axioms] by finding a set of cryptomorphic axioms for infinite
matroids, generalising the usual independent set-, bases-, circuit-, closure-
and rank-axioms for finite mastoids. Higgs named originally these structures
B-matroids to distinguish from the original concept. Later this terminology
vanished and in the context of infinite combinatorics B-matroids are referred
as matroids and the term ‘finite matroid’ is used to differentiate.

An $M=(E,\mathcal{I})$ is a matroid if $\mathcal{I}\subseteq\mathcal{P}(E)$
with

  1. (1)

$\varnothing\in\mathcal{I}$;

  2. (2)

$\mathcal{I}$ is downward closed;

  3. (3)

For every $I,J\in\mathcal{I}$ where $J$ is $\subseteq$-maximal in
$\mathcal{I}$ but $I$ is not, there exists an $e\in J\setminus I$ such that
$I+e\in\mathcal{I}$;

  4. (4)

For every $X\subseteq E$, any $I\in\mathcal{I}\cap\mathcal{P}(X)$ can be
extended to a $\subseteq$-maximal element of $\mathcal{I}\cap\mathcal{P}(X)$.

If $E$ is finite, then (4) is redundant and (1)-(3) is one of the usual
axiomatizations of finite matroids. One can show that every dependent set in
an infinite matroid contains a minimal dependent set which is called a
circuit. Before Rado’s program was settled, a more restrictive axiom was used
as a replacement of (4):

  1. (4’)

If all the finite subsets of an $X\subseteq E$ are in $\mathcal{I}$, then
$X\in\mathcal{I}$.

The implication (4’)$\Longrightarrow$(4) follows directly from Zorn’s lemma
thus axioms (1), (2), (3) and (4’) describe a subclass $\mathfrak{F}$ of the
the matroids. This $\mathfrak{F}$ consists of the matroids having only finite
circuits and called the class of _finitary_ matroids. Class $\mathfrak{F}$ is
closed under several important operations like direct sums and taking minors
but not under taking duals which was the main motivation of Rado’s program for
looking for a more general matroid concept. The class $\mathfrak{F}^{*}$ of
the duals of the matroids in $\mathfrak{F}$ consists of the _cofinitary_
matroids, i.e. matroid whose all cocircuits are finite. In order to being
closed under all matroid operations we need, we work with the class
$\mathfrak{F}\oplus\mathfrak{F}^{*}$ of matroids having only finitary and
cofinitary components, equivalently that are the direct sum of a finitary and
cofinitary matroid.

Matroid union is a fundamental concept in the theory of finite matroids. For a
finite family $(M_{i}:i\leq n)$ of matroids on a common finite edge set $E$
one can define a matroid $\bigvee_{i\leq n}M_{i}$ on $E$ by letting
$I\subseteq E$ be independent in $\bigvee_{i\leq n}M_{i}$ if $I=\bigcup_{i\leq
n}I_{i}$ for suitable $I_{i}\in\mathcal{I}_{M_{i}}$ (see
[edmonds1968matroid]). This phenomenon fails for infinite families of finitary
matroids. Indeed, let $E$ be uncountable and let $M_{i}$ be the $1$-uniform
matroid on $E$ for $i\in\mathbb{N}$. Then exactly the countable subsets of $E$
would be independent in $\bigvee_{i\in\mathbb{N}}M_{i}$ and hence there would
be no maximal independent set contradicting (4).111For a finite family of
finitary matroids the union operation results in a matroid (Proposition 4.1 in
[aigner2018intersection]). Even so, Bowler and Carmesin observed (see section
3 in [bowler2015matroid]) that the rank formula in the Matroid Partition
Theorem by Edmonds and Fulkerson (Theorem 13.3.1 in [frank2011connections]),
namely:

$r\left(\bigvee_{i\leq
n}M_{i}\right)=\max_{I_{i}\in\mathcal{I}_{M_{i}}}\left|\bigcup_{i\leq
n}I_{i}\right|=\min_{E=E_{p}\sqcup E_{c}}\left|E_{c}\right|+\sum_{i\leq
n}r_{M_{i}}(E_{p}),$

can be interpreted in infinite setting via the complementary slackness
conditions. In the minimax formula above there is equality for the family
$(I_{i}:i\leq n)$ and partition $E=E_{p}\sqcup E_{c}$ iff

  * •

$I_{i}$ is independent in $M_{i}$,

  * •

$\bigcup_{i\leq n}I_{i}\supseteq E_{c}$,

  * •

$I_{i}\cap E_{p}$ spans $E_{p}$ in $M_{i}$ for every $i$,

  * •

$I_{i}\cap I_{j}\cap E_{p}=\varnothing$ for $i\neq j$.

Bowler and Carmesin conjectured that for every family
$\mathcal{M}:=(M_{i}:i\in\Theta)$ of matroids on a common edge set $E$ there
is a family $(I_{i}:i\in\Theta)$ and partition $E=E_{p}\sqcup E_{c}$
satisfying the conditions above. To explain the name “Packing/Covering
Conjecture” let us provide an alternative formulation. A _packing_ for
$\mathcal{M}$ is a system $(S_{i}:i\in\Theta)$ of pairwise disjoint subsets of
$E$ where $S_{i}$ is spanning in $M_{i}$. Similarly, a _covering_ for
$\mathcal{M}$ is a system $(I_{i}:i\in\Theta)$ with
$\bigcup_{i\in\Theta}I_{i}=E$ where $I_{i}$ is independent in $M_{i}$.

######  Conjecture 1.1 (Packing/Covering, Conjecture 1.3 in
[bowler2015matroid] ).

For every family $(M_{i}:i\in\Theta)$ of matroids on a common edge set $E$
there is a partition $E=E_{p}\sqcup E_{c}$ in such a way that
$(M_{i}\upharpoonright E_{p}:i\in\Theta)$ admits a packing and
$(M_{i}.E_{c}:i\in\Theta)$ admits a covering.

We shall prove the following special case of the Pacing/Covering Conjecture
1.1:

######  Theorem 1.2.

For every family $(M_{i}:i\in\Theta)$ of matroids on a common countable edge
set $E$ where $M_{i}\in\mathfrak{F}\oplus\mathfrak{F}^{*}$, there is a
partition $E=E_{p}\sqcup E_{c}$ such that $(M_{i}\upharpoonright
E_{p}:i\in\Theta)$ admits a packing and $(M_{i}.E_{c}:i\in\Theta)$ admits a
covering.

It is worth to mention that packings and coverings have a crucial role in
other problems as well. For example if $(M_{i}:i\in\Theta)$ is as in Theorem
1.2 and admits both a packing and a covering, then there is a partition
$E=\bigsqcup_{i\in\Theta}B_{i}$ where $B_{i}$ is a base of $M_{i}$ (see
[erde2019base]). Maybe surprisingly, the failure of the analogous statement
for arbitrary matroids is consistent with set theory ZFC (Theorem 1.5 of
[erde2019base]) which might raise some scepticism about the provability of
Conjecture 1.1 for general matroids.

The Packing/Covering Conjecture 1.1 is closely related to the Matroid
Intersection Conjecture which has been one of the central open problems in the
theory of infinite matroids:

######  Conjecture 1.3 (Matroid Intersection Conjecture by Nash-Williams,
[aharoni1998intersection]).

If $M$ and $N$ are finitary matroids on the same edge set $E$, then they admit
a common independent set $I$ for which there is a partition $E=E_{M}\sqcup
E_{N}$ such that $I_{M}:=I\cap E_{M}$ spans $E_{M}$ in $M$ and $I_{N}:=I\cap
E_{N}$ spans $E_{N}$ in $N$.

Aharoni proved in [aharoni1984konig] based on his earlier works with Nash-
Williams and Shelah (see [aharoni1983general] and [aharoni1984another]) that
the special case of Conjecture 1.3 where $M$ and $N$ are partition matroids
holds. The conjecture is also known to be true if we assume that $E$ is
countable but $M$ and $N$ can be otherwise arbitrary (see [joo2020MIC]). Let
us call Generalized Matroid Intersection Conjecture what we obtain from 1.3 by
extending it to arbitrary matroids (i.e. omitting the word “finitary”).
Several partial results has been obtained for this generalization but only for
well-behaved matroid classes. The positive answer is known for example if: $M$
is finitary and $N$ is cofinatory [aigner2018intersection] or both matroids
are singular222A matroid is singular if it is the direct sum of $1$-uniform
matroids and duals of $1$-uniform matroids. and countable [ghaderi2017] or $M$
is arbitrary and $N$ is the direct sum of finitely many uniform matroids
[joó2020intersection].

Bowler and Carmesin showed that their Pacing/Covering Conjecture 1.1 and the
Generalized Matroid Intersection Conjecture are equivalent and they also found
an important reduction for both (see Corollary 3.9 in [bowler2015matroid]). By
analysing their proof it is clear that the equivalence can be established if
we restrict both conjectures to a class of matroids closed under certain
operations. It allows us to prove Theorem 1.4 by showing the following
instance of the Generalized Matroid Intersection Conjecture which itself is a
common extension of the singular case by Ghaderi [ghaderi2017] and our
previous work [joo2020MIC]:

######  Theorem 1.4.

If $M$ and $N$ are matroids in $\mathfrak{F}\oplus\mathfrak{F}^{*}$ on the
same countable edge set $E$, then they admit a common independent set $I$ for
which there is a partition $E=E_{M}\sqcup E_{N}$ such that $I_{M}:=I\cap
E_{M}$ spans $E_{M}$ in $M$ and $I_{N}:=I\cap E_{N}$ spans $E_{N}$ in $N$.

The paper is organized as follows. In the following section we introduce some
notation and fundamental facts about matroids that are mostly well-know for
finite ones. In Section 3 we collect some previous results and relatively easy
technical lemmas in order be able the discuss later the proof of the main
results without any distraction. Then in Section 4 we reduce the main results
to a key-lemma. After these preparations the actual proof begins with Section
5 by developing and analysing an ‘augmenting path’ type of technique. Our main
principle from this point is to handle the finitary and the cofinitary parts
of matroid $N$ differently in order to exploit the advantage of the finiteness
of the circuits and cocircuits respectively. Equipped with these “mixed”
augmenting paths we discuss the proof of our key-lemma in Section 6. Finally,
we introduce an application in Section 7 about orientations of a graph with
in-degree requirements.

##  2\. Notation and basic facts

In this section we introduce the notation and recall some basic facts about
matroids that we will use later without further explanation. For more details
we refer to [nathanhabil].

An enumeration of a countable set $X$ is an $\mathbb{N}\rightarrow X$
surjection that we write as $\\{x_{n}:n\in\mathbb{N}\\}$. We denote the
symmetric difference $(X\setminus Y)\cup(Y\setminus X)$ of $X$ and $Y$ by
$\boldsymbol{X\vartriangle Y}$. A pair ${M=(E,\mathcal{I})}$ is a _matroid_ if
${\mathcal{I}\subseteq\mathcal{P}(E)}$ satisfies the axioms (1)-(4). The sets
in $\mathcal{I}$ are called _independent_ while the sets in
${\mathcal{P}(E)\setminus\mathcal{I}}$ are _dependent_. An $e\in E$ is a
_loop_ if $\\{e\\}$ is dependent. If $E$ is finite, then (1)-(3) is one of the
the usual axiomization of matroids in terms of independent sets (while (4) is
redundant). The maximal independent sets are called _bases_. If $M$ admits a
finite base, then all the bases have the same size which is the rank
$\boldsymbol{r(M)}$ of $M$ otherwise we let $r(M):=\infty$.333It is
independent of ZFC that the bases of a fixed matroid have the same size (see
[higgs1969equicardinality] and [bowler2016self]). The minimal dependent sets
are called _circuits_. Every dependent set contains a circuit. The
_components_ of a matroid are the components of the hypergraph of its
circuits. The _dual_ of a matroid ${M}$ is the matroid ${M^{*}}$ with
$E(M^{*})=E(M)$ whose bases are the complements of the bases of $M$. For an
${X\subseteq E}$, ${\boldsymbol{M\upharpoonright
X}:=(X,\mathcal{I}\cap\mathcal{P}(X))}$ is a matroid and it is called the
_restriction_ of $M$ to $X$. We write ${\boldsymbol{M-X}}$ for
$M\upharpoonright(E\setminus X)$ and call it the minor obtained by the
_deletion_ of $X$. The _contraction_ of $X$ in $M$ and the contraction of $M$
onto $X$ are ${\boldsymbol{M/X}:=(M^{*}-X)^{*}}$ and
$\boldsymbol{M.X}:=M/(E\setminus X)$ respectively. Contraction and deletion
commute, i.e., for disjoint $X,Y\subseteq E$, we have $(M/X)-Y=(M-Y)/X$.
Matroids of this form are the _minors_ of $M$. The independence of an
$I\subseteq X$ in $M.X$ is equivalent with
$I\subseteq\mathsf{span}_{M^{*}}(X\setminus I)$. If $I$ is independent in $M$
but $I+e$ is dependent for some $e\in E\setminus I$ then there is a unique
circuit $\boldsymbol{C_{M}(e,I)}$ of $M$ through $e$ contained in $I+e$. We
say ${X\subseteq E}$ _spans_ ${e\in E}$ in matroid $M$ if either ${e\in X}$ or
there exists a circuit ${C\ni e}$ with ${C-e\subseteq X}$. By letting
$\boldsymbol{\mathsf{span}_{M}(X)}$ be the set of edges spanned by $X$ in $M$,
we obtain a closure operation
$\mathsf{span}_{M}:\mathcal{P}(E)\rightarrow\mathcal{P}(E)$. An ${S\subseteq
E}$ is _spanning_ in $M$ if ${\mathsf{span}_{M}(S)=E}$. An $S\subseteq X$
spans $X$ in $M.X$ iff $X\setminus S$ is independent in $M^{*}$. If
$M_{i}=(E_{i},\mathcal{I}_{i})$ is a matroid for $i\in\Theta$ and the sets
$E_{i}$ are pairwise disjoint, then their direct sum is
$\boldsymbol{\bigoplus_{i\in\Theta}M_{i}}=(E,\mathcal{I})$ where
$E=\bigsqcup_{i\in\Theta}E_{i}$ and
$\mathcal{I}=\\{\bigsqcup_{i\in\Theta}I_{i}:I_{i}\in\mathcal{I}_{i}\\}$. For a
class $\mathfrak{C}$ of matroids $\boldsymbol{\mathfrak{C}(E)}$ denotes the
subclass $\\{M\in\mathfrak{C}:E(M)=E\\}$. A matroid is called uniform if for
ever base $B$ and every edges $e\in B$ and $f\in E\setminus B$ the set $B-e+f$
is also a base. Let $\boldsymbol{U_{E,n}}$ be the $n$-uniform matroid on $E$,
formally $U_{E,n}:=(E,[E]^{\leq n})$.

We need some further more subject-specific definitions. From now on let $M$
and $N$ be matroids on a common edge set $E$. We call a $W\subseteq E$ an
$(M,N)$-_wave_ if $M\upharpoonright W$ admits an $N.W$-independent base. Waves
in the matroidal context were introduced by Aharoni and Ziv in
[aharoni1998intersection] but it was also an important tool in the proof of
the infinite version of Menger’s theorem [aharoni2009menger] by Aharoni and
Berger. We write $\boldsymbol{\mathsf{cond}(M,N)}$ for the condition: ‘For
every $(M,N)$-wave $W$ there is an $M$-independent base of $N.W$.’ A set
$I\in\mathcal{I}_{M}\cap\mathcal{I}_{N}$ is _feasible_ if
$\mathsf{cond}(M/I,N/I)$ holds. It is known (see Proposition 3.5) that there
exists a $\subseteq$-largest $(M,N)$-wave which we denote by
$\boldsymbol{W(M,N)}$. Let $\boldsymbol{\mathsf{cond}^{+}(M,N)}$ be the
statement that $W(M,N)$ consists of $M$-loops and ${r(N.W(M,N))=0}$. As the
notation indicates it is a strengthening of $\mathsf{cond}(M,N)$. Indeed,
under the assumption $\mathsf{cond}^{+}(M,N)$, $\varnothing$ is an
$M$-independent base of $N.W$ for every wave $W$. A feasible $I$ is called
_nice_ if $\mathsf{cond}^{+}(M/I,N/I)$ holds. For $X\subseteq E$ let
$\boldsymbol{B(M,N,X)}$ be the (possibly empty) set of common bases of
$M\upharpoonright X$ and $N.X$.

##  3\. Preliminary lemmas and preparation

We collect those necessary lemmas in this section that are either known from
previous papers or follow more or less directly from definitions.

###  3.1. Classical results

The following two statements were proved by Edmonds’ in
[edmonds2003submodular]:

######  Proposition 3.1.

Assume that $I$ is independent,
${e_{1},\dots,e_{m}\in\mathsf{span}(I)\setminus I}$ and ${f_{1},\dots,f_{m}\in
I}$ with ${f_{j}\in C(e_{j},I)}$ but ${f_{j}\notin C(e_{k},I)}$ for ${k<j}$.
Then

${\left(I\cup\\{e_{1},\dots,e_{m}\\}\right)\setminus\\{f_{1},\dots,f_{m}\\}}$

is independent and spans the same set as $I$.

###### Proof.

We use induction on $m$. The case ${m=0}$ is trivial. Suppose that ${m>0}$. On
the one hand, the set ${I-f_{m}+e_{m}}$ is independent and spans the same set
as $I$. On the other hand, ${C(e_{j},I-f_{m}+e_{m})=C(e_{j},I)}$ for ${j<m}$
because ${f_{m}\notin C(e_{j},I)}$ for ${j<m}$. Hence by using the induction
hypothesis for ${I-f_{m}+e_{m}}$ and
${e_{1},\dots,e_{m-1},f_{1},\dots,f_{m-1}}$ we are done. ∎

######  Lemma 3.2 (Edmonds’ augmenting path method).

For $I\in\mathcal{I}_{M}\cap\mathcal{I}_{N}$, exactly one of the following
statements holds:

  1. (1)

There is a partition $E=E_{M}\sqcup E_{N}$ such that $I_{M}:=I\cap E_{M}$
spans $E_{M}$ in $M$ and $I_{N}:=I\cap E_{N}$ spans $E_{N}$ in $N$.

  2. (2)

There is a $P=\\{x_{1},\dots,x_{2n+1}\\}\subseteq E$ with
$x_{1}\notin\mathsf{span}_{N}(I)$ and $x_{2n+1}\notin\mathsf{span}_{M}(I)$
such that $I\vartriangle P\in\mathcal{I}_{M}\cap\mathcal{I}_{N}$ with
$\mathsf{span}_{M}(I\vartriangle P)=\mathsf{span}_{M}(I+x_{2n+1})$ and
$\mathsf{span}_{N}(I\vartriangle P)=\mathsf{span}_{M}(I+x_{1})$.

We will develop in Section 5 a “mixed” augmenting path method which operates
differently on the finitary and on the cofinitary part of an
$N\in(\mathfrak{F}\oplus\mathfrak{F}^{*})(E)$. The phrase ‘augmenting path’
refers always to our mixed method except in the proof of Lemma 3.14. Note that
$E_{M}$ is an $(M,N)$-wave witnessed by $I_{M}$ and $E_{N}$ is an $(N,M)$-wave
witnessed by $I_{N}$.

One can define matroids in the language of circuits (see [bruhn2013axioms]).
The following claim is one of the axioms in that case.

######  Claim 3.3 (Circuit elimination axiom).

Assume that $C\ni e$ is a circuit and $\\{C_{x}:x\in X\\}$ is a family of
circuits where $X\subseteq C-e$ and $C_{x}$ is a circuit with $C\cap
X=\\{x\\}$ avoiding $e$. Then there is a circuit through $e$ contained in

$\left(C\cup\bigcup_{x\in X}C_{x}\right)\setminus X=:Y$

###### Proof.

Since $C_{x}-x$ spans $x$ we have $C-e\subseteq\mathsf{span}(Y-e)$ and
therefore $e\in\mathsf{span}(\mathsf{span}(Y-e))$. But then
$e\in\mathsf{span}(Y-e)$ because $\mathsf{span}$ is a closure operator. ∎

For finite matroids the axiom above is demanded only in the special case where
$X$ is a singleton (known as “Strong circuit elimination“) from which the case
of arbitrary $X$ can be derived by repeated application.

######  Corollary 3.4.

Let $I$ be an independent and suppose that there is a circuit
$C\subseteq\mathsf{span}(I)$ with $e\in I\cap C$. Then there is an $f\in
C\setminus I$ with $e\in C(f,I)$.

###### Proof.

For every $x\in C\setminus I$ we pick a circuit $C_{x}$ with $C_{x}\setminus
I=\\{x\\}$. If $e\in C_{x}$ for some $x$, then $f:=x$ is as desired. Suppose
for a contradiction that there is no such an $x$. Then by Circuit elimination
(Claim 3.3) we obtain a circuit through $e$ which is contained entirely in $I$
contradicting the independence of $I$. ∎

The following statement was shown by Aharoni and Ziv in
[aharoni1998intersection] using a slightly different terminology.

######  Proposition 3.5.

The union of arbitrary many waves is a wave.

###### Proof.

Suppose that $W_{\beta}$ is a wave for $\beta<\kappa$ and let
$W_{<\alpha}:=\bigcup_{\beta<\alpha}W_{\beta}$ for $\alpha\leq\kappa$. We fix
a base $B_{\beta}\subseteq W_{\beta}$ of $M\upharpoonright W_{\beta}$ which is
independent in $N.W_{\beta}$. Let us define $B_{<\alpha}$ by transfinite
recursion for $\alpha\leq\kappa$ as follows.

$B_{<\alpha}:=\begin{cases}\varnothing&\mbox{if }\alpha=0\\\
B_{<\beta}\cup(B_{\beta}\setminus W_{<\beta})&\mbox{if }\alpha=\beta+1\\\
\bigcup_{\beta<\alpha}B_{<\beta}&\mbox{if }\alpha\text{ is limit
ordinal}.\end{cases}$

First we show by transfinite induction that $B_{<\alpha}$ is spanning in
$M\upharpoonright W_{<\alpha}$. For $\alpha=0$ it is trivial. For a limit
$\alpha$ it follows directly from the induction hypothesis. If
$\alpha=\beta+1$, then by the choice of $B_{\beta}$, the set
$B_{\beta}\setminus W_{<\beta}$ spans $W_{\beta}\setminus W_{<\beta}$ in
$M/W_{<\beta}$. Since $W_{<\beta}$ is spanned by $B_{<\beta}$ in $M$ by
induction, it follows that $W_{<\beta+1}$ is spanned by $B_{<\beta+1}$ in $M$.

The independence of $B_{<\alpha}$ in $N.W_{<\alpha}$ can be reformulated as
“$W_{<\alpha}\setminus B_{<\alpha}$ is spanning in $N^{*}\upharpoonright
W_{<\alpha}$”, which can be proved the same way as above. ∎

###  3.2. Some more recent results and basic facts

######  Theorem 3.6 (Aigner-Horev, Carmesin and Frölich; Theorem 1.5 in
[aigner2018intersection]).

If $M\in\mathfrak{F}(E)$ and $N\in\mathfrak{F}^{*}(E)$, then there is an
$I\in\mathcal{I}_{M}\cap\mathcal{I}_{N}$ and a partition $E=E_{M}\sqcup E_{N}$
such that $I_{M}:=I\cap E_{M}$ spans $E_{M}$ in $M$ and $I_{N}:=I\cap E_{N}$
spans $E_{N}$ in $N$.

######  Corollary 3.7.

If $M\in\mathfrak{F}(E)$ and $N\in\mathfrak{F}^{*}(E)$ satisfy
$\mathsf{cond}^{+}(M,N)$, then there is an $M$-independent $N$-base.

###### Proof.

Let $E_{M},E_{N},I_{M}$ and $I_{N}$ be as in Theorem 3.6. Then $E_{M}$ is a
wave witnessed by $I_{M}$ thus by $\mathsf{cond}^{+}(M,N)$ we know that
$E_{M}$ consists of $M$-loops and $r(N.E_{M})=0$. But then $I_{M}=\varnothing$
and $I_{N}$ is a base of $N$ which is independent in $M$. ∎

######  Observation 3.8.

If $\mathsf{cond}(M,N)$ holds and $L$ is a set of the $M$-loops, then
$r(N.L)=0$ which means $L\subseteq\mathsf{span}_{N}(E\setminus L)$.

######  Corollary 3.9.

If $I$ is feasible, then $r(N.(\mathsf{span}_{M}(I)\setminus I)=0$.

######  Observation 3.10.

If $W_{0}$ is an $(M,N)$-wave and $W_{1}$ is an $(M/W_{0},N-W_{0})$-wave, then
$W_{0}\cup W_{1}$ is an $(M,N)$-wave.

######  Corollary 3.11.

For $W:=W(M,N)$, the largest $(M/W,N-W)$-wave is $\varnothing$. In particular,
$\mathsf{cond}^{+}(M/W,N-W)$ holds.

######  Observation 3.12.

$\mathsf{cond}^{+}(M,N)$ implies ${\mathsf{cond}^{+}(M\upharpoonright X,N.X)}$
for every $X\subseteq E$.

######  Proposition 3.13.

If $I_{0}\in\mathcal{I}_{N}\cap\mathcal{I}_{M}$ and $I_{1}$ is feasible with
respect to $(M/I_{0},N/I_{0})$, then $I_{0}\cup I_{1}$ is feasible with
respect to $(M,N)$. If in addition $I_{1}$ is a nice feasible in regards to
$(M/I_{0},N/I_{0})$, then so is $I_{0}\cup I_{1}$ to $(M,N)$.

###### Proof.

By definition the feasibility of $I_{1}$ w.r.t. $(M/I_{0},N/I_{0})$ means that
the condition $\mathsf{cond}(M/(I_{0}\cup I_{1}),N/(I_{0}\cup I_{1}))$ holds.
The feasibility of $I_{0}\cup I_{1}$ w.r.t. $(M,N)$ means the same also by
definition. For ‘nice feasible’ the argument is similar, only $\mathsf{cond}$
must be replaced by $\mathsf{cond}^{+}$. ∎

The following lemma was introduced in [joo2020MIC].

######  Lemma 3.14.

Condition $\mathsf{cond}^{+}(M,N)$ implies that whenever $W$ is an
$(M/e,N/e)$-wave for some $e\in E$ witnessed by $B\subseteq W$, then $B\in
B(M/e,N/e,W)$, i.e. $B$ is spanning in $N.W$.

###### Proof.

Let $W$ be an $(M/e,N/e)$-wave. Note that $(N/e).W=N.W$ by definition. Pick a
$B\subseteq W$ which is an $N.W$-independent base of $(M/e)\upharpoonright W$.
We may assume that $e\in\mathsf{span}_{M}(W)$ and $e$ is not an $M$-loop.
Indeed, otherwise $(M/e)\upharpoonright W=M\upharpoonright W$ holds and hence
$W$ is also an $(M,N)$-wave. Thus by $\mathsf{cond}^{+}(M,N)$ we may conclude
that $W$ consists of $M$-loops and hence $B=\varnothing$, moreover, $r(N.W)=0$
and therefore $\varnothing$ is a base of $N.W$.

Then $B$ is not a base of $M\upharpoonright W$ but “almost”, namely
$r(M/B\upharpoonright W)=1$. We apply the augmenting path Lemma 3.2 by Edmonds
with $B$ in regards to $M\upharpoonright W$ and $N.W$. An augmenting path $P$
cannot exist. Indeed, if $P$ were an augmenting path then $B\vartriangle P$
would show that $W$ is an $(M,N)$-wave which does not consist of $M$-loops,
contradiction. Thus we get a partition $W=W_{0}\sqcup W_{1}$ instead where
$W_{0}$ is an $(M\upharpoonright W,N.W)$-wave witnessed by $B\cap W_{0}$, and
therefore also an $(M,N)$-wave, and $W_{1}$ is an $(N.W,M\upharpoonright
W)$-wave showed by $B\cap W_{1}$. Then $W_{0}$ must consist of $M$-loops by
$\mathsf{cond}^{+}(M,N)$ and therefore $B\subseteq W_{1}$ by the
$M$-independence of $B$. We need to show that $B$ is spanning not just in
$N.W_{1}$ but also in $N.W$. To do so let $B^{\prime}$ be a base of $N-W$.
Then $B\cup B^{\prime}$ spans $E\setminus W_{0}$ in $N$ because $B=B\cap
W_{1}$ is a base $N.W_{1}$. But then $B\cup B^{\prime}$ is spanning in $N$
because $r(N.W_{0})=0$ by Observation 3.8. We conclude that $B$ is spanning in
$N.W$ as desired. ∎

###  3.3. Technical lemmas in regards to $\boldsymbol{B(M,N,W)}$

######  Proposition 3.15.

For $W:=W(M,N)$, the elements of $B(M,N,W)$ are nice feasible sets.

###### Proof.

Let $B\in B(M,N,W)$. Clearly $B\in\mathcal{I}_{M}\cap\mathcal{I}_{N}$ because
$B\in\mathcal{I}_{M}\cap\mathcal{I}_{N.W}$ by definition and
$\mathcal{I}_{N.W}\subseteq\mathcal{I}_{N}$. We know that $W\setminus B$ is an
$(M/B,N/B)$-wave consisting of $M/B$ loops and $r(N.(W\setminus B))=0$ because
$B$ is a base of $N.W$. In order to show $\mathsf{cond}^{+}(M/B,N/B)$, it is
enough to prove that $W\setminus B$ is actually $W(M/B,N/B)=:W^{\prime}$.
Suppose for a contradiction that $W^{\prime}\supsetneq W\setminus B$. Let
$B^{\prime}$ be an $N.W^{\prime}$-independent base of $M/B\upharpoonright
W^{\prime}$. Note that $B\cup B^{\prime}$ is a base of $M\upharpoonright(W\cup
W^{\prime})$ and $B^{\prime}\cap(W\setminus B)=\varnothing$. Since $B$ is
$N^{*}$-spanned by $W\setminus B\subseteq(W\cup W^{\prime})\setminus(B\cup
B^{\prime})$ and $B^{\prime}$ is $N^{*}$-spanned by $W^{\prime}\setminus
B^{\prime}\subseteq(W\cup W^{\prime})\setminus(B\cup B^{\prime})$, we may
conclude that $B\cup B^{\prime}$ is independent in $N.(W\cup W^{\prime})$.
Thus $W\cup W^{\prime}$ is an $(M,N)$-wave witnessed by $B\cup B^{\prime}$
which contradicts the maximality of $W$. ∎

######  Corollary 3.16.

Assume that $I\in\mathcal{I}_{M}\cap\mathcal{I}_{M}$ and $B\in B(M/I,N/I,W)$
where $W:=W(M/I,N/I)$. Then $I\cup B$ is a nice feasible set.

###### Proof.

Combine Propositions 3.13 and 3.15. ∎

######  Observation 3.17.

If $\mathsf{cond}^{+}(M,N)$ holds and $L$ is a set of $M$-loops, then
$\mathsf{cond}^{+}(M-L,N-L)$ also holds.

######  Observation 3.18.

Let $W$ be a wave and let $L$ be a set of common loops of $M$ and $N$. Then
$W\setminus L$ is also a wave and $B(M,N,W)=B(M,N,W\setminus L)$.

######  Lemma 3.19.

Let $W$ be a wave and $L\subseteq W$ such that $L$ consists of $M$-loops with
$r(N.L)=0$. Then $W\setminus L$ is an $(M-L,N-L,W\setminus L)$-wave with

$B(M,N,W)=B(M-L,N-L,W\setminus L).$

###### Proof.

A set $B$ is a base of $M\upharpoonright W$ iff it is a base of
$M\upharpoonright(W\setminus L)$ because $L$ consists of $M$-loops. A
$B\subseteq W\setminus L$ is $N.W$-independent iff
$B\subseteq\mathsf{span}_{N^{*}}(W\setminus B)$. This holds if and only if
$B\subseteq\mathsf{span}_{N^{*}/L}(W\setminus(B\cup L))$ i.e. $B$ is
independent in $(N-L).(W\setminus L)$. Note that $r(N.L)=0$ is equivalent with
the $N^{*}$-independence of $L$. Thus for $B\subseteq W\setminus L$,
$W\setminus B$ is $N^{*}$-independent iff $W\setminus(B\cup L)$ is
$N^{*}/L$-independent. It means that $B$ is spanning in $N.W$ iff it is
spanning in $(N-L).(W\setminus L)$.

Thus the sets that are witnessing that $W\setminus L$ is an
$(M-L,N-L,W\setminus L)$-wave are exactly those that are witnessing that $W$
is an $(M,N)$-wave, moreover, $B(M,N,W)=B(M-L,N-L,W\setminus L)$ holds.

∎

######  Lemma 3.20.

Assume that $X_{j},Y_{j}\subseteq E$ for $j\in\\{0,1\\}$ where $X_{j}\sqcup
Y_{j}=Z$ for $j\in\\{0,1\\}$, furthermore
$\mathsf{span}_{M}(X_{0})=\mathsf{span}_{M}(X_{1})$ and
$\mathsf{span}_{N^{*}}(Y_{0})=\mathsf{span}_{N^{*}}(Y_{1})$. Then for every
$X\subseteq E\setminus Z$ we have

$B(M/X_{0}-Y_{0},N/X_{0}-Y_{0},X)=B(M/X_{1}-Y_{1},N/X_{1}-Y_{1},X).$

###### Proof.

The matroids $M/X_{0}-Y_{0}$ and $M/X_{1}-Y_{1}$ are the same as well as the
matroids $N/X_{0}-Y_{0}$ and $N/X_{1}-Y_{1}$. ∎

##  4\. Reductions

We repeat here our main results for convenience: See 1.2

See 1.4

###  4.1. Matroid Intersection with a finitary $\boldsymbol{M}$

As we mentioned, the method by Bowler and Carmesin used to prove Corollary 3.9
in [bowler2015matroid] works not only for the class of all matroids but can be
adapted for every class closed under certain operations. We apply their
technique to obtain the following reduction:

######  Lemma 4.1.

Theorems 1.2 and 1.4 are implied by the special case of Theorem 1.4 where
$M\in\mathfrak{F}$.

###### Proof.

First we show that one can assume without loss of generality in the proof of
Theorem 1.2 that $\Theta$ is countable. To do so let

$E^{\prime}:=\\{e\in
E:\left|\\{i\in\Theta:\\{e\\}\in\mathcal{I}_{M_{i}}\\}\right|\leq\aleph_{0}\\}$

and

$\Theta^{\prime}:=\\{i\in\Theta:(\exists e\in
E^{\prime})(\\{e\\}\in\mathcal{I}_{M_{i}})\\}.$

We apply Theorem 1.2 with $E^{\prime}$ and with the countable family
$(M_{i}\upharpoonright E^{\prime}:i\in\Theta^{\prime})$. Then we obtain a
partition $E^{\prime}=E^{\prime}_{p}\sqcup E^{\prime}_{c}$ such that
$(M_{i}\upharpoonright E^{\prime}_{p}:i\in\Theta^{\prime})$ admits a packing
$(S_{i}:i\in\Theta^{\prime})$ and $(M_{i}\upharpoonright
E^{\prime}.E_{c}:i\in\Theta^{\prime})$ admits a covering
$(I_{i}:i\in\Theta^{\prime})$. Let $E_{p}:=E^{\prime}_{p}$ and
$E_{c}:=E\setminus E_{p}=E^{\prime}_{c}\cup(E\setminus E^{\prime})$. By
construction $r_{M_{i}}(E^{\prime})=0$ for
$i\in\Theta\setminus\Theta^{\prime}$. Thus by letting $S_{i}:=\varnothing$ for
$i\in\Theta\setminus\Theta^{\prime}$ the family $(S_{i}:i\in\Theta)$ is a
packing w.r.t. $(M_{i}\upharpoonright E_{p}:i\in\Theta)$. Let $g:E\setminus
E^{\prime}\rightarrow\Theta\setminus\Theta^{\prime}$ be injective. For
$i\in\Theta\setminus\Theta^{\prime}$, we take $I_{i}:=\\{g^{-1}(i)\\}$ if
$i\in\mathsf{ran}(g)$ and $I_{i}:=\varnothing$ otherwise. Then
$(I_{i}:i\in\Theta)$ is a covering for $(M_{i}.E_{c}:i\in\Theta)$ and we are
done.

We proceed with the proof of Theorem 1.2 assuming that $\Theta$ is countable.
For $i\in\Theta$, let $M^{\prime}_{i}$ be the matroid on $E\times\\{i\\}$ that
we obtain by “copying” $M_{i}$ via the bijection $e\mapsto(e,i)$. Then for

$M:=\bigoplus_{i\in\Theta}M_{i}^{\prime},\ \text{ and }N:=\bigoplus_{e\in
E}U_{\\{e\\}\times\Theta,1}$

we have $M\in(\mathfrak{F}\oplus\mathfrak{F}^{*})(E\times\Theta)$ and
$N\in\mathfrak{F}(E\times\Theta)$ where $E\times\Theta$ is countable. Thus by
assumption there is a partition $E\times\Theta=E_{M}\sqcup E_{N}$ and an
$I\in\mathcal{I}_{M}\cap\mathcal{I}_{N}$ such that $I_{M}:=I\cap E_{M}$ spans
$E_{M}$ in $M$ and $I_{N}:=I\cap E_{N}$ spans $E_{N}$ in $N$. The
$M$-independence of $I$ ensures that $J_{i}:=\\{e\in E:(e,i)\in I\\}$ is
$M_{i}$-independent. The $N$-independence of $I$ guarantees that the sets
$J_{i}$ are pairwise disjoint. Let $E_{c}:=\\{e\in E:(\exists
i\in\Theta)(e,i)\in E_{N}\\}$. Then for each $e\in E_{c}$ there must be some
$i\in\Theta$ with $(e,i)\in I_{N}$ because
$E_{N}\subseteq\mathsf{span}_{N}(I_{N})$. Thus the sets $J_{i}$ cover $E_{c}$
and so do the sets $I_{i}:=J_{i}\cap E_{c}$. It is enough to show that
$S_{i}:=J_{i}\setminus I_{i}$ spans $E_{p}:=E\setminus E_{c}$ in $M_{i}$ for
every $i\in\Theta$. Let $f\in E_{p}$ and $i\in\Theta$ be given. Then
$\\{f\\}\times\Theta\subseteq E_{M}$ follows directly from the definition of
$E_{p}$, in particular $(f,i)\in E_{M}$. We know that
$(f,i)\in\mathsf{span}_{M}(I_{M})$ and hence
$f\in\mathsf{span}_{M_{i}}(\\{e\in E:(e,i)\in I_{M}\\})$. Suppose for a
contradiction that $h\in E_{c}\cap\\{e\in E:(e,i)\in I_{M}\\}$. Then for some
$j\in\Theta$ we have $(h,j)\in E_{N}$. Since
$(h,j)\in\mathsf{span}_{N}(I_{N})$, we have $(h,k)\in I_{N}$ for some
$k\in\Theta$. But then $(h,i),(h,k)\in I$ are distinct elements thus $i\neq k$
which contradict the $N$-independence of $I$. Therefore $E_{c}\cap\\{e\in
E:(e,i)\in I_{M}\\}=\varnothing$. Since $\\{e\in E:(e,i)\in I_{M}\\}\subseteq
J_{i}$ by the definition of $J_{i}$ we conclude $\\{e\in E:(e,i)\in
I_{M}\\}=S_{i}$. Therefore $(S_{i}:i\in\Theta)$ is a packing for
$(M_{i}\upharpoonright E_{p}:i\in\Theta)$ and $(I_{i}:i\in\Theta)$ is a
covering for $(M_{i}.E_{c}:i\in\Theta)$ as desired.

Now we derive Theorem 1.4 from Theorem 1.2. To do so, we take a partition
$E=E_{p}\sqcup E_{c}$ such that $(S_{M},S_{N})$ is a packing for
$(M\upharpoonright E_{p},N^{*}\upharpoonright E_{p})$ and $(R_{M},R_{N})$ is a
covering for $(M.E_{c},N^{*}.E_{c})$. Let $I_{M}\subseteq S_{M}$ be a base of
$M\upharpoonright E_{p}$ and we define $I_{N}:=R_{M}$. By construction
$E_{p}\subseteq\mathsf{span}_{M}(I_{M})$ and $I_{N}\in\mathcal{I}_{M.E_{c}}$.
We also know that

$I_{M}\subseteq\mathsf{span}_{N^{*}}(S_{N})\subseteq\mathsf{span}_{N^{*}}(E_{p}\setminus
I_{M})$

which means $I_{M}\in\mathcal{I}_{N.E_{p}}$. Finally,
$R_{N}\in\mathcal{I}_{N^{*}.E_{c}}$ means that $E_{c}\setminus R_{N}$ spans
$E_{c}$ in $N$ and therefore so does $I_{N}=R_{M}\supseteq E_{c}\setminus
R_{N}$. ∎

###  4.2. Finding an $\boldsymbol{M}$-independent base of $\boldsymbol{N}$

The following reformulation of the matroid intersection problem was introduced
by Aharoni and Ziv in [aharoni1998intersection] but its analogue by Aharoni
was already an important tool to attack (and eventually solve in
[aharoni2009menger]) the Erdős-Menger Conjecture.

######  Claim 4.2.

Assume that $M\in\mathfrak{F}(E)$ and
$N\in(\mathfrak{F}\oplus\mathfrak{F}^{*})(E)$ such that $E$ is countable and
$\mathsf{cond}^{+}(M,N)$ holds. Then there is an $M$-independent base of $N$.

######  Lemma 4.3.

Claim 4.2 implies our main results Theorems 1.2 and 1.4.

###### Proof.

By Lemma 4.1 it is enough to show that the special case of Theorem 1.4 where
$M\in\mathfrak{F}$ follows from Claim 4.2. To do so, let $E_{M}:=W(M,N)$ and
let $I_{M}\subseteq E_{M}$ be a witness that $E_{M}$ is a wave. For
$E_{N}:=E\setminus E_{M}$, we have $M/E_{M}\in\mathfrak{F}(E_{N})$ and
$N-E_{M}\in(\mathfrak{F}\oplus\mathfrak{F}^{*})(E_{N})$, furthermore,
$\mathsf{cond}^{+}(M/W,N-W)$ holds (see Corollary 3.11). By Claim 4.2, there
is an $M/E_{M}$-independent base $I_{N}$ of $N-E_{M}$. Then
$I\in\mathcal{I}_{M}\cap\mathcal{I}_{N}$ and $E=E_{M}\sqcup E_{N}$ such that
$I_{M}:=I\cap E_{M}$ spans $E_{M}$ in $M$ and $I_{N}:=I\cap E_{N}$ spans
$E_{N}$ in $N$ as desired. ∎

###  4.3. Reduction to a key-lemma

From now on we assume that $M\in\mathfrak{F}(E)$ and
$N\in(\mathfrak{F}\oplus\mathfrak{F}^{*})(E)$ where $E$ is countable. Let
$\boldsymbol{E_{0}}$ be the union of the finitary components of $N$ and let
$\boldsymbol{E_{1}}:=E\setminus E_{0}$. Note that $N\upharpoonright E_{0}$ is
finitary, $N\upharpoonright E_{1}$ is cofinitary and no $N$-circuit meets both
$E_{0}$ and $E_{1}$.

######  Lemma 4.4 (key-lemma).

If $\mathsf{cond}^{+}(M,N)$ holds, then for every $e\in E_{0}$ there is a nice
feasible $I$ with $e\in\mathsf{span}_{N}(I)$.

######  Lemma 4.5.

Lemma 4.4 implies our main results Theorems 1.2 and 1.4.

###### Proof.

It is enough to show that Lemma 4.4 implies Claim 4.2 because of Lemma 4.3.
Let us fix an enumeration $\\{e_{n}:n\in\mathbb{N}\\}$ of $E_{0}$. We build an
$\subseteq$-increasing sequence $(I_{n})$ of nice feasible sets starting with
$I_{0}:=\varnothing$ (who is nice feasible by $\mathsf{cond}^{+}(M,N)$) in
such a way that ${e_{n}\in\mathsf{span}_{N}(I_{n+1})}$. Suppose that $I_{n}$
is already defined. If $e_{n}\notin\mathsf{span}_{N}(I_{n})$, then we apply
Lemma 4.4 with $(M/I_{n},N/I_{n})$ and $e_{n}$ and take the union of the
resulting $I$ with $I_{n}$ to obtain $I_{n+1}$ (see Observation 3.13),
otherwise let $I_{n+1}:=I_{n}$. The recursion is done. Now we construct an
$M$-independent $I^{+}_{n}\supseteq I_{n}$ with
$E_{1}\subseteq\mathsf{span}_{N}(I^{+}_{n})$ for $n\in\mathbb{N}$. The matroid
$M/I_{n}\upharpoonright(E_{1}\setminus I_{n})$ is finitary and
$N.(E_{1}\setminus I_{n})=(N\upharpoonright E_{1})/(I_{n}\cap E_{1})$ is
cofinitary, moreover, by Observation 3.12

$\mathsf{cond}^{+}(M/I_{n},N/I_{n})\Longrightarrow\mathsf{cond}^{+}(M/I_{n}\upharpoonright(E_{1}\setminus
I_{n}),N.(E_{1}\setminus I_{n})).$

Thus by Corollary 3.7 there is an $M/I_{n}$-independent base $B_{n}$ of
$(N\upharpoonright E_{1})/(E_{1}\cap I_{n})$ and $I^{+}_{n}:=I_{n}\cup B_{n}$
is as desired.

Let $\mathcal{U}$ be a free ultrafilter on $\mathcal{P}(\mathbb{N})$ ad we
define

$S:=\\{e\in E:\\{n\in\mathbb{N}:e\in I^{+}_{n}\\}\in\mathcal{U}\\}.$

Then $S$ is $M$-independent and $N$-spanning and therefore we are done.
Indeed, suppose for a contradiction that $S$ contains an $M$-circuit $C$. For
$e\in C$, we pick a $U_{e}\in\mathcal{U}$ with $e\in I^{+}_{n}$ for $n\in
U_{e}$. Since $M$ is finitary, $C$ is finite, thus $U:=\cap\\{U_{e}:e\in
C\\}\in\mathcal{U}$. But then for $n\in U$ we have $C\subseteq I^{+}_{n}$
which contradicts the $M$-independence of $I^{+}_{n}$. Clearly,
$I_{n+1}\subseteq S$ for every $n\in\mathbb{N}$ and therefore
$E_{0}\subseteq\mathsf{span}_{N}(S)$. Finally, suppose for a contradiction
that there is some $N^{*}\upharpoonright E_{1}$-circuit $C^{\prime}$ with
$S\cap C^{\prime}=\varnothing$. For $e\in C^{\prime}$, we can pick a
$U_{e}^{\prime}\in\mathcal{U}$ with $e\notin I^{+}_{n}$ for $n\in
U_{e}^{\prime}$. Since $N^{*}\upharpoonright E_{1}$ is finitary, $C^{\prime}$
is finite, thus $U^{\prime}:=\cap\\{U_{e}^{\prime}:e\in
C^{\prime}\\}\in\mathcal{U}$. But then for $n\in U^{\prime}$ we have
$I^{+}_{n}\cap C=\varnothing$ which contradicts
$E_{1}\subseteq\mathsf{span}_{N}(I^{+}_{n})$. ∎

##  5\. Mixed augmenting paths

In the section we introduce an ‘augmenting path’ type of method and analyse it
in order to show some properties we need later. On $E_{0}$ the definition will
be the same as in the proof of the Matroid Intersection Theorem by Edmonds
[edmonds2003submodular] but on $E_{1}$ we need to define it in a different way
considering that $N\upharpoonright E_{1}$ is cofinitary. For brevity we write
$\boldsymbol{\overset{\circ}{\mathsf{span}}_{M}(F)}$ for
$\mathsf{span}_{M}(F)\setminus F$ and $\boldsymbol{F^{j}}$ for $F\cap E_{j}$
where $F\subseteq E$ and $j\in\\{0,1\\}$. We call an $F\subseteq E$ _dually
safe_ if $F^{1}$ is spanned by $\overset{\circ}{\mathsf{span}}_{M}(F)$ in
$N^{*}$.

######  Lemma 5.1.

If $I\in\mathcal{I}_{M}\cap\mathcal{I}_{n}$ is dually safe and $B\in
B(M/I,N/I,W)$ for $W:=W(M/I,N/I)$, then $I\cup B$ is a nice dually safe
feasible set.

###### Proof.

We already know by Corollary 3.16 that $I\cup B$ is a nice feasible set. By
using that $I$ is dually safe and
$\overset{\circ}{\mathsf{span}}_{M}(I)\subseteq\overset{\circ}{\mathsf{span}}_{M}(I\cup
B)$ we get

$I^{1}\subseteq\mathsf{span}_{N^{*}}(\overset{\circ}{\mathsf{span}}_{M}(I))\subseteq\mathsf{span}_{N^{*}}(\overset{\circ}{\mathsf{span}}_{M}(I\cup
B)).$

Since $B\in B(M/I,N/I,W)$ we have $W\setminus
B\subseteq\overset{\circ}{\mathsf{span}}_{M}(I\cup B)$ and $B$ is a base of
$N.W$. The latter can be rephrased as ‘$W\setminus B$ is a base of
$N^{*}\upharpoonright W$’. By combining these
$\overset{\circ}{\mathsf{span}}_{M}(I\cup B)$ spans $B$ in $N^{*}$. Therefore
$(I\cup B)\cap
E_{1}\subseteq\mathsf{span}_{N^{*}}(\overset{\circ}{\mathsf{span}}_{M}(I\cup
B))$, which means that $I\cup B$ is dually safe. ∎

######  Proposition 5.2.

For a dually safe feasible $I$, $\overset{\circ}{\mathsf{span}}_{M}(I)^{1}$ is
a base of ${N^{*}\upharpoonright\mathsf{span}_{M}(I)^{1}}$.

###### Proof.

By the definition of ‘dually safe’,
$\overset{\circ}{\mathsf{span}}_{M}(I)^{1}$ spans
$N^{*}\upharpoonright\mathsf{span}_{M}(I)^{1}$. Furthermore,
$r(N.\overset{\circ}{\mathsf{span}}_{M}(I))=0$ by Corollary 3.9, which is
equivalent with the $N^{*}$-independence of
$\overset{\circ}{\mathsf{span}}_{M}(I)$. ∎

For a dually safe feasible $I$, we define an auxiliary digraph $D(I)$ on $E$.
Let $xy$ be an arc of $D(I)$ iff one of the following possibilities occurs:

  1. (1)

$x\in E\setminus I$ and $I+x$ is $M$-dependent with $y\in C_{M}(x,I)-x$,

  2. (2)

$x\in I^{0}$ and $C_{N}(y,I)$ is well-defined and contains $x$,

  3. (3)

$x\in I^{1}$ and $y\in
C_{N^{*}}(x,\overset{\circ}{\mathsf{span}}_{M}(I)^{1})-x$ (see Proposition
5.2).

An augmenting path for a nice dually safe feasible $I$ is a
$P=\\{x_{1},\dots,x_{2n+1}\\}$ where

  1. (i)

$x_{1}\in E_{0}\setminus\mathsf{span}_{N}(I)$,

  2. (ii)

$x_{2n+1}\in E_{0}\setminus\mathsf{span}_{M}(I)$,

  3. (iii)

$x_{k}x_{k+1}\in D(I)$ for $1\leq k\leq 2n$,

  4. (iv)

$x_{k}x_{\ell}\notin D(I)$ if $k+1<\ell$.

######  Proposition 5.3.

If $I$ is a dually safe feasible set and $P=\\{x_{1},\dots,x_{2n+1}\\}$ is an
augmenting path for $I$, then $I\vartriangle P$ is a dually safe element of
$\mathcal{I}_{M}\cap\mathcal{I}_{N}$ with

  1. (A)

$\mathsf{span}_{M}(I\vartriangle P)=\mathsf{span}_{M}(I+x_{2n+1})$,

  2. (B)

$\mathsf{span}_{N}(I\vartriangle P)\cap E_{0}=\mathsf{span}_{N}(I+x_{1})\cap
E_{0}$,

  3. (C)

$\mathsf{span}_{N^{*}}(\overset{\circ}{\mathsf{span}}_{M}(I)^{1})=\mathsf{span}_{N^{*}}(\overset{\circ}{\mathsf{span}}_{M}(I)^{1}\vartriangle
P^{1})$ and $\overset{\circ}{\mathsf{span}}_{M}(I)^{1}\vartriangle
P^{1}\in\mathcal{I}_{N^{*}}$.

###### Proof.

The set $I+x_{2n+1}$ is $M$-independent by the definition of $P$. Property
(iv) ensures that we can apply Proposition 3.1 with $I+x_{2n+1},\
e_{j}=x_{2j-1},\ f_{j}=x_{2j}\ (1\leq j\leq n)$ and $M$ and conclude that
$I\vartriangle P\in\mathcal{I}_{M}$ and (A) holds.

To prove $(I\vartriangle P)\cap E_{0}\in\mathcal{I}_{N}$ and (B) we proceed
similarly. We start with the $N$-independent set $(I+x_{1})\cap E_{0}$. In
order to satisfy the premisses of Proposition 3.1 via property (iv), we need
to enumerate the relevant edge pairs backwards. Namely, for
$j\leq\left|I^{0}\cap P\right|$ let $e_{j}:=x_{i_{j}+1}$ where $i_{j}$ is the
$j$th largest index with $x_{i_{j}}\in I^{0}$ and $f_{j}:=x_{i_{j}}$. We
conclude that $(I\vartriangle P)\cap E_{0}\in\mathcal{I}_{N}$ and (B) holds.

Finally, we let $e_{j}:=x_{i_{j}}$ for $j\leq\left|I^{1}\cap P\right|$ where
$i_{j}$ is the $j$th smallest index with $x_{i_{j}}\in I^{1}$ and
$f_{j}:=x_{i_{j}+1}$. Recall that $\overset{\circ}{\mathsf{span}}_{M}(I)^{1}$
is $N^{*}$-independent (see Proposition 5.2). We apply Proposition 3.1 with
$\overset{\circ}{\mathsf{span}}_{M}(I)^{1},\ e_{j},\ f_{j}$ and $N^{*}$ to
conclude (C). This means that
$\overset{\circ}{\mathsf{span}}_{M}(I)^{1}\vartriangle P^{1}$ is a base of
$N^{*}\upharpoonright\mathsf{span}_{M}(I)^{1}$ because
$\overset{\circ}{\mathsf{span}}_{M}(I)^{1}$ was a base of it by Proposition
5.2. By (A) and by the definition of $P$ we know that

$(I\vartriangle P)\cap E_{1}\subseteq I^{1}\cup
P^{1}\subseteq\mathsf{span}^{1}_{M}(I).$

By combining these we obtain

$(I\vartriangle P)\cap
E_{1}\subseteq\mathsf{span}_{N^{*}}(\overset{\circ}{\mathsf{span}}_{M}(I)^{1}\vartriangle
P^{1}).$

The set $I\vartriangle P$ is disjoint from
$\overset{\circ}{\mathsf{span}}_{M}(I)\vartriangle P$ because $I$ is disjoint
from $\overset{\circ}{\mathsf{span}}_{M}(I)$, moreover,
$\overset{\circ}{\mathsf{span}}_{M}(I)\vartriangle P$ contained in
$\mathsf{span}_{M}(I\vartriangle P)$. Hence
$\overset{\circ}{\mathsf{span}}_{M}(I\vartriangle P)$ contains
$\overset{\circ}{\mathsf{span}}_{M}(I)^{1}\vartriangle P^{1}$ and therefore
$N^{*}$-spans $(I\vartriangle P)\cap E_{1}$, i.e. $I\vartriangle P$ is dually
safe. It means that $(I\vartriangle P)\cap E_{1}$ is independent in
$N.\mathsf{span}_{M}(I\vartriangle P)^{1}$. Thus uniting $(I\vartriangle
P)\cap E_{0}\in\mathcal{I}_{N}$ with $(I\vartriangle P)\cap E_{1}$ preserves
$N$-independence, i.e. $I\vartriangle P\in\mathcal{I}_{N}$.

∎

######  Lemma 5.4.

If $I$ is a nice dually safe feasible set and $P=\\{x_{1},\dots,x_{2n+1}\\}$
is an augmenting path for $I$, then $I\vartriangle P$ can be extended to a
nice dually safe feasible set.

###### Proof.

Let $M^{\prime}:=M/(I\vartriangle P)$ and $N^{\prime}:=N/(I\vartriangle P)$.
By Lemma 5.1 it is enough to show that
$B(M^{\prime},N^{\prime},W)\neq\varnothing$ for $W:=W(M^{\prime},N^{\prime})$.
Statements (A) and (B) of Proposition 5.3 ensure that the elements of
$L:=\\{x_{1},x_{3},\dots,x_{2n-1}\\}\cap E_{0}$ are common loops of
$M^{\prime}$ and $N^{\prime}$. Statement (C) tells that
$Y_{0}:=\overset{\circ}{\mathsf{span}}_{M}(I)^{1}$ and
$Y_{1}:=\overset{\circ}{\mathsf{span}}_{M}(I)^{1}\vartriangle P^{1}$ have the
same $N^{*}$-span, furthermore, $Y_{1}$ is $N^{*}$-independent, i.e.
$r(N.Y_{1})=0$. Note that $Y_{1}$ consists of $M^{\prime}$-loops by (A). Thus
by applying Observation 3.18 with $W$ and $L$ and then Lemma 3.19 with
$W\setminus L$ and $Y_{1}$ we can conclude that $W\setminus(L\cup Y_{1})$ is
an $(M^{\prime}-Y_{1},N^{\prime}-Y_{1})$-wave, furthermore,

$B(M^{\prime},N^{\prime},W)=B(M^{\prime}-Y_{1},N^{\prime}-Y_{1},W\setminus(L\cup
Y_{1})).$

The sets $X_{0}:=I+x_{2n+1}$ and $X_{1}:=I\vartriangle P$ have the same
$M$-span (see Proposition 5.3/ (A)). Recall that $M^{\prime}=M/X_{1}$ and
$N^{\prime}=N/X_{1}$ by definition. Hence Lemma 3.20 ensures that
$W\setminus(Y_{1}\cup L)$ is also an $(M/X_{0}-Y_{0},M/X_{0}-Y_{0})$-wave with

$B(M/X_{1}-Y_{1},N/X_{1}-Y_{1},W\setminus(Y_{1}\cup
L))=B(M/X_{0}-Y_{0},M/X_{0}-Y_{0},W\setminus(Y_{1}\cup L)).$

We have $\mathsf{cond}^{+}(M/I,N/I)$ because $I$ is a nice feasible set by
assumption. Then by Observation 3.17 $\mathsf{cond}^{+}(M/I-Y_{0},N/I-Y_{0})$
also holds. Applying Lemma 3.14 with $M/I-Y_{0},\ N/I-Y_{0},\
W\setminus(Y_{0}\cup L)$ and $x_{2n+1}$ tells
$B(M/X_{0}-Y_{0},M/X_{0}-Y_{0},W\setminus(Y_{1}\cup L))\neq\varnothing$ which
completes the proof. ∎

######  Lemma 5.5.

If $P=\\{x_{1},\dots,x_{2n+1}\\}$ is an augmenting path for $I$ which contains
neither $x$ nor any of its out-neighbours in $D(I)$, then $xy\in D(I)$ implies
$xy\in D(I\vartriangle P)$.

###### Proof.

Suppose that $xy\in D(I)$. First we assume that $x\notin I$. Then the set of
the out-neighbours of $x$ is $C_{M}(x,I)-x$. By assumption $P\cap
C_{M}(x,I)=\varnothing$ and therefore $C_{M}(x,I)\subseteq I\vartriangle P$
thus $C_{M}(x,I)=C_{M}(x,I\vartriangle P)$. This means by definition that $x$
has the same out-neighbours in $D(I)$ and $D(I\vartriangle P)$.

If $x\in I^{1}$, then we can argue similarly. The set of the out-neighbours of
$x$ in $D(I)$ is $C_{N^{*}}(x,\overset{\circ}{\mathsf{span}}_{M}(I)^{1})-x$.
By assumption $P\cap
C_{N^{*}}(x,\overset{\circ}{\mathsf{span}}_{M}(I)^{1})=\varnothing$ and
therefore
$C_{N^{*}}(x,\overset{\circ}{\mathsf{span}}_{M}(I)^{1})\cap(I\vartriangle
P)=\\{x\\}$. Since $\mathsf{span}^{1}_{M}(I\vartriangle
P)\supseteq\mathsf{span}^{1}_{M}(I)$ because of Proposition 5.3/(A), we also
have
$C_{N^{*}}(x,\overset{\circ}{\mathsf{span}}_{M}(I)^{1})\subseteq\mathsf{span}^{1}_{M}(I\vartriangle
P)$. By combining these we conclude

$C_{N^{*}}(x,\overset{\circ}{\mathsf{span}}_{M}(I\vartriangle
P)^{1})=C_{N^{*}}(x,\overset{\circ}{\mathsf{span}}_{M}(I)^{1}).$

This means by definition that $x$ has the same out-neighbours in $D(I)$ and
$D(I\vartriangle P)$.

We turn to the case where $x\in I^{0}$. By definition $C_{N}(y,I)$ is well-
defined and contains $x$, in particular $y\in E_{0}$. For $k\leq n$, let us
denote $I+x_{1}-x_{2}+x_{3}-\ldots-x_{2k}+x_{2k+1}$ by $I_{k}$. Note that
${I_{n}=I\vartriangle P}$. We show by induction on $k$ that $I_{k}$ is
$N$-independent and ${x\in C_{N}(y,I_{k})}$. Since $I+x_{1}$ is
$N$-independent by definition and $x_{1}\neq y$ because $y\notin P$ by
assumption, we obtain $C_{N}(y,I)=C_{N}(y,I_{0})$, thus for $k=0$ it holds.
Suppose that $n>0$ and we already know the statement for some $k<n$. We have
$C_{N}(x_{2k+3},I_{k})=C_{N}(x_{2k+3},I)\ni x_{2k+2}$ because there is no
“jumping arc” in the augmenting path by property (iv). It follows via the
$N$-independence of $I_{k}$ that $I_{k+1}$ is also $N$-independent. If
$x_{2k+2}\notin C_{N}(y,I_{k})$ then $C_{N}(y,I_{k})=C_{N}(y,I_{k+1})$ and the
induction step is done. Suppose that $x_{2k+2}\in C_{N}(y,I_{k})$. Then
$x_{2k+2},x_{2k+3}\in E_{0}$, moreover, $x\notin C_{N}(x_{2k+3},I)$ since
otherwise $P$ would contain the out-neighbour $x_{2k+3}$ of $x$ in $D(I)$. We
apply circuit elimination (Claim 3.3) with $C=C_{N}(y,I_{k}),\ e=x,\
X=\\{x_{2k+2}\\},\ C_{x_{2k+2}}=C_{N}(x_{2k+3},I_{k})$. The resulting circuit
$C^{\prime}\ni x$ can have at most one element out of $I_{k+1}$, namely $y$.
Since $I_{k+1}$ is $N$-independent, there must be at least one such an element
and therefore $C^{\prime}=C_{N}(y,I_{k+1})$. ∎

######  Observation 5.6.

If $xy\in D(I)$ and $J\supseteq I$ is a dually safe feasible set with
$\\{x,y\\}\cap J=\\{x,y\\}\cap I$, then $xy\in D(J)$ (the same circuit is the
witness).

##  6\. Proof of the key-lemma

See 4.4

###### Proof.

It is enough to build a sequence $(I_{n})$ of nice dually safe feasible sets
such that $(\mathsf{span}_{N}(I_{n})\cap E_{0})$ is an ascending sequence
exhausting $E_{0}$. We fix a well-order $\boldsymbol{\prec}$ of type
$\left|E_{0}\right|$ on $E_{0}$. Let $I_{0}=\varnothing$, which is a nice
dually safe feasible set by $\mathsf{cond}^{+}(M,N)$. Suppose that $I_{n}$ is
already defined. If there is no augmenting path for $I_{n}$, then we let
$I_{m}:=I_{n}$ for $m>n$. Otherwise we pick an augmenting path $P_{n}$ for
$I_{n}$ in such a way that its first element is as $\prec$-small as possible.
Then we apply Lemma 5.3 to extend $I\vartriangle P$ to a nice dually safe
feasible set which we define to be $I_{n+1}$. The recursion is done.

Let
$\boldsymbol{X}:=E\setminus\bigcup_{n\in\mathbb{N}}\mathsf{span}_{N}(I_{n})$
and for $x\in X$, let $\boldsymbol{E(x,n)}$ be the set of elements that are
reachable from $x$ in $D(I_{n})$ by a directed path. We define
$\boldsymbol{n_{x}}$ to be the smallest natural number such that for every
$y\in E\setminus X$ with $y\prec x$ we have
$y\in\mathsf{span}_{N}(I_{n_{x}})$. We shall prove that

$\boldsymbol{W}:=\bigcup_{x\in X}\bigcup_{n\geq n_{x}}E(x,n)$

is a wave.

######  Lemma 6.1.

For every $x\in X$ and $\ell\geq m\geq n_{x}$,

  1. (1)

$I_{m}\cap E(x,m)=I_{\ell}\cap E(x,m)$,

  2. (2)

$C_{M}(y,I_{\ell})=C_{M}(y,I_{m})\subseteq E(x,m)$ for every $y\in
E(x,m)\setminus I_{m}$,

  3. (3)

$C_{N^{*}}(y,\overset{\circ}{\mathsf{span}}_{M}(I_{\ell})^{1})=C_{N^{*}}(y,\overset{\circ}{\mathsf{span}}_{M}(I_{m})^{1})$
for every $y\in E(x,m)\cap I_{m}^{1}$,

  4. (4)

If $yz\in D(I_{m})$ with $y,z\in E(x,m)$, then $yz\in D(I_{\ell})$,

  5. (5)

$E(x,m)\subseteq E(x,\ell)$.

###### Proof.

Suppose that there is an $n\geq n_{x}$ such that we know already the statement
whenever $m,\ell\leq n$. For the induction step it is enough to show that the
claim holds for $n$ and $n+1$. We may assume that $P_{n}$ exists, i.e.
$I_{n}\neq I_{n+1}$, since otherwise there is nothing to prove.

######  Proposition 6.2.

$P_{n}\cap E(x,n)=\varnothing$.

###### Proof.

A common element of $P_{n}$ and $E(x,n)$ would show that there is also an
augmenting path in $D(I_{n})$ starting at $x$ which is impossible since $x\in
X$ and $n\geq n_{x}$. ∎

######  Corollary 6.3.

$I_{n}\cap E(x,n)=(I_{n}\vartriangle P_{n})\cap E(x,n)$.

######  Proposition 6.4.

$(I_{n}\vartriangle P_{n})\cap E(x,n)=I_{n+1}\cap E(x,n)$.

###### Proof.

If $y\in E(x,n)\setminus I_{n}$, then its out-neighbours in $D(I_{n})$ are in
$E(x,n)\cap I_{n}$ and span $y$ in $M$. Thus
$I_{n+1}\setminus(I_{n}\vartriangle P_{n})$ cannot contain any edge from
$E(x,n)$. ∎

######  Corollary 6.5.

$I_{n}\cap E(x,n)=I_{n+1}\cap E(x,n)$ and for every $y\in E(x,n)\setminus
I_{n}$ we have $C_{M}(y,I_{n})=C_{M}(y,I_{n+1})\subseteq E(x,n)$.

######  Corollary 6.6.

For $y\in E(x,n)\setminus I_{n}$, $y$ has the same out-neighbours in
$D(I_{n})$ and in $D(I_{n+1})$ and they span $y$ in $N^{*}$. More concretely:

$C_{N^{*}}(y,\overset{\circ}{\mathsf{span}}_{M}(I_{n+1})^{1})=C_{N^{*}}(y,\overset{\circ}{\mathsf{span}}_{M}(I_{n})^{1}).$

Finally, for $y\in E(x,n)$, $P_{n}$ does not contain $y$ or any of its out-
neighbours with respect to $D(I_{n})$ because $P_{n}\cap E(x,n)=\varnothing$.
Hence by applying Lemma 5.5 with $P_{n},y$ and $I_{n}$ (and then Observation
5.6) we may conclude that $yz\in D(I_{n+1})$ whenever $yz\in D(I_{n})$. This
implies $E(x,n)\subseteq E(x,n+1)$ since reachability from $x$ is witnessed by
the same directed paths. ∎

Let

$B:=\bigcup_{m\in\mathbb{N}}\bigcap_{n>m}W\cap I_{n}.$

We are going to show that $B$ witnesses that $W$ is a wave. Since $M$ is
finitary the $M$-independence of the sets $I_{n}\cap W$ implies the
$M$-independence of $B$. Similarly $B^{0}$ is independent in $N$ because
$N\upharpoonright E_{0}$ is finitary. Statements (1) and (2) of Claim 6.1
ensure $W\subseteq\mathsf{span}_{M}(B)$, while (1) and (3) guarantee
$B^{1}\subseteq\mathsf{span}_{N^{*}}(W\setminus B)$. The latter means that
$B^{1}$ is independent in $N.(W^{1}\setminus B^{1})$. Suppose for a
contradiction that $B^{0}$ is not independent in $N.W^{0}$. Then there exists
an $N$-circuit $C\subseteq E_{0}$ that meets $B$ but avoids $W\setminus B$. We
already know that $B^{0}$ is $N$-independent thus $C$ is not contained in $B$.
Hence $C\setminus B=C\setminus W\neq\varnothing$. Let us pick some $e\in C\cap
B$. Since $C$ is finite, for every large enough $n$ we have $C\cap B\subseteq
C\cap I_{n}$ and $I_{n}$ spans $C$ in $N$ (for the latter we use $X\subseteq
W\setminus B$). Applying Corollary 3.4 with $I_{n},N,C$ and $e$ tells that
$e\in C_{N}(f,I_{n})$ for some $f\in C\setminus W$ whenever $n$ is large
enough. Then by (5) of Claim 6.1 we can take an $x\in X$ and an $n\geq n_{x}$
such that $e\in E(x,n)\cap C_{N}(f,I_{n})$ for some $f\in C\setminus W$. Then
by definition $f\in E(x,n)\subseteq W$ which contradicts $f\in C\setminus W$.
Thus $B^{0}$ is indeed independent in $N.W^{0}$ and hence $B$ in $N.W$ as well
therefore $W$ is a wave.

By $\mathsf{cond}^{+}(M,N)$ we know that $W$ consists of $M$-loops and
$r(N.W)=0$. It implies $r(N.X)=0$ because $X\subseteq W$ by definition. This
means $X\subseteq\mathsf{span}_{N}(E\setminus X)$. Since $X\subseteq E_{0}$
and $E_{0}$ is the union of the finitary $N$-components,
$X\subseteq\mathsf{span}_{N}(E_{0}\setminus X)$ follows. Thus for every $x\in
X$ there is a finite $N$-circuit $C\subseteq E_{0}$ with $C\cap X=\\{x\\}$.
The sequence $(\mathsf{span}_{N}(I_{n})\cap E_{0})$ is ascending by
construction and exhausts $E_{0}\setminus X$ by the definition of $X$. As
$C-x\subseteq E_{0}\setminus X$ is finite, this implies that for every large
enough $n$, $I_{n}$ spans $C-x$ in $N$ and hence spans $x$ itself as well. But
then by the definition of $X$, we must have $X=\varnothing$. Therefore
$(\mathsf{span}_{N}(I_{n})\cap E_{0})$ exhausts $E_{0}$ and the proof of Lemma
4.4 is complete. ∎

##  7\. An application: Degree-constrained orientations of infinite graphs

Matroid intersection is a powerful tool in graph theory and in combinatorial
optimization. Our generalization Theorem 1.4 extends the scope of its
applicability to infinite graphs. To illustrate this, let us consider a
classical problem in combinatorial optimization. A graph is given with degree-
constrains and we are looking for either an orientation that satisfies it or a
certain substructure witnessing the non-existence of such an orientation (see
[hakimi1965degrees]).

Let a (possibly infinite) graph $G=(V,E)$ be fixed through this section. We
denote the set of edges incident with $v$ by $\boldsymbol{\delta(v)}$. Let
$o:V\rightarrow\mathbb{Z}$ with $\left|o(n)\right|\leq d(v)$ for $v\in V$
which we will threat as ‘lower bounds’ for in-degrees in orientations in the
following sense. We say that the orientation $D$ of $G$ is _above_ $o$ at $v$
if either $o(v)\geq 0$ and $v$ has at least $o(v)$ ingoing edges in $D$ or
$o(v)<0$ and all but at most $-o(v)$ edges in $\delta(v)$ are oriented towards
$v$ by $D$. We say _strictly above_ if we forbid equality in the definition.
Orientation $D$ is above $o$ if it is above $o$ at every $v\in V$. We say that
$D$ is (strictly) bellow $o$ at $v$ if the reverse of $D$ is (strictly) above
$-o(v)$. Finally, $D$ is (strictly) bellow $o$ if the reverse of $D$ is
strictly above $-o$.

######  Theorem 7.1.

Let $G=(V,E)$ be a countable graph and let $o:V\rightarrow\mathbb{Z}$. If
there is no orientation of $G$ above $o$, then there is a $V^{\prime}\subseteq
V$ and an orientation $D$ of $G$ such that

  * •

$D$ is bellow $o$ at every $v\in V^{\prime}$;

  * •

There exists a $v\in V^{\prime}$ such that $D$ is strictly bellow $o$ at $v$;

  * •

Every edge between $V^{\prime}$ and $V\setminus V^{\prime}$ is oriented by $D$
towards $V^{\prime}$.

###### Proof.

Without loss of generality we may assume that $G$ is loopless. We define the
digraph $\overset{\leftrightarrow}{G}=(V,A)$ by replacing each $e\in E$ by
back and forth arcs $a_{e},a^{\prime}_{e}$ between the end-vertices of $e$.
Let $\delta^{+}(v)$ be the set of the ingoing edges of $v$ in
$\overset{\leftrightarrow}{G}$. For $v\in V$, let $M_{v}$ be
$U_{\delta^{+}(v),o(v)}$ if $o(v)\geq 0$ and $U_{\delta^{+}(v),-o(v)}^{*}$ if
$o(v)<0$. We define $N_{e}$ to be $U_{\\{a_{e},a^{\prime}_{e}\\},1}$ for $e\in
E$. Let

$M:=\bigoplus_{v\in V}M_{v}\text{ and }N:=\bigoplus_{e\in E}N_{e}.$

Since $M,N\in(\mathfrak{F}\oplus\mathfrak{F}^{*})(A)$, Theorem 1.4 guarantees
that there exists an $I\in\mathcal{I}_{M}\cap\mathcal{I}_{N}$ and a partition
$A=A_{M}\sqcup A_{N}$ such that $I_{M}:=I\cap A_{M}$ spans $A_{M}$ in $M$ and
$I_{N}:=I\cap A_{N}$ spans $A_{N}$ in $N$. Note that
$\left|I\cap\\{a_{e},a^{\prime}_{e}\\}\right|\leq 1$ by the $N$-independence
of $I$. We define $D$ by taking the orientation $a_{e}$ of $e$ if $a_{e}\in I$
and $a^{\prime}_{e}$ otherwise. Let $V^{\prime\prime}$ consists of those
vertices $v$ for which $I_{M}$ contains a base of $M_{v}$ and let
$V^{\prime}:=V\setminus V^{\prime\prime}$. We claim that whenever an edge
$e\in E$ is incident with some $v\in V^{\prime}$, then $I$ contains one of
$a_{e}$ and $a^{\prime}_{e}$. Indeed, if $I$ contains none of them then they
cannot be $N$-spanned by $I_{N}$ thus they are $M$-spanned by $M$ which
implies that both end-vertices of $e$ belong to $V^{\prime\prime}$,
contradiction. Thus if $e$ is incident some $v\in V^{\prime}$, then all
ingoing arcs of $v$ in $D$ must be in $I$. Then the $M$-independence of $I$
ensures that $D$ is bellow $o$ at $v$.

Suppose for a contradiction that $a_{e}$ is an arc in $D$ from a $v\in
V^{\prime}$ to a $w\in V^{\prime\prime}$. As we have already shown, we must
have $a_{e}\in I$ . By $w\in V^{\prime\prime}$ we know that $I_{M}$ contains a
base of $M_{w}$ thus $a_{e}\notin I_{N}$ by the $M$-independence of $I$ and
therefore $a_{e}\in I_{M}$. But then $a^{\prime}_{e}$ cannot be spanned by
$I_{N}$ in $N$ hence $a^{\prime}_{e}\in\mathsf{span}_{M}(I_{M})$, which means
that $I_{M}$ contains a base of $M_{v}$ contradicting $v\in V^{\prime}$. We
conclude that all the edges between $V^{\prime\prime}$ and $V^{\prime}$ are
oriented towards $V^{\prime}$ in $D$. By the definition of $V^{\prime\prime}$,
$D$ is above $o$ at every $w\in V^{\prime\prime}$. If $D$ is also above $o$
for every $v\in V^{\prime}$, then $D$ is above $o$. Otherwise there exists a
$v\in V^{\prime}$ such that $D$ is strictly bellow $o$ at $v$, but then
$V^{\prime}$ is as desired. ∎

Easy calculation shows that if $G$ is finite, then the existence of a
$V^{\prime}$ described in Theorem 7.1 implies the non-existence of an
orientation above $o$. Indeed, the total demand by $o$ on $V^{\prime}$ is more
than the number of all the edges that are incident with a vertex in
$V^{\prime}$. That is why for finite $G$, “if” can be replaced by “if and only
if” in Theorem 7.1. For an infinite $G$ it is not always the case. Indeed, let
$G$ be the one-way infinite path $v_{0},v_{1},\dots$ and let $o(v_{n})=1$ for
$n\in\mathbb{N}$. Then orienting edge $\\{v_{n},v_{n+1}\\}$ towards $v_{n+1}$
for each $n\in\mathbb{N}$ and taking $V^{\prime}:=V$ satisfies the three
points in Theorem 7.1. However, taking the opposite orientation is above $o$.

A natural next step is to introduce upper bounds $p:V\rightarrow\mathbb{Z}$
beside the lower bounds $o:V\rightarrow\mathbb{Z}$. To avoid trivial
obstructions we assume that $o$ and $p$ are _consistent_ which means that for
every $v\in V$ there is an orientation $D_{v}$ which is above $o$ at bellow
$p$ at $v$.

######  Question 7.2.

Let $G$ be a countable graph and let $o,p:V\rightarrow\mathbb{Z}$ be a
consistent pair of bounding functions. Suppose that there are orientations
$D_{o}$ and $D_{p}$ that are above $o$ and bellow $p$ respectively. Is there
always a single orientation $D$ which is above $o$ and bellow $p$?

The positive answer for finite graphs is not too hard to prove, as far we know
its first appearance in the literature is [frank1978orient].

## References