# Rota’s Basis Conjecture for Binary Matroids with Density Close to One

Sean McGuinness  Thompson Rivers University

###### Abstract

Rota’s basis conjecture (RBC) states that given a collection $\mathcal{B}$ of
$n$ bases in a matroid $M$ of rank $n$, one can always find $n$ disjoint
rainbow bases with respect to $\mathcal{B}$. We show that if $M$ is a binary
matroid having $n+k$ elements, then one can construct $n-b_{0}$ disjoint
rainbow bases, where $b_{0}$ is a constant depending only on $k.$

Keywords : Binary matroid, basis, Rota’s basis conjecture, girth.

AMS Subject Classifications (2012) : 05D99,05B35.

##  1 Introduction

For basic concepts and notation pertaining to matroids, we follow Oxley [14],
and for graphs, we shall follow Bondy and Murty [2]. Let $M$ be a matroid of
rank $n$. A base sequence of $M$ is an $n$-tuple $\mathcal{B}=(B_{1},\ldots
B_{n})\in\mathfrak{B}(M)^{n}$ of bases of $M$, where for each
$i\in\\{1,2,\ldots,n\\}$, we think of the base $B_{i}$ as “coloured” with
colour $i$. A rainbow base (RB) with respect to $\mathcal{B}$ is a base of $M$
that contains exactly one element of each colour. Rainbow bases with respect
to $\mathcal{B}$ are said to be disjoint if for each colour $c$, the
representatives of colour $c$ are distinct. We let $t_{M}(\mathcal{B})$ denote
the cardinality of a largest set of disjoint rainbow bases with respect to
$\mathcal{B}$, where the subscript is dropped when $M$ is implicit. In 1989,
Rota made the following conjecture, first communicated in [11]:

######  Conjecture 1.1 (Rota’s Basis Conjecture (RBC))

Let $M$ be a matroid of rank $n$, and let $\mathcal{B}$ be a base sequence of
$M$. Then $t(\mathcal{B})=n$.

Due to the work of Drisko [7], Glynn [10], and Onn [13] on the Alon-Tarsi
conjecture [1], RBC is known to be true for $\mathbb{F}$-representable
matroids of rank $p\pm 1$, where $\mathbb{F}$ is a field of characteristic
$0$, and $p$ is an odd prime. See [8] for an overview of these results. Chan
[4] and Cheung [5] proved RBC for matroids of rank $3$ and $4$, respectively.
In [9], it was shown that RBC is true for sparse paving matroids and Wild [16]
proved the conjecture for strongly base-orderable matroids.

Recent results on RBC have focussed on finding a maximum number of disjoint
rainbow bases. In [3] it was recently shown that one can always find
$(\frac{1}{2}-o(1))n$ disjoint rainbow basis, which improved on a previous
bound of $\Omega(\frac{n}{\log n})$ by Dong and Geelen [6]. In light of this
result, a natural question to ask is, for what classes of matroids can one
improve the $(\frac{1}{2}-o(1))n$ bound to say $(1-o(1))n$? Using the method
of [3], it was shown in [8] that if $M$ is a rank-$n$ matroid having girth at
least $n-o(\sqrt{n})$, and no element of $M$ belongs to more than
$o(\sqrt{n})$ bases in $\mathcal{B}$, then one can find at least $n-o(n)$
disjoint rainbow bases with respect to $\mathcal{B}$. We mention also an
interesting recent result in [15] where it is shown that one can find at least
$n-o(n)$ disjoint rainbow independent sets of size at least $n-o(n).$

There are few classes of matroids for which RBC is known to be true or for
which one can construct $n-o(n)$ rainbow bases (for a matroid of rank $n$). In
this paper, we show that if the density of a rank-$n$ binary matroid is close
to one, then relative to $n$, one can find close to $n$ disjoint rainbow
bases. The main result of this paper is the following:

###### Theorem 1.2

Let $\mathcal{B}$ be a sequence of $n$ bases in a binary matroid of rank $n$
having $n+k$ elements. There exists a constant $b_{0}$ depending only on $k$
such that $t(\mathcal{B})\geq n-b_{0}.$

###  1.1 Overview of the proof

We will give a brief overview of the proof of Theorem 1.2. Let $M$ be a binary
matroid of rank $n$ where $\varepsilon(M)=|E(M)|=n+k.$ Let
$\mathcal{B}=(B_{1},\dots,B_{n})$ be a sequence of coloured bases of $M$. Let
$m=n+k$ and let $E(M)=\\{e_{1},\dots,e_{m}\\}.$ For an element $e\in E(M),$
let $v_{e}$ denote the corresponding vertex in $V$. For a subset $A\subseteq
E(M),$ let $V_{A}=\\{v_{e}\ \big{|}e\in A\\}.$

We shall define a bipartite graph $G=G(\mathcal{B})$ having bipartition
$(U,V)$ where $U=\\{u_{1},\dots,u_{n}\\}$, each vertex $u_{i}$ representing
$B_{i}$, and $V=\\{v_{1},\dots,v_{m}\\}$, each $v_{i}$ representing $e_{i}\in
E(M)$. For all $i,j$, $u_{i}$ and $v_{j}$ are joined by an edge in $G$ if and
only if $e_{j}\in B_{i}.$ Note that $d_{G}(u_{i})=n,\ i=1,\dots,n$ and
$d_{G}(v_{i})\leq n,\ i=1,\dots,n.$ We colour the edges of $G$ with colours
$1,2,\dots,n$ such that, for $i=1,\dots,n$, the edges incident to $u_{i}$
receive colour $i.$ A rainbow basis $B$ in $M$ corresponds to a matching $W$
in $G$ which saturates all vertices in $U$ and those elements in $V$ saturated
by $W$ correspond to $B$.

Suppose that $G$ can be partitioned into $n$ matchings $W_{1},\dots,W_{n}$,
where, for all $i$, $W_{i}$ corresponds to a rainbow basis of $M$. For
$i=1,\dots,n,$ let $G_{i}=G-W_{1}-\dots-W_{i}.$ Note that $G_{i}$ has maximum
degree $n-i$. Such a decomposition of $G$ into matchings $W_{1},\dots,W_{n}$
necessitates that the graph $G_{i}$ satisfy certain conditions. More
precisely, it can be shown that for every subset $A\subseteq E,$ the set
$V_{A}$ must satisfy the inequality $\sum_{v\in V_{A}}(n-i-d_{G_{i}}(v))\leq
r_{N}(A)(n-i)$, which we refer to as a deficit inequality for $A$ in $G_{i}.$

Suppose now that we have only constructed disjoint matchings
$W_{1},\dots,W_{p}$, each corresponding to rainbow basis. A key observation is
that if $G_{p}$ satisfies a deficit inequality for each $A\subseteq E,$ then
there exists a matching $W_{p+1}$ in $G_{p}$ corresponding to a rainbow basis.
Thus to guarantee that $G_{p}$ has such a matching it suffices to choose the
previous matchings $W_{1},\dots,W_{p}$ so that $G_{p}$ satisfies deficit
inequalities. This in itself is a daunting task. It turns out that if he
deficit inequalities hold for $G_{p-1}$ and $n-p$ is large enough, then one
can choose $W_{p}$ carefully so that the deficit inequalities hold for
$G_{p}$. At each step, we first choose $W_{p}$ corresponding to a rainbow
basis, and then we alter the matching $W_{p}$ by using sequences of
alternating paths with respect to $W_{p}$ in $G_{p-1}$ where one swaps the
matching edges on the paths with the non-matching edges. One of the challenges
is to alter the matchings so that the resulting matching corresponds to a
rainbow basis. Secondly, the new matching must improve on the previous
matching by reducing the number of deficit inequalities which are unsatisfied.
We show that this can be achieved by constructing a path-chain of alternating
paths. The existence of such path-chains will be dependent on $n-p$ being much
larger than $k.$ After each step $p$, the construction of the next matching
$W_{p+1}$ really only depends on the judicious selection of $W_{p}$ and as
such one can view the rainbow bases as being constructed one-at-a-time.

##  2 Notation

For a positive integer $k$, let $[k]$ denote the set $\\{1,\dots,k\\}$. For a
graph $G$, let $d_{G}(v)$ denote the degree of $v.$ for a subset $X\subseteq
V(G)$, let $\partial_{G}(X)$ denote the set of edges with one endpoint in $X$
and the other in $V(G)\backslash X.$ We let $d_{G}(X)=|\partial_{G}(X)|$. For
sets $X$ and $Y$ of vertices, we let $E_{G}(X,Y)$ denote the set of edges with
one endpoint in $X$ and the other in $Y$ and let $e_{G}(X,Y)=|E_{G}[X,Y]|.$
For a subset $X$ of vertices, let $N_{G}(X)$ denote the set of neighbours of
vertices in $X$ belonging to $V(G)\backslash X.$ For a set $Y\subset V(G)$, we
let $N_{G}(X,Y)=N_{G}(X)\cap Y.$

For a directed graph $\overrightarrow{D},$ we let
$N_{\overrightarrow{D}}^{+}(v)$ (resp. $N_{\overrightarrow{D}}^{-}(v)$) denote
the set of out-neighbours (resp. in-neighbours) of $v.$

For a set $X$, we let $\mathbf{1}_{X}$ denote the indicator function for $X.$

For a matroid $M$, we let $\varepsilon(M)=|E(M)|,$ the number of elements in
$M$. For a basis $B$ and element $e\in E(M)\backslash B,$ we let $C(e,B)$
denote the fundamental circuit with respect to $B$ in $B+e.$ For a subset
$A\subseteq E(M),$ we let $\overline{A}$ denote the set $E(M)\backslash A.$

In several places in the paper, we shall use the (easily proven) observation
that if $B$ is a basis in a matroid, $C^{*}$ is a cocircuit, and
$e\in\overline{B}$ is such that $(B+e)\cap C^{*}=\\{e,f\\},$ then $B-f+e$ is a
basis.

##  3 The deficit function

Let $M$ be a binary matroid of rank $n$ where $\varepsilon(M)=|E(M)|=n+k.$ Let
$\mathcal{B}=(B_{1},\dots,B_{n})$ be a sequence of coloured bases of $M$. Let
$m=n+k$ and let $E(M)=\\{e_{1},\dots,e_{m}\\}.$

We shall define a bipartite graph $G=G(\mathcal{B})$ having bipartition
$(U,V)$ where $U=\\{u_{1},\dots,u_{n}\\}$, each vertex $u_{i}$ representing
$B_{i}$, and $V=\\{v_{1},\dots,v_{m}\\}$, each $v_{i}$ representing $e_{i}\in
E(M)$. For all $i,j$, $u_{i}$ and $v_{j}$ are joined by an edge in $G$ if and
only if $e_{j}\in B_{i}.$ Note that $d_{G}(u_{i})=n,\ i=1,\dots,n$ and
$d_{G}(v_{i})\leq n,\ i=1,\dots,n.$ We colour the edges of $G$ with colours
$1,2,\dots,n$ such that, for $i=1,\dots,n$, the edges incident to $u_{i}$
receive colour $i.$ A rainbow basis $B$ corresponds to a matching in $G$ which
saturates $U$ and the those elements in $V$ corresponding to $B$.

For a subset of edges $A\subseteq E(G)$, let $U_{A}\subseteq U$ (respectively,
$V_{A}\subseteq V$) denote the set of endvertices of edges in $A$ belonging to
$U$ (respectively, $V$). For all vertices $v\in V,$ let $e_{v}$ denote the
corresponding element in $E(M)$, noting that $e_{i}=e_{v_{i}}.$ For a subset
$Y\subseteq V,$ let $E_{Y}=\\{e_{v}\ \big{|}\ v\in Y\\}.$ For convenience, if
$A\subseteq E(G),$ then we let $E_{A}=E_{V_{A}}.$ For an element $e\in E(M),$
let $v_{e}$ denote the corresponding vertex in $V$, noting that
$v_{i}=v_{e_{i}}.$ For a subset $A\subseteq E(M),$ let $V_{A}=\\{v_{e}\
\big{|}e\in A\\}.$

  * Definition:

For a graph $H$ of maximum degree $d$, we define the $\mathbf{H}$-deficit of a
vertex $v$ to be $\delta_{H}(v):=d-d_{H}(v).$ For a subset $X\subseteq V(H)$,
we define the $H$-deficit of $X$ to be $\delta(X):=\sum_{x\in X}\delta(x).$ We
define the deficit of $H$ to be $\delta(H):=\delta(V(G)).$

Suppose that $G$ can be partitioned into $n$ matchings $W_{1},\dots,W_{n}$,
where, for all $i$, $E_{W_{i}}$ is a basis of $M$; that is, $E_{W_{i}}$ is a
rainbow basis. For $i=1,\dots,n,$ let $G_{i}=G-W_{1}-\dots-W_{i}.$ For
convenience, we let $\delta_{i}$ denote the deficit function $\delta_{G_{i}}$
and we let $d_{i}(v)=d_{G_{i}}(v).$ Note that $G_{i}$ has maximum degree
$n-i$.

###### Lemma 3.1

The deficit of $G_{i}$ equals $k(n-i).$

  * Proof:

We have

$\displaystyle\delta(G_{i})$ $\displaystyle=\sum_{v\in
V}\delta_{i}(v)=\sum_{v\in V}(n-i-d_{i}(v))=(n+k)(n-i)-\sum_{v\in V}d_{i}(v)$
$\displaystyle=(n+k)(n-i)-|E(G_{i})|=(n+k)(n-i)-(n^{2}-ni)=k(n-i).$

$\square$

###### Lemma 3.2

Let $V^{\prime}\subseteq V.$ Then $|V_{W_{i+1}}\cap
V^{\prime}|=|V^{\prime}|-\alpha$ if and only if
$\delta_{i+1}(V^{\prime})=\delta_{i}(V^{\prime})-\alpha.$

  * Proof:

Suppose $|V_{W_{i+1}}\cap V^{\prime}|=|V^{\prime}|-\alpha$. Then

$\displaystyle\delta_{i+1}(V^{\prime})$ $\displaystyle=\sum_{v\in
V^{\prime}}((n-i-1)-d_{i+1}(v))=(n-i-1)|V^{\prime}|-\sum_{v\in
V^{\prime}}d_{i+1}(v)$ $\displaystyle=(n-i-1)|V^{\prime}|-\sum_{v\in
V^{\prime}}d_{i}(v)+(|V^{\prime}|-\alpha))=(n-i)|V^{\prime}|-\sum_{v\in
V^{\prime}}d_{i}(v)-\alpha$ $\displaystyle=\delta_{i}(V^{\prime})-\alpha.$

The above also shows that if
$\delta_{i+1}(V^{\prime})=\delta_{i}(V^{\prime})-\alpha,$ then
$|V_{W_{i+1}}\cap V^{\prime}|=|V^{\prime}|-\alpha$. $\square$

##  4 The Matroid $N$

We may assume that $B^{*}=\\{e_{1},\dots,e_{n}\\}$ is a base in $M$. For
$i=1,\dots,k$, let $C_{i}=C(e_{k+i},B^{*})$ be the fundamental circuit with
respect to $B^{*}$ which contains $e_{k+i}.$ The circuits $C_{i},\
i=1,\dots,k$ form a basis for the circuit space of $M.$ We define a surjection
$\psi_{E}:E\rightarrow\mathbb{Z}_{2}^{k}$ where
$\psi_{E}(e)=(\varepsilon_{1},\dots,\varepsilon_{k}),$
$\varepsilon_{i}\in\\{0,1\\}$, and $\varepsilon_{i}=1$ if and only if $e\in
C_{i}.$ Let $\psi_{V}:V\rightarrow\mathbb{Z}_{2}^{k}$ where
$\psi_{V}(v)=\psi_{E}(e_{v}).$

  * Definition:

The matroid $N$ is the vector matroid consisting of vectors
$\psi_{E}(e)=(\varepsilon_{1},\dots,\varepsilon_{k})\in\mathbb{Z}_{2}^{k},\
e\in E$; that is, $N$ is a sub-matroid of the projective geometry $PG(k-1,2)$
plus a loop (corresponding to $\mathbf{0}$).

For $a=(\varepsilon_{1},\dots,\varepsilon_{k})\in E(N)$, let
$V_{a}=\psi_{V}^{-1}(a)$ and let $E_{a}=\psi_{E}^{-1}(a).$ For any subset
$F\subseteq E(N)$, let $V_{F}=\psi_{V}^{-1}(F)$ and let
$E_{F}=\psi_{E}^{-1}(F).$ Note that for each circuit $C_{i}$ in $M$,
$C_{i}^{*}=\psi_{E}(C_{i})$ is a cocircuit in $N$ for which
$\psi_{E}^{-1}(C_{i}^{*})=C_{i}.$ This is because for each circuit $C_{i}$,
$E(N)\backslash\psi_{E}(C_{i})=\\{(\varepsilon_{1},\dots,\varepsilon_{k})\in
E(N)\\}\ \big{|}\ \varepsilon_{i}=0\\},$ is a hyperplane in $N.$ The
cocircuits $C_{i}^{*},\ i=1,\dots,k$ are seen to form a basis for the
cocircuit space of $N.$ Thus for each circuit $C$ in $M$, the set
$C^{*}=\psi_{E}(C)$ is seen to be a cocircuit in $N$ where
$C=\psi_{E}^{-1}(C^{*}).$ Conversely, for each cocircuit $C^{*}$ in $N,$
$\psi_{E}^{-1}(C^{*})$ is a circuit in $M.$ Summarizing,

###### Observation 4.1

$C$ is a circuit in $M$ if and only if $\psi_{E}(C)$ is a cocircuit in $N.$
Conversely, $C^{*}$ is a cocircuit in $N$ if and only if
$\psi_{E}^{-1}(C^{*})$ is a circuit in $M$.

The above leads to the following observation:

###### Lemma 4.2

A subset $B\subseteq E(M)$ is a basis in $M$ if and only if
$\psi_{E}(E(M)\backslash B)$ is a basis in $N.$

  * Proof:

Let $B\subseteq E(M)$ where $|B|=n.$ Let $F=\psi_{E}(E(M)\backslash B).$ Then
$|F|\leq k$ since $|E(M)\backslash B|=k.$ Suppose that $B$ is a basis in $M.$
If $r_{N}(F)<r(N)=k,$ then $F$ is contained in a hyperplane $H$ in $N.$ Thus
$\psi_{E}^{-1}(E(N)\backslash H)\subseteq B.$ But $E(N)\backslash H$ is a
cocircuit in $N$ and hence by Observation 4.1, $\psi_{E}^{-1}(E(N)\backslash
H)$ is circuit in $M.$ This is impossible since $B$ contains no circuits. Thus
$r_{N}(F)=k$ and hence $F$ is a basis in $N.$

On the other hand, if $B$ is not a basis, then $B$ contains a circuit $C$. By
Observation 4.1, $C^{*}=\psi_{E}(C)$ is a cocircuit where
$\psi_{E}^{-1}(C^{*})=C.$ Thus $F\cap C^{*}=\emptyset$ and $F$ is contained in
some hyperplane of $N$. It follows that $F$ is not a basis of $N.$ $\square$

###### Lemma 4.3

For a subset $X\subseteq E(M)$ we have $r(X)=n-|E-X|+r_{N}(\psi_{E}(E-X)).$

  * Proof:

Let $X\subseteq E(M).$ Let $A^{\prime}\subseteq\psi_{E}(E-X)$ be an
independent set of $N$ of size $r_{N}(\psi_{E}(E-X)).$ Let $A$ be a basis of
$N$ containing $A^{\prime}.$ Let
$Y^{\prime}\subset\psi_{E}^{-1}(A^{\prime})\cap(E-X)$ be such that
$\psi_{E}(Y^{\prime})=A^{\prime}$ and let
$Y^{\prime\prime}\subseteq\psi_{E}^{-1}(A-A^{\prime})$ be such that
$\psi_{E}(Y^{\prime\prime})=A-A^{\prime}.$ Then for $Y=Y^{\prime}\cup
Y^{\prime\prime},$ we have $\psi_{E}(Y)=A$ and hence by Observation 4.2, $E-Y$
is a basis of $M.$ We have that $|Y|=|A|=k$ and hence
$|Y^{\prime}|=|A^{\prime}|$ and $|Y^{\prime\prime}|=|A-A^{\prime}|.$ Thus
$|X\cap Y|=|Y^{\prime\prime}|=k-|Y^{\prime}|=k-r_{N}(\psi_{E}(E-X)).$ We see
that $X-Y^{\prime\prime}\subseteq E-Y$ and hence

$r(X)\geq|X|-|Y^{\prime\prime}|=|X|-k+r_{N}(\psi_{E}(E-X))=n+k-|E-X|-k+r_{N}(\psi_{E}(E-X))=n-|E-X|+r_{N}(\psi_{E}(E-X)).$

Suppose on the other hand that $B$ is a basis in $M$ for which $|B\cap
X|=r(X)$. We have that $\psi_{E}(E-B)$ is a basis in $N$. Let
$A^{\prime}=\psi_{E}(E-B)\cap\psi_{E}(E-X)$. Then $A^{\prime}$ is independent
and $|A^{\prime}|\leq r_{N}(\psi_{E}(E-X)).$ We have
$r_{N}(\psi_{E}(E-X))+r_{N}(\psi_{E}(X-B))\geq k$ and hence
$r_{N}(\psi_{E}(E-X))+|X-B|\geq k.$ Thus $|X-B|\geq k-r_{N}(\psi_{E}(E-X))$
and hence $r(X)=|X\cap
B|\leq|X|-(k-r_{N}(\psi_{E}(E-X)))=n-|E-X|+r_{N}(\psi_{E}(E-X)).$ $\square$

###  4.1 Necessary conditions for the existence of $n$ rainbow bases

The existence of $n$ disjoint rainbow bases necessitates that $N$ satisfy
certain conditions. These are given below in Lemma 4.4. Suppose $G$ has a
decomposition into matchings $W_{1},\dots,W_{n}$, where $E_{W_{i}},\ i\in[n],$
is a basis in $M.$ Let $G_{p}$ be the graph obtained from $G$ by removing
$W_{1},\dots,W_{p}.$ To each element $e\in E(M)$, we define the deficit
$\delta_{p}(e):=\delta_{p}(v_{e})$ and to each $a\in E(N),$ we define
$\delta_{p}(a):=\delta_{p}(V_{a}).$

For the remainder of the paper, we define $\eta:=n-p.$

###### Lemma 4.4

For all $e\in E(M),\ \delta_{p}(e)\geq 0,$ and for all flats $F$ in $N$ we
have $\delta_{p}(F)\leq r_{N}(F)\eta.$

  * Proof:

Since the maximum degree of $G_{p}$ equals $\eta$, it follows that
$\delta_{p}(e)\geq 0$ for all elements $e\in E(M).$ For each matching $W_{i},\
i=p+1,\dots,n$, we have $\psi_{V}(\overline{V}_{W_{i}})$ is a basis of $N$ (by
Lemma 4.2). Thus for all flats $F$ in $N,$ $|\overline{V}_{W_{i}}\cap
V_{F}|\leq r_{N}(F)$ since $\psi_{V}(\overline{V}_{W_{i}}\cap V_{F})\subseteq
F$ is independent in $N.$ It follows that $|V_{W_{i}}\cap
V_{F}|\geq|V_{F}|-r_{N}(F).$ Therefore, by Lemma 3.2,
$\delta_{i}(V_{F})\geq\delta_{i-1}(V_{F})-r_{N}(F)$ and consequently,
$\delta_{i}(F)\geq\delta_{i-1}(F)-r_{N}(F),\ i=p+1,\dots,n.$ Thus
$0=\delta_{n}(F)\geq\delta_{p}(F)-r_{N}(F)\eta$ and hence $\delta_{p}(F)\leq
r_{N}(F)\eta.$ $\square$

##  5 Finding a rainbow basis

In this section, we will assume that only matchings $W_{1},\dots,W_{p}$ have
been constructed, where $E(W_{i})$ is a basis, for $i=1,\dots,p.$ As before,
$\eta=n-p.$ In addition, we shall assume the matchings $W_{1},\dots,W_{p}$ are
constructed such that $\forall e\in E(M),\ \delta_{p}(e)\geq 0$ and for each
flat $F$ in $N$, the following deficit inequality holds for for each flat $F$:

$\delta_{p}(F)\leq r_{N}(F)\eta$

We shall prove the following key lemma:

###### Lemma 5.1

If $p\geq 1$, $\delta_{p}(e)\geq 0,\ \forall e\in E(M)$ and (5) holds for all
flats $F$ in $N$, then there exists a matching $W_{p+1}$ in $G_{p}$ for which
$E_{W_{p+1}}$ is a basis of $M.$

Let $H$ be a bipartite graph with bipartition $(X,Y).$ For a subset
$X^{\prime}\subseteq X,$ we define

$def_{H}(X^{\prime})=\max\\{0,|X^{\prime}|-|N_{H}(X^{\prime})|\\}.$

Let $\mu(H)$ be the size of a maximum matching in $H$. We have the König-Ore
formula for $\mu(H)$ (see [12, Theorem 1.2,5]):

$\mu(H)=|X|-\max_{X^{\prime}\subseteq X}def_{H}(X^{\prime})$

To prove the above lemma, we shall use the well-known matroid intersection
theorem of Edmonds [14, Theorem 12.3.15]:

###### Theorem 5.2

Let $M_{1}$ and $M_{2}$ be matroids on a common set $S$ having rank functions
$r_{1}$ and $r_{2}.$ Then the maximum size of an independent set common to
both matroids is equal to

$\min_{A\subseteq S}r_{1}(A)+r_{2}(S-A).$

Let $M_{1}$ be a transversal matroid defined on $E$ where a subset $A\subseteq
E$ is independent if and only if there is a matching in $G_{p}$ from $V_{A}$
to $U$. Let $r_{1}$ be the rank function for $M_{1}.$ Let $A\subseteq E.$
Since the maximum vertex degree in $G_{p}$ equals $\eta$, it follows that

$|N_{G_{p}}(V_{A})|\geq\frac{d_{p}(V_{A})}{\eta}=\frac{\sum_{v\in
V_{A}}(\eta-\delta_{p}(v))}{\eta}=\frac{\eta|A|-\delta_{p}(A)}{\eta}=|A|-\frac{\delta_{p}(A)}{\eta}.$

Thus $def_{G_{p}}(V_{A})\leq\frac{\delta_{p}(A)}{\eta}.$ In calculating
$r_{1}(A)$, let $H$ be the bipartite subgraph of $G_{p}$ having bipartition
$(U,V_{A}).$ Then by (5) we obtain

$\displaystyle r_{1}(A)$
$\displaystyle=\mu(H)=|V_{A}|-\max_{A^{\prime}\subseteq
A}def_{H}(V_{A^{\prime}})$ $\displaystyle\geq|V_{A}|-\max_{A^{\prime}\subseteq
A}\frac{\delta_{p}(A^{\prime})}{\eta}\geq|A|-\frac{\delta_{p}(A)}{\eta}.$

The second inequality holds because $\delta_{p}$ is nonnegative function and
as such, $\delta_{p}(A^{\prime})\leq\delta_{p}(A)$ when $A^{\prime}\subseteq
A.$ Thus for all $A\subseteq E,$

$r_{1}(A)\geq|A|-\frac{\delta_{p}(A)}{\eta}$

###  5.1 Proof of Lemma 5.1

Let $M_{1}$ be defined as before and let $M_{2}=M$ and let $r_{2}$ be the rank
function $r.$ Let $A\subseteq E$. By Lemma 4.3, it follows that
$r_{2}(E-A)=n-|A|+r_{N}(\psi_{E}(A)).$ Now by (5),

$\displaystyle r_{1}(A)+r_{2}(E-A)$
$\displaystyle\geq|A|-\frac{\delta_{p}(A)}{\eta}+n-|A|+r_{N}(\psi_{E}(A))$
$\displaystyle=n-\frac{\delta_{p}(A)}{\eta}+r_{N}(\psi_{E}(A))$

By (5), it follows that $\delta_{p}(A)\leq r_{N}(\psi_{E}(A))\eta,$ and thus
$\frac{\delta_{p}(A)}{\eta}\leq r_{N}(\psi_{E}(A)).$ Thus from the above we
obtain that $r_{1}(A)+r_{2}(E-A)\geq n.$ It now follows from Theorem 5.2 that
$M_{1}$ and $M_{2}$ have a common basis $B$. This completes the proof of the
lemma.

##  6 Alternating paths

We shall assume $\forall e\in E,$ $\delta_{p}(e)\geq 0$ and for all flats $F$
in $N$, (5) holds. By Lemma 5.1, one can find a matching $W=W_{p+1}$ in
$G_{p}$ for which $E_{W_{p+1}}$ is a basis. Our strategy is show that,
provided $\eta$ is large enough, one can alter $W$ using alternating paths in
such a way that when we delete it from $G_{p}$, the resulting graph $G_{p+1}$
will also be such that $\forall e\in E(M),\ \delta_{p+1}(e)\geq 0$ and for all
flats $F$ in $N$, $\delta_{p+1}(F)\leq r_{N}(F)(\eta-1).$ It will then follow
by Lemma 5.1 that $G_{p+1}$ has a matching $W_{p+2}$ for which $E_{W_{p+2}}$
is a basis. The process then continues with $W_{p+2}$ in place of $W_{p+1}.$

Let $A=\psi_{E}(E-E_{W})=\psi_{V}(\overline{V}_{W})$, which (by Lemma 4.2) is
a basis in $N.$ It follows by Lemma 3.2 that for all flats $F$ in $N,$

$\delta_{p+1}(F)=\delta_{p}(F)-\nu\ \Longleftrightarrow\
|\overline{V}_{W}\cap\psi_{V}^{-1}(F)|=\nu.$

In particular, to insure that for all flats $F$ in $N$, $\delta_{p+1}(F)\leq
r_{N}(F)(\eta-1),$ it suffices to insure that
$|\overline{V}_{W}\cap\psi_{V}^{-1}(F)|\geq\delta_{p}(F)-r_{N}(F)(\eta-1).$
Noting that $|\overline{V}_{W}\cap\psi_{V}^{-1}(F)|=|A\cap F|$, this condition
is equivalent to insuring that for all flats $F$,

$|A\cap F|\geq\delta_{p}(F)-r_{N}(F)(\eta-1).$

Given a set of edges $X$ forming a matching in a bipartite graph, an
alternating path with respect to $X$ is a path $P$ whose edges alternate
between matching edges and non-matching edges. If the terminal vertices of $P$
are vertices unsaturated by the matching, then one can change the matching $X$
by deleting from it matching edges belonging to $P$, and adding to it, the
non-matching edges in $P$. The resulting set of edges $X^{\prime}$ is a
matching where $|X^{\prime}|=|X|+1.$ For this reason, we call $P$ an
augmenting path with respect to $X.$

Let $W$ be a matching in $G_{p}$ where $E_{W}$ is a basis. For a subset
$Y\subseteq V_{W},$ we let $U_{W,Y}$ denote the set of vertices in $U$ which
are reachable by an alternating path originating at some vertex in $Y$ where
the first edge of the path is in $W.$

###### Lemma 6.1

$e_{p}(U_{W,Y},\overline{V}_{W})\geq\delta_{p}(Y).$

  * Proof:

Let $Y^{\prime}$ be the set of vertices in $V_{W}$ matched to vertices in
$U_{W,Y},$ noting that $|Y^{\prime}|=|U_{W,Y}|.$ Then

$\displaystyle\eta|U_{W,Y}|$
$\displaystyle=d_{p}(U_{W,Y})=e_{p}(U_{W,Y},Y^{\prime}\cup\overline{V}_{W})=e_{p}(U_{W,Y},Y^{\prime})+e_{p}(U_{W,Y},\overline{V}_{W})$
$\displaystyle\leq d_{p}(Y^{\prime})+e_{p}(U_{W,Y},\overline{V}_{W})$
$\displaystyle=|Y^{\prime}|\eta-\delta_{p}(Y^{\prime})+e_{p}(U_{W,Y},\overline{V}_{W})$
$\displaystyle=|U_{W,Y}|\eta-\delta_{p}(Y^{\prime})+e_{p}(U_{W,Y},\overline{V}_{W})$

From the above, we see that
$e_{p}(U_{W,Y},\overline{V}_{W})\geq\delta_{p}(Y^{\prime})\geq\delta_{p}(Y).$
$\square$

  * Definition:

For a subset $Y\subseteq V,$ let $\widetilde{Y}=Y\backslash\overline{V}_{W}.$
An alternating path with respect to $W$ in $G_{p}$ which originates in
$\overline{V}_{W}$ and terminates in $\widetilde{Y}$ is called a
$\mathbf{Y}$-path with respect to $W$.

###### Lemma 6.2

Let $Y\subseteq V.$ There are at least
$\big{\lceil}\frac{\delta_{p}(\widetilde{Y})}{\eta}\big{\rceil}$ vertices
$v\in\overline{V}_{W}$ for which there is a $Y$-path originating at $v.$

  * Proof:

By Lemma 6.1,
$e_{p}(U_{W,\widetilde{Y}},\overline{V}_{W})\geq\delta_{p}(\widetilde{Y}).$
Given that each vertex in $\overline{V}_{W}$ has degree at most $\eta$, there
are at least $\big{\lceil}\frac{\delta_{p}(\widetilde{Y})}{\eta}\big{\rceil}$
vertices in $\overline{V}_{W}$ which are neighbours of vertices in
$U_{W,\widetilde{Y}}.$ If $v\in\overline{V}_{W}$ is a neighbour of
$U_{W,\widetilde{Y}}$, then it is the terminal vertex of a $Y$-path. $\square$

###### Lemma 6.3

Let $Y\subseteq V$ and suppose $Y^{\prime}\subset\overline{V}_{W}$ is such
that $\delta_{p}(\widetilde{Y})>i\eta+d_{p}(Y^{\prime})$. Then there are at
least $i+1$ vertices $v$ in $\overline{V}_{W}-Y^{\prime}$ which are terminal
vertices of some $Y$-path.

  * Proof:

It follows by Lemma 6.1 that
$e_{p}(U_{W,\widetilde{Y}},\overline{V}_{W})\geq\delta_{p}(\widetilde{Y})>i\eta+d_{p}(Y^{\prime})$.
Thus it follows that there are at least
$\left\lceil\frac{i\eta+1}{\eta}\right\rceil=i+1$ vertices in
$N_{p}(U_{W,\widetilde{Y}},\overline{V}_{W}-Y^{\prime}).$ This in turn implies
that there are at least $i+1$ vertices $v$ in $\overline{V}_{W}-Y^{\prime}$
for which there is a $Y$-path originating at $v.$ $\square$

###### Lemma 6.4

Let $Y\subseteq V$ and suppose that $|Y\cap\overline{V}_{W}|=s.$ If
$\delta_{p}(Y)\geq\ell+s\eta,$ then

$\delta_{p}(\widetilde{Y})\geq\ell+\sum_{y_{i}\in
Y\cap\overline{V}_{W}}d_{p}(y_{i}).$

Furthermore, there exist at least $\lceil\frac{\ell}{\eta}\rceil$ vertices
$v\in\overline{V}_{W}-Y$ for which there is a $Y$-path originating at $v.$

  * Proof:

Since $\delta_{p}(Y)\geq\ell+s\eta,$ we have

$\displaystyle\delta_{p}(Y)$
$\displaystyle=\delta_{p}(\widetilde{Y})+\delta_{p}(Y\cap\overline{V}_{W})\geq\ell+s\eta$
$\displaystyle\delta_{p}(\widetilde{Y})$
$\displaystyle\geq\ell+s\eta-\delta_{p}(Y\cap\overline{V}_{W})$
$\displaystyle=\ell+s\eta-\sum_{y_{i}\in Y\cap\overline{V}_{W}}(\eta-
d_{p}(y_{i}))$ $\displaystyle=\ell+\sum_{y_{i}\in
Y\cap\overline{V}_{W}}d_{p}(y_{i}).$

It now follows by Lemma 6.3 that there are at least
$\lceil\frac{\ell}{\eta}\rceil$ vertices
$v\in\overline{V}_{W}-(Y\cap\overline{V}_{W})$ for which there is a
$\widetilde{Y}$-path originating at $v.$ $\square$

If there is an alternating path $P$ with respect to $W$ which originates a
vertex $z_{1}\in\overline{V}_{W}$ and terminates at a vertex
$z_{1}^{\prime}\in V_{W}$, then we write
$z_{1}\xrightarrow[W]{P}z_{1}^{\prime}.$ We will simply write
$z_{1}\xrightarrow[W]{}z_{1}^{\prime}$, if
$z_{1}\xrightarrow[W]{P}z_{1}^{\prime},$ for some alternating path $P.$ The
next observation is an easily proven property of alternating paths.

###### Observation 6.5

Suppose $z_{1}\xrightarrow[W]{P_{1}}z_{1}^{\prime}$ and
$z_{2}\xrightarrow[W]{P_{2}}z_{2}^{\prime}.$ If $V(P_{1})\cap
V(P_{2})\neq\emptyset,$ then $z_{1}\xrightarrow[W]{}z_{2}^{\prime}$ and
$z_{2}\xrightarrow[W]{}z_{1}^{\prime}.$

##  7 The set of flats $\mathfrak{F}$

Let $W$ be a matching in $G_{p}$ for which $E_{W}$ is a basis and let
$\overline{V}_{W}=\\{y_{1},\dots,y_{k}\\}$ . For all $i\in[k],$ let
$a_{i}=\psi_{V}(y_{i})$ and let $A=\\{a_{1},\dots,a_{k}\\},$ which is a basis
in $N$. We shall assume that for all flats $F$ in $N$, $\delta_{p}(F)\leq
r_{N}(F)\eta.$ Our primary goal is to show that $W$ can be chosen so that for
all flats $F$ in $N$, (6) holds. When $\delta_{p}(F)\leq r_{N}(F)(\eta-1),$
this inequality automatically holds and thus the focus will be on the flats
$F$ where $\delta_{p}(F)>r_{N}(F)(\eta-1).$

  * Definition:

For all $i\in[k]$ let $H_{i}$ be the hyperplane in $N$, where
$H_{i}=\mathrm{cl}_{N}(A-a_{i})$, and let $C_{i}^{*}=\overline{H}_{i},$ which
is a cocircuit in $N$ containing $a_{i}.$ For all $i\in[k]$, let
$Z_{i}=\psi_{V}^{-1}(C_{i}^{*}).$

For $\\{i_{1},i_{2},\dots,i_{s}\\}\subseteq[k]$ we have that $N_{i_{1}\cdots
i_{s}}=H_{i_{1}}\cap H_{i_{2}}\cap\cdots\cap
H_{i_{s}}=\mathrm{cl}_{N}(A-\\{a_{i_{1}},\dots,a_{i_{s}}\\})$ is a
rank-$(k-s)$ flat in $N.$ By assumption, $\delta_{p}(N_{i_{1}\cdots
i_{s}})\leq(k-s)\eta.$ Thus
$\delta_{p}\left(\bigcup_{j=1}^{s}C_{i_{j}}^{*}\right)=\delta_{p}(\overline{N_{i_{1}\cdots
i_{s}}})\geq s\eta.$

  * Definition:

Let $\mathcal{F}$ be the set all flats $F$ in $N$ for which
$\delta_{p}(F)>r_{N}(F)(\eta-1)$ and let $\mathfrak{F}$ denote the set of all
flats in $N$ which can be expressed as a finite intersection of flats in
$\mathcal{F}.$

We note that $N\in\mathcal{F}$ and $\mathcal{F}\subseteq\mathfrak{F}$.
Furthermore, $\mathfrak{F}$ is closed under intersections.

  * Definition:

For all $i\in[k]$, there is a unique flat in $\mathfrak{F}$ of least rank
which contains $a_{i}.$ We shall denote such a flat by $F_{i}.$ Furthermore,
we let $F_{i}^{\prime}=H_{i}\cap F_{i}$ and
$F_{i}^{\prime\prime}=F_{i}-F_{i}^{\prime}=C_{i}^{*}\cap F_{i}.$

  * Definition:

For a subset $F\subseteq E(N)$, we define $\omega_{W}(F):=|A\cap F|.$

We shall show that, provided $\eta$ is large enough, one can alter the
matching $W$, obtaining a matching $W^{\prime}$ for which $E_{W^{\prime}}$ is
a basis and for all flats $F\in\mathfrak{F}$ in $N,$
$\omega_{W^{\prime}}(F)=r_{N}(F).$ This in turn will imply that (6) holds for
all flats $F$ in $N.$

  * Definition:

For all flats $F$ in $N$, we define $F_{A}:=\mathrm{cl}_{N}(F\cap A).$

We note that $r_{N}(F_{A})=\omega_{W}(F).$

###### Lemma 7.1

Suppose that $Q_{i},\ i\in[s],$ are flats in $N$ where for all $i\in[s],$
$\delta_{p}(Q_{i})=r_{N}(Q_{i})\eta-j_{i}.$ Then
$\delta_{p}\left(\bigcap_{i=1}^{s}Q_{i}\right)\geq
r_{N}\left(\bigcap_{i=1}^{s}Q_{i}\right)\eta-j_{1}-j_{2}-\cdots-j_{s}.$

  * Proof:

Using the fact that $r_{N}$ is a submodular function, we have

$\displaystyle\delta_{p}(Q_{1}\cap Q_{2})$
$\displaystyle=\delta_{p}(Q_{1})+\delta_{p}(Q_{2})-\delta_{p}(Q_{1}\cup
Q_{2})$ $\displaystyle=r_{N}(Q_{1})\eta-j_{1}+r_{N}(Q_{2})\eta-
j_{2}-\delta_{p}(Q_{1}\cup Q_{2})$
$\displaystyle\leq(r_{N}(Q_{1})+r_{N}(Q_{2}))\eta-j_{1}-j_{2}-r_{N}(Q_{1}\cup
Q_{2})\eta$ $\displaystyle=(r_{N}(Q_{1})+r_{N}(Q_{2})-r_{N}(Q_{1}\cup
Q_{2}))\eta-j_{1}-j_{2}$ $\displaystyle\geq r_{N}(Q_{1}\cap Q_{2})\eta-
j_{1}-j_{2}.$

It is now easily proven by induction that $\delta_{p}(Q_{1}\cap
Q_{2}\cap\cdots\cap Q_{s})\geq r_{N}(Q_{1}\cap Q_{2}\cap\cdots\cap Q_{s})\eta-
j_{1}-j_{2}-\cdots-j_{s}.$ $\square$

###### Lemma 7.2

There is a constant $c_{0}$ depending only on $k$ such that for all
$F\in\mathfrak{F},$ $\delta_{p}(F)\geq r_{N}(F)\eta-c_{0}$.

  * Proof:

By the definition of $\mathcal{F}$, we have for all $F\in\mathcal{F}$,
$\delta_{p}(F)>r_{N}(F)(\eta-1)\geq r_{N}(F)\eta-k$. Given that $\mathcal{F}$
contains at most $2^{2^{k}}$ flats and $\mathfrak{F}$ consists of flats which
are finite intersections of flats in $\mathcal{F},$ it follows by Lemma 7.1
that for all $F\in\mathfrak{F},$ $\delta_{p}(F)\geq
r_{N}(F)\eta-k2^{2^{2^{k}}}.$ Thus taking $c_{0}=k2^{2^{2^{k}}}$ will suffice.
$\square$

###### Lemma 7.3

For all $i\in[k]$, $\delta_{p}(F_{i}^{\prime\prime})\geq\eta-c_{0}.$

  * Proof:

We have that

$\displaystyle\delta_{p}(F_{i}^{\prime\prime})$
$\displaystyle=\delta_{p}(F_{i})-\delta_{p}(F_{i}^{\prime})\geq
r_{N}(F_{i})\eta-c_{0}-r_{N}(F_{i}^{\prime})\eta$ $\displaystyle\geq
r_{N}(F_{i})\eta-c_{0}-(r_{N}(F_{i})-1)\eta$ $\displaystyle=\eta-c_{0}$

$\square$

###### Lemma 7.4

Let $A^{\prime}\subseteq A$ where for all $a_{i},a_{j}\in A^{\prime}$,
$F_{i}=F_{j}.$ Then $\delta_{p}\left(\bigcup_{a_{i}\in
A^{\prime}}F_{i}^{\prime\prime}\right)\geq|A^{\prime}|\eta-c_{0}.$

  * Proof:

Let $F\in\mathfrak{F}$ be the flat for which $F=F_{i}$, for all $a_{i}\in
A^{\prime}.$ Let $F^{\prime}=F\cap\bigcap_{a_{i}\in A^{\prime}}H_{i}.$ Then we
have

$\displaystyle\delta_{p}\left(\bigcup_{a_{i}\in
A^{\prime}}F_{i}^{\prime\prime}\right)$
$\displaystyle=\delta_{p}(F)-\delta_{p}(F^{\prime})$ $\displaystyle\geq
r_{N}(F)\eta-c_{0}-r_{N}(F^{\prime})\eta$ $\displaystyle\geq r_{N}(F)\eta-
c_{0}-(r_{N}(F)-|A^{\prime}|)\eta$ $\displaystyle=|A^{\prime}|\eta-c_{0}.$

$\square$

###### Lemma 7.5

Let $A^{\prime}\subseteq A,$ where for all $a_{i}\in A^{\prime},$
$\omega_{W}(F_{i})=r_{N}(F_{i}).$ Then there is a constant $c_{1}$ depending
only on $k$ such that $\delta_{p}\left(\bigcup_{a_{i}\in
A^{\prime}}F_{i}^{\prime\prime}\right)\geq|A^{\prime}|\eta-c_{1}.$

  * Proof:

We first observe that for all $a_{i},a_{j}\in A^{\prime},$ if
$F_{i}^{\prime\prime}\cap F_{j}^{\prime\prime}\neq\emptyset,$ then
$F_{i}=F_{j}.$ Defining an equivalence relation on $A^{\prime}$ where
$a_{i}\sim a_{j}$ if and only if $F_{i}=F_{j}$, let
$A_{1}^{\prime},\dots,A_{s}^{\prime}$ be the equivalence classes. Then we have
by Lemma 7.3,

$\displaystyle\delta_{p}\left(\bigcup_{a_{i}\in
A^{\prime}}F_{i}^{\prime\prime}\right)$
$\displaystyle=\sum_{i=1}^{s}\delta_{p}\left(\bigcup_{a_{j}\in
A_{j}^{\prime}}F_{i}^{\prime\prime}\right)$
$\displaystyle\geq\sum_{i=1}^{s}(|A_{i}^{\prime}|\eta-c_{0})$
$\displaystyle=|A^{\prime}|\eta-sc_{0}\geq|A^{\prime}|\eta-kc_{0}.$

Thus $c_{1}=kc_{0}$ will suffice. $\square$

##  8 Path-tangles and path-chains

To show that $W$ can be chosen so that (6) holds for all flats $F$ in $N,$ it
will suffice to show that $W$ can be chosen so that for all
$F\in\mathfrak{F},$ $\omega_{W}(F)=r_{N}(F).$ This can be achieved by changing
$W$ incrementally using sequences of alternating paths in $G_{p}$ which we
refer to as path-chains.

Recall that $\overline{V}_{W}=\\{y_{1},\dots,y_{k}\\}$,
$\psi_{V}(\overline{V}_{W})=A=\\{a_{1},\dots,a_{k}\\}$ (a basis for $N$) and
for $i\in[k],$ $F_{i}^{\prime}=H_{i}\cap F_{i}$,
$F_{i}^{\prime\prime}=F_{i}-F_{i}^{\prime},$ $C_{i}^{*}=\overline{H}_{i}$, and
$Z_{i}=\psi_{V}^{-1}(C_{i}^{*}).$ Let $A_{0}\subseteq E(N)-A$ and
$Y_{0}=\psi_{V}^{-1}(A_{0}).$

  * Definition:

For a positive integer $t,$ let $\beta:[t]\rightarrow[k]$ be a function and
suppose $P_{1},\dots,P_{t}$ are alternating paths with respect to $W$
originating in $\overline{V}_{W}$ and terminating in $V_{W}.$ The $t$-tuple
$K=(P_{1},\dots,P_{t})$ is called a path-tangle rooted at $Y_{0}$ if:

    * i)

For all $i\in[t],$ $y_{\beta(i)}\xrightarrow[W]{P_{i}}y_{\beta(i)}^{\prime}$.

    * ii)

$y_{\beta(1)}^{\prime}\in Y_{0}$.

    * iii)

For $i=2,\dots,t,$ either $y_{\beta(i)}^{\prime}\in Y_{0}$ or
$y_{\beta(i)}^{\prime}\in Z_{\beta(i^{\prime})}$, for some $i^{\prime}<i.$

  * Definition:

$K=(P_{1},P_{2},\dots,P_{t})$ is called a path-chain if instead of iii) $K$
satisfies the stronger property:

    * iv)

For $i=2,\dots,t,$ $y_{\beta(i)}^{\prime}\in Z_{\beta(i-1)}$.

Let $K=(P_{1},\dots,P_{t})$ be the path-tangle as described above. Consider
$y_{\beta(i)}.$ Within $K$ one can find a path-chain
$K^{\prime}=(P_{\gamma(1)},\dots,P_{\gamma(s)})$ where $\gamma(s)=i$ and
$y_{\gamma(1)}^{\prime}\in Y_{0}.$ One can describe such a path-chain
informally as follows: The path $P_{\beta(i)}$ connects $y_{\beta(i)}$ with
$y_{\beta(i)}^{\prime}$. If $y_{\beta(i)}^{\prime}\in Y_{0},$ then
$K^{\prime}=P_{\beta(i)}$ is the desired path-chain. Suppose
$y_{\beta(i)}^{\prime}\not\in Y_{0}.$ Then $y_{\beta(i)}^{\prime}\in
Z_{\beta(i^{\prime})}$, for some $i^{\prime}<i.$ The path
$P_{\beta(i^{\prime})}$ connects $y_{\beta(i^{\prime})}$ with
$y_{\beta(i^{\prime})}^{\prime}.$ If $y_{\beta(i^{\prime})}^{\prime}\in
Y_{0}$, then $K^{\prime}=(P_{\beta(i^{\prime})},P_{\beta(i)})$ is the desired
path-chain. Suppose $y_{\beta(i^{\prime})}^{\prime}\not\in Y_{0}$. Then
$y_{\beta(i^{\prime})}^{\prime}\in Z_{\beta(i^{\prime\prime})}$, for some
$i^{\prime\prime}<i^{\prime}.$ The path $P_{\beta(i^{\prime\prime})}$ connects
$y_{\beta(i^{\prime\prime})}$ with $y_{\beta(i^{\prime\prime})}^{\prime}$. If
$y_{\beta(i^{\prime\prime})}^{\prime}\in Y_{0}$, then
$K^{\prime}=(P_{\beta(i^{\prime\prime})},P_{\beta(i)^{\prime}},P_{\beta(i)})$
is the desired chain. If $y_{\beta(i^{\prime\prime})}^{\prime}\not\in Y_{0},$
then the process continues. Seeing as these paths must eventually terminate in
$Y_{0},$ we will eventually attain the desired path-chain $K^{\prime}$. We
refer to $K^{\prime}$ as a path-chain in $K$ from $Y_{0}$ to $y_{\beta(i)}$.

###  8.1 The composition of path-chains

For $i=1,2,$ let $\beta_{i}:[t_{i}]\rightarrow[k]$ be functions and for
$i=1,2,$ let $K_{i}=(P_{i1},\dots,P_{it_{i}})$ be a path-chain rooted at
$Y_{0},$ where for $j=1,\dots,t_{i}$,
$y_{\beta_{i}(j)}\xrightarrow[W]{P_{ij}}y_{\beta_{i}(j)}^{i}.$ Suppose that
$y_{\beta_{1}(1)}^{1}\in Z_{\beta_{2}(t_{2})}$. Then
$K=(P_{21},\dots,P_{2t_{2}},P_{11},\dots,P_{1t_{1}})$ is seen to be a path-
chain rooted at $Y_{0}.$ We call such a path-chain the composition of $K_{2}$
with $K_{1}$ and denote it by $K_{1}\circ K_{2}.$ See Figure 1.

$Z_{\beta_{1}(t_{1})}$$y_{\beta_{1}(t_{1})}$$Z_{\beta_{1}(t_{1}-1)}$$y_{\beta_{1}(t_{1}-1)}$$y_{\beta_{1}(t_{1})}^{1}$$P_{1t_{1}}$$Z_{\beta_{1}(t_{1}-2)}$$y_{\beta_{1}(t_{1}-2)}$$y_{\beta_{1}(t_{1}-1)}^{1}$$P_{1(t_{1}-1)}$$Z_{\beta_{1}(t_{1}-3)}$$y_{\beta_{1}(t_{1}-3)}$$y_{\beta_{1}(t_{1}-2)}^{1}$$P_{1(t_{1}-2)}$$Z_{\beta_{1}(1)}$$y_{\beta_{1}(1)}$$y_{\beta_{1}(2)}^{1}$$P_{12}$$\cdot$$\cdot$$\cdot$$Z_{\beta_{2}(t_{2})}$$y_{\beta_{2}(t_{2})}$$y_{\beta_{1}(1)}^{1}$$P_{11}$$Z_{\beta_{2}(t_{2}-1)}$$y_{\beta_{2}(t_{2}-1)}$$y_{\beta_{2}(t_{2})}^{2}$$P_{2t_{2}}$$Z_{\beta_{2}(t_{2}-2)}$$y_{\beta_{2}(t_{2}-2)}$$y_{\beta_{2}(t_{2}-1)}^{2}$$P_{2(t_{2}-1)}$$Z_{\beta_{2}(t_{2}-3)}$$y_{\beta_{2}(t_{2}-3)}$$y_{\beta_{2}(t_{2}-2)}^{2}$$P_{2(t_{2}-2)}$$Z_{\beta_{2}(1)}$$y_{\beta_{2}(1)}$$y_{\beta_{2}(2)}^{2}$$P_{22}$$Y_{0}$$y_{\beta_{2}(1)}^{2}$$P_{21}$$\cdot$$\cdot$$\cdot$
Figure 1: The composition of the path-chain $K_{2}=(P_{21},\dots,P_{2t_{2}})$
with $K_{1}=(P_{11},\dots,P_{1t_{1}})$

###  8.2 Targets

Recall that for $i\in[k]$, $C_{i}^{*}=\overline{H}_{i}$ is a cocircuit
containing $a_{i}$. When we modify $W$, we also change $A$ which becomes a new
basis $A^{\prime}.$ The changes we make will be such that when $a_{i}\in A$ is
replaced by an element $a_{i}^{\prime}\in A^{\prime},$ we will require that
$a_{i}^{\prime}\in C_{i}^{*}.$

  * Definition:

A target for $A$ is a $k$-tuple of subsets
$\mathcal{T}=(T_{1},T_{2},\dots,T_{k})$ where for all $i\in[k]$ $a_{i}\in
T_{i}$ and $T_{i}\subseteq C_{i}^{*}.$

  * Definition:

When $\mathcal{T}=(T_{1},\dots,T_{k})$ is a target for $A$, we let
$Z_{i}^{\prime}=\psi_{V}^{-1}(T_{i}),\ i\in[k].$

Let $K=(P_{1},\dots,P_{t})$ be a path-tangle rooted at $Y_{0}$, where for all
$i\in[t],$ $y_{\beta(i)}\xrightarrow[W]{P_{i}}y_{\beta(i)}^{\prime}$. Then $K$
is said to be consistent with the target $\mathcal{T}$ if for $i=2,\dots,t$,
either $y_{\beta(i)}^{\prime}\in Y_{0}$ or $y_{\beta(i)}^{\prime}\in
Z_{\beta(i^{\prime})}^{\prime},$ for some $i^{\prime}<i.$

###  8.3 The flat $\mathbf{F_{0}}$

For the remainder fo the paper, we shall assume that there is at least one
flat $F\in\mathfrak{F}$ for which $\omega_{W}(F)<r_{N}(F).$ We shall choose
such flat $F_{0}$ having least rank.

  * Definition:

Let $F_{0}\in\mathfrak{F}$ be a flat where

    * –

$\omega_{W}(F_{0})<r_{N}(F_{0}).$

    * –

For all flats $F\in\mathfrak{F}$ where $r_{N}(F)<r(F_{0}),$
$\omega_{W}(F)=r_{N}(F).$

In addition, we define a subset $A^{*}\subseteq A$ as follows:

  * Definition:

The set $A^{*}$ consists of elements $a_{i}\in A$ for which $r_{N}(F_{i})\leq
r_{N}(F_{0})$ and $\omega_{W}(F_{i})=r_{N}(F_{i})$.

Note: If $a_{i}\in F_{0}-A^{*},$ then $F_{i}=F_{0}.$ To see this, if
$F_{i}\neq F_{0},$ then $F_{i}\subset F_{0}.$ By our choice of $F_{0}$, we
have $\omega_{W}(F_{i})=r_{N}(F_{i}),$ implying that $a_{i}\in A^{*},$ a
contradiction.

  * Definition:

We say that $\mathcal{T}=(T_{1},T_{2},\dots,T_{k})$ is an $\mathbf{F_{0}}$\-
target if:

    * –

For all $a_{i}\in F_{0}\cup A^{*}$, $T_{i}=F_{i}^{\prime\prime}.$

    * –

For all $a_{i}\not\in F_{0}\cup A^{*},$ $T_{i}=C_{i}^{*}.$

###### Lemma 8.1

Let $\mathcal{T}=(T_{1},T_{2},\dots,T_{k})$ be an $F_{0}$ \- target.

  * a)

If $a_{i}\in A^{*}$ and $a_{j}\not\subseteq F_{i},$ then $C_{j}^{*}\cap
T_{i}=\emptyset.$

  * b)

If $a_{i}\in A^{*}$ and $T_{i}\cap T_{j}\neq\emptyset,$ then $F_{i}=F_{j}$,
$a_{j}\in A^{*},$ and $T_{i}\cap C_{j}^{*}=T_{i}\cap T_{j}$.

  * c)

If $a_{i},a_{j}\in A^{*}$ and $(C_{i}^{*}-T_{i})\cap T_{j}\neq\emptyset,$ then
$F_{i}\subset F_{j}.$

  * d)

If $a_{i},a_{j}\in F_{0}-A^{*}$, then $C_{i}^{*}\cap T_{j}=T_{i}\cap T_{j}.$

  * Proof:

    * a)

Suppose $a_{i}\in A^{*}$ and $a_{j}\not\subseteq F_{i}.$ By definition of
$A^{*},$ $\omega_{W}(F_{i})=r_{N}(F_{i}).$ It follows that $F_{i}\subseteq
H_{j}$ and thus $C_{j}^{*}\cap T_{i}=\emptyset.$

    * b)

Suppose $a_{i}\in A^{*}$ and $T_{i}\cap T_{j}\neq\emptyset.$ By a), $a_{j}\in
F_{i}$ and thus $a_{j}\in A^{*}.$ If $F_{i}\neq F_{j},$ then $a_{i}\not\in
F_{j}$ and $T_{i}\cap T_{j}=\emptyset.$ Thus $a_{i}\in F_{j}$ and consequently
$F_{i}=F_{j}.$

    * c)

Suppose $a_{i},a_{j}\in A^{*}$ and $(C_{i}^{*}-T_{i})\cap T_{j}\neq\emptyset.$
By a), $a_{i}\in F_{j}$ and hence $F_{i}\subseteq F_{j}.$ If $F_{i}=F_{j}$,
then $C_{i}^{*}\cap T_{j}=C_{i}^{*}\cap(C_{j}^{*}\cap F_{j})=(C_{i}^{*}\cap
F_{i})\cap(C_{j}^{*}\cap F_{j})=T_{i}\cap T_{j}.$ However, this contradicts
the assumption that $(C_{i}^{*}-T_{i})\cap T_{j}\neq\emptyset.$ Thus
$F_{i}\subset F_{j}.$

    * d)

Assume that $a_{i},a_{j}\in F_{0}-A^{*}$. We first observe that
$F_{i}=F_{j}=F_{0}.$ Thus $T_{i}=F_{i}^{\prime\prime}=C_{i}^{*}\cap F_{0}$ and
$T_{j}=F_{j}^{\prime\prime}=C_{j}^{*}\cap F_{0}.$ We now see that
$C_{i}^{*}\cap T_{j}=C_{i}^{*}\cap(C_{j}^{*}\cap F_{0})=(C_{i}^{*}\cap
F_{0})\cap(C_{j}^{*}\cap F_{0})=T_{i}\cap T_{j}.$

$\square$

  * Definition:

Let $\mathcal{T}=(T_{1},\dots,T_{k})$ be a target for $A$ and let
$K=(P_{1},\dots,P_{t})$ be a path-chain consistent with $\mathcal{T}$ and
rooted at $Y_{0}$ where $\forall
i\in[t],y_{\beta(i)}\xrightarrow[W]{P_{i}}y_{\beta(i)}^{\prime}$. Then $K$ is
said to be simple if the paths $P_{1},\dots,P_{t}$ are vertex-disjoint and for
$j=2,\dots,t,$ $y_{\beta(j)}^{\prime}\in
Z_{\beta(j-1)}^{\prime}\backslash\bigcup_{j^{\prime}<j-1}Z_{\beta(j^{\prime})}^{\prime}.$

##  9 Choosing $W$ so that $\forall e\in E,\delta_{p+1}(e)\geq 0$

In choosing $W=W_{p+1}$ in $G_{p}$, we need to do so in such a way that
$\forall e\in E,\ \delta_{p+1}(e)\geq 0.$ Equivalently, we want to choose $W$
so that $\forall v\in V,\ \delta_{p+1}(v)\geq 0.$ To do this, we need to
insure that $\forall v\in V,\ d_{p+1}(v)\leq\eta-1.$ It follows by Lemma 3.2,
that for all vertices $v\in V,$ $\delta_{p+1}(v)=\delta_{p}(v)-\nu,$ where
$\nu=1$ if $v\in\overline{V}_{W}$, and $\nu=0$ otherwise. Given that
$\delta_{p}(v)\geq 0,\ v\in V,$ to guarantee that $\forall v\in V,\
\delta_{p+1}(v)\geq 0,$ it suffices to choose $W$ in such a way that $\forall
v\in\overline{V}_{W},\ \delta_{p}(v)>0.$ To achieve this goal, we will show
that that $W$ can be changed incrementally using alternating paths.

We recall that $\overline{V}_{W}=\\{y_{1},\dots,y_{k}\\}$ and
$A=\\{a_{1},\dots,a_{k}\\}.$

###### Proposition 9.1

One can choose the matching $W$ in $G_{p}$ such that $\forall
v\in\overline{V}_{W},\ \delta_{p}(v)>0.$

  * Proof:

Recall that in Section 7 it was shown that for any subset $A^{\prime}\subseteq
A,$ $\delta_{p}\left(\bigcup_{a_{i}\in
A^{\prime}}C_{i}^{*}\right)\geq|A^{\prime}|\eta.$ We may assume that there are
vertices $y_{i}\in\overline{V}_{W}$ such that $\delta_{p}(y_{i})=0.$ It
suffices to show that one can construct a matching $W^{\prime}$ for which
$E_{W^{\prime}}$ is a basis and $\overline{V}_{W^{\prime}}$ has fewer vertices
$v$ than $\overline{V}_{W}$ for which $\delta_{p}(v)=0.$ To begin with, we may
assume (without loss of generality) that $\delta_{p}(y_{k})=0.$ Let
$A_{0}=C_{k}^{*}=\overline{H}_{k}$ and let $Y_{0}=\psi_{V}^{-1}(A_{0})-y_{k}.$

###### Claim 1

There exists a path-tangle $K=(P_{1},\dots,P_{t})$ rooted at $Y_{0}$ where for
some function
$\beta:[t]\rightarrow[k],\
y_{\beta(i)}\xrightarrow[W]{P_{i}}y_{\beta(i)}^{\prime},$ and
$a_{\beta(t)}=a_{k}$.

  * Proof:

We have $\delta_{p}(Y_{0})=\delta_{p}(A_{0})=\delta_{p}(C_{k}^{*})\geq\eta.$
By Lemma 6.2, there is an $Y_{0}$-path $P_{1}$ from some vertex
$y_{i_{1}}\in\overline{V}_{W}$ to some vertex
$y_{i_{1}}^{\prime}\in\widetilde{Y}_{0}$ (noting that
$\delta_{p}(y_{i_{1}}^{\prime})>0$). If $y_{i_{1}}=y_{k},$ then $K=P_{1}$ is
the required path-tangle. Thus we may assume that $y_{1}\neq y_{k}.$ Let
$Y_{1}=Y_{0}\cup Z_{i_{1}}=(Z_{k}\cup Z_{i_{1}})-y_{k}.$ Then
$\delta_{p}(Y_{1})=\delta_{p}(Z_{i_{1}}\cup
Z_{k})=\delta_{p}(C_{i_{1}}^{*}\cup C_{k}^{*})\geq 2\eta.$ By Lemma 6.4, there
is a $Y_{1}$-path $y_{i_{2}}\xrightarrow[W]{P_{2}}y_{i_{2}}^{\prime}$ from a
vertex $y_{i_{2}}\in Y_{1}-y_{i_{1}}$ to a vertex
$y_{i_{2}}^{\prime}\in\widetilde{Y}_{1}.$ If $y_{i_{2}}=y_{k},$ then
$K=(P_{1},P_{2})$ is the required path-tangle. Thus we may assume that
$y_{i_{2}}\neq y_{k}.$ Continuing, suppose we have constructed sets
$Y_{0},Y_{1},\dots,Y_{s}$ and paths $P_{1},\dots,P_{s+1}$ where

    * i)

For all $j\in[s],$ $Y_{j}=Y_{0}\cup Z_{i_{1}}\cup\cdots\cup Z_{i_{j}}$, and
$P_{j}$ is a $Y_{j}$-path where
$y_{i_{j}}\xrightarrow[W]{P_{j}}y_{i_{j}}^{\prime}$.

    * ii)

For all $j\in[s],$ $y_{i_{j}}\in Z_{i_{j}}$ and $y_{i_{j}}^{\prime}\in
Y_{j-1}.$

    * iii)

For all $j\in[s]$, $i_{j}\neq k.$

Given that

$\delta_{p}\left(C_{k}^{*}\cup C_{i_{1}}^{*}\cup\cdots\cup
C_{i_{s}}^{*}\right)=\delta_{p}(N)-\delta_{p}(H_{k}\cap
H_{i_{1}}\cap\cdots\cap H_{i_{s}})\geq k\eta-(k-s-1)\eta=(s+1)\eta,$

we have

$\delta_{p}(Y_{s})=\delta_{p}(Z_{k}\cup Z_{i_{1}}\cup\cdots\cup
Z_{i_{s}})=\delta_{p}\left(C_{k}^{*}\cup C_{i_{1}}^{*}\cup\cdots\cup
C_{i_{s}}^{*}\right)\geq(s+1)\eta.$

By Lemma 6.2, there is a $Y_{s}$-path
$y_{i_{s+1}}\xrightarrow[W]{P_{s+1}}y_{i_{s+1}}^{\prime}$ from some vertex
$y_{i_{s+1}}\in\overline{V}_{W}-\\{y_{i_{1}},\dots,y_{i_{s}}\\}$ to some
vertex $y_{i_{s+1}}^{\prime}\in Y_{s}.$ If $y_{i_{s+1}}=y_{k},$ then
$K=(P_{1},\dots,P_{s+1})$ is the desired path-tangle. On the other hand, if
$y_{i_{s+1}}\neq y_{k},$ then the process continues with $s+1$ in place of
$s.$ Since this process must eventually terminate, we must eventually end up
with the desired path-tangle $K=(P_{1},\dots,P_{t})$. $\square$

Let $K=(P_{1},\dots,P_{t})$ be the path-tangle described in Claim 1. Among
such path-tangles, we may assume that $K$ contains a minimum number of paths.
We claim that $K$ is a simple path-chain. If for some $j_{1}<j_{2},$ the paths
$P_{j_{1}}$ and $P_{j_{2}}$ intersect, then it follows by Observation 6.5 that
$y_{i_{j_{2}}}\xrightarrow[W]{P}y_{i_{j_{1}}}^{\prime}$ for some path $P$. In
this case, $K^{\prime}=(P_{1},\dots,P_{j_{1}-1},P,P_{j_{2}+1},\dots,P_{t})$
would be a path-tangle with fewer paths. Thus by our choice of $K$, the paths
$P_{1},\dots,P_{t}$ must be pairwise disjoint. By a similar argument using
minimality, one can show that for $j=2,\dots,t$ $y_{i_{j}}^{\prime}\in
Z_{i_{j-1}}\backslash\bigcup_{j^{\prime}<j-1}Z_{i_{j^{\prime}}}.$ Thus $K$ is
a simple path-chain.

For all $j\in[t],$ let $a_{i_{j}}^{\prime}=\psi_{V}(y_{i_{j}}^{\prime}).$
Since $K$ is a simple path-chain, we have for $j=2,\dots,t,\
a_{i_{j}}^{\prime}\in C_{i_{j-1}}^{*}.$

###### Claim 2

$A^{\prime}=A-\\{a_{i_{1}},\dots,a_{i_{t}}\\}+\\{a_{i_{1}}^{\prime},\dots,a_{i_{t}}^{\prime}\\}$
is a basis in $N.$

  * Proof:

First we claim that $A^{1}=A-a_{i_{t-1}}+a_{i_{t}}^{\prime}$ is a basis. Given
this is clear if $a_{i_{t}}^{\prime}=a_{i_{t-1}},$ we may assume that
$a_{i_{t}}^{\prime}\neq a_{i_{t-1}}.$ Then $(A+a_{i_{t}}^{\prime})\cap
C_{i_{t-1}}^{*}=\\{a_{i_{t-1}},a_{i_{t}}^{\prime}\\}$ and it follows that
$A^{1}$ is a basis in $N.$ Suppose now that for some $s\geq 1$,
$A^{s}=A-\\{a_{i_{t-s}},\dots,a_{i_{t-1}}\\}+\\{a_{i_{t-s+1}}^{\prime},\dots,a_{i_{t}}^{\prime}\\}$
is a basis. Assuming $s<t-1$, we claim that
$A^{s+1}=A^{s}-a_{i_{t-s-1}}+a_{i_{t-s}}^{\prime}$ is a basis. We may assume
$a_{i_{t-s-1}}\neq a_{i_{t-s}}^{\prime}$ (for otherwise, $A^{s+1}=A^{s}$).
Since $K$ is a simple path-chain, for $j=t-s+1,\dots,t$,
$y_{i_{j}}^{\prime}\not\in Z_{i_{t-s-1}},$ it follows that for
$j=t-s+1,\dots,t,$ $a_{i_{j}}^{\prime}\not\in C_{i_{t-s-1}}^{*}.$ Thus
$(A^{s}+a_{i_{t-s}}^{\prime})\cap
C_{i_{t-s-1}}^{*}=\\{a_{i_{t-s-1}},a_{i_{t-s}}^{\prime}\\},$ and thus it
follows that $A^{s+1}$ is a basis. By induction, we see that
$A^{t-1}=A-\\{a_{i_{1}},\dots,a_{i_{t-1}}\\}+\\{a_{i_{2}}^{\prime},\dots,a_{i_{t}}^{\prime}\\}$
is a basis in $N.$ Since $K$ is a simple path-chain, for all $j=2,\dots,t$,
$y_{i_{j}}^{\prime}\not\in Y_{0}.$ Thus for $j=2,\dots,t,$
$a_{i_{j}}^{\prime}\not\in C_{k}^{*}$ and this implies that
$(A^{t-1}+a_{i_{1}}^{\prime})\cap C_{k}^{*}=\\{a_{k},a_{i_{1}}^{\prime}\\}.$
It now follows that $A^{\prime}=A^{t-1}-a_{k}+a_{i_{1}}$ is a basis. $\square$

Finally, let $W^{\prime}$ be the matching obtained from $W$ by the deleting
from $W$ the edges in $P_{1}\cup\cdots P_{t}$ belonging to $W$ and then adding
the edges of $P_{1}\cup\cdots\cup P_{t}$ which do not belong to $W$. Then
$\overline{V}_{W^{\prime}}=\overline{V}_{W}-\\{y_{i_{1}},\dots,y_{i_{t}}\\}+\\{y_{i_{1}}^{\prime},\dots,y_{i_{t}}^{\prime}\\}$
and $A^{\prime}=\psi_{V}(\overline{V}_{W^{\prime}}).$ Since $\forall j\in[t],\
\delta_{p}(y_{i_{j}}^{\prime})>0,$ we see that $\overline{V}_{W^{\prime}}$ has
fewer vertices $v$ than $\overline{V}_{W}$ for which $\delta_{p}(v)=0.$
Furthermore, since $A^{\prime}$ is a basis in $N$, it follows that
$E_{W^{\prime}}$ is a basis in $M.$ $\square$

##  10 Choosing $W$ so that for all flats $F\in\mathfrak{F}$,
$\omega_{W}(F)=r_{N}(F)$

In light of Proposition 9.1, we may assume that $\forall
v\in\overline{V}_{W},\ \delta_{p}(v)>0.$ Our goal in this section is to prove
the following theorem:

###### Theorem 10.1

The matching $W$ can be chosen so that i) $E_{W}$ is a basis ii) $\forall e\in
E,\ \delta_{p+1}(e)\geq 0$ and iii) $\forall F\in\mathfrak{F}$,
$\omega_{W}(F)=r_{N}(F)$.

  * Definition:

Let $W^{\prime}$ and $W^{\prime\prime}$ be matchings in $G_{p}$ for which
$E_{W^{\prime}}$ and $E_{W^{\prime\prime}}$ are bases. We define a partial
order $\preceq$ where $W^{\prime}\preceq W^{\prime\prime}$ if the following
holds: for all $F\in\mathfrak{F},$ where $r_{N}(F)\leq r_{N}(F_{0})$, if
$\omega_{W^{\prime}}(F)=r_{N}(F),$ then
$\omega_{W^{\prime\prime}}(F)=r_{N}(F).$

We will introduce an procedure by which we alter $W$ and construct a matching
$W^{\prime}$ in $G_{p}$ for which

  * •

$E_{W^{\prime}}$ is a basis of $M$.

  * •

$\forall v\in\overline{V}_{W^{\prime}},\ \delta_{p}(v)>0,$

  * •

$W\preceq W^{\prime}$

  * •

$\omega_{W^{\prime}}(F_{0})>\omega_{W}(F_{0}).$

Repeated iterations of the above procedure will eventually yield a matching
$W^{\prime}$ for for which $W\preceq W^{\prime}$ and
$\omega_{W^{\prime}}(F_{0})=r_{N}(F_{0}).$ If there are flats
$F\in\mathfrak{F}$ for which $\omega_{W^{\prime}}(F)<r_{N}(F),$ then we choose
such a flat $F_{0}^{\prime}$ of least rank and repeat the procedure with
$F_{0}^{\prime}$ in place of $F_{0}$ and $W^{\prime}$ in place of $W.$
Eventually we achieve a matching $W^{\prime}$ for which $E_{W^{\prime}}$ is a
basis and for which $\forall F\in\mathfrak{F},\
\omega_{W^{\prime}}(F)=r_{N}(F).$ Thus to prove Theorem 10.1, it suffices to
show that the procedure works. We shall accomplish this by choosing a specific
simple path-chain.

To begin, we will need a lemma pertaining to directed graphs:

###### Lemma 10.2

Let $\overrightarrow{D}$ be a directed graph having no directed cycles. Then
for every vertex $u$ there is a partition $(X,Y)$ for the vertices for which
$u\in X$, and for all vertices $v\in V(\overrightarrow{D})$,
$\mathbf{1}_{X}(v)+|X\cap N_{\overrightarrow{D}}^{-1}(v)|$ is odd if and only
if $v=u.$

  * Proof:

By induction on the number of vertices in $\overrightarrow{D}.$ If the
$\overrightarrow{D}$ only has one vertex, then the lemma is immediate. Suppose
$\overrightarrow{D}$ has $\ell$ vertices and the lemma hold for directed
graphs with fewer than $\ell$ vertices. Let $u$ be a vertex in
$\overrightarrow{D}$. Since $\overrightarrow{D}$ is acyclic, it has as least
one source and one sink. We may assume that $v_{s}$ is a such a vertex where
$v_{s}\neq u.$ Let $\overrightarrow{D}^{\prime}$ be the (acyclic) directed
graph obtained by deleting $v_{s}.$ By assumption, the lemma holds for
$\overrightarrow{D}^{\prime}$ and thus there is a partition
$(X^{\prime},Y^{\prime})$ for the vertices of $\overrightarrow{D}^{\prime}$
for which $u\in X^{\prime}$, and for all vertices $v\in
V(\overrightarrow{D}^{\prime})$, the sum
$\mathbf{1}_{X^{\prime}}(v)+|X^{\prime}\cap
N_{\overrightarrow{D}^{\prime}}^{-1}(v)|$ is odd if and only if $v=u.$ If
$v_{s}$ is a source, then letting $X=X^{\prime}$ and $Y=Y^{\prime}+v_{s}$ we
achieve the desired partition $(X,Y).$ On the other hand, if $v_{s}$ is a
sink, then we let $X=X^{\prime}+v_{s}$ and $Y=Y^{\prime}$ if $|X^{\prime}\cap
N_{\overrightarrow{D}}^{-1}(v_{s})|$ is odd; otherwise, if $|X^{\prime}\cap
N_{\overrightarrow{D}}^{-1}(v_{s})|$ is even, then we let $X=X^{\prime}$ and
$Y=Y^{\prime}+v_{s}.$ This is seen to give the desired partition $(X,Y)$ for
$\overrightarrow{D}.$ The proof now follows by induction. $\square$

Let $A_{0}=F_{0}-(F_{0})_{A}$ (where $(F_{0})_{A}=\mathrm{cl}_{N}(F_{0}\cap
A)$). Let $\mathcal{T}=(T_{1},\dots,T_{k})$ be an $F_{0}$-target for $A$ and
let $Y_{0}=\psi_{V}^{-1}(A_{0}).$ Let $K=(P_{1},\dots,P_{t})$ be a simple
path-chain consistent with $\mathcal{T}$ rooted at $Y_{0}$ where $\forall
i\in[t],\ y_{\beta(i)}\xrightarrow[W]{P_{i}}y_{\beta(i)}^{\prime}.$ For all
$i\in[t],$ let $a_{\beta(i)}^{\prime}=\psi_{V}(y_{\beta(i)}^{\prime}).$

###### Proposition 10.3

Suppose $a_{\beta(t)}\in A-(F_{0}\cup A^{*})$ and $a_{\beta(1)}^{\prime}\in
T_{\beta(t)}.$ Suppose there is no pair $j,j^{\prime}\in[t]$, $0\leq
j-j^{\prime}<t-1,$ for which $a_{\beta(j)}\in A-(F_{0}\cup A^{*})$ and
$a_{\beta(j^{\prime})}^{\prime}\in F_{0}\cap T_{\beta(j)}.$ Then
$A-\\{a_{\beta(1)},\dots,a_{\beta(t)}\\}+\\{a_{\beta(1)}^{\prime},\dots,a_{\beta(t)}^{\prime}\\}$
is a basis for $N$.

  * Proof:

We shall define a directed graph $\overrightarrow{D}$ as follows:
$V_{\overrightarrow{D}}=\\{x_{1},\dots,x_{t}\\}$ and for all $i,j\in[t],$
there is an arc from $x_{i}$ to $x_{j}$ if and only if
$a_{\beta(j+1)}^{\prime}\in C_{\beta(i)}^{*}.$ Here we define
$a_{\beta(t+1)}^{\prime}:=a_{\beta(1)}^{\prime}.$ An arc from $x_{i}$ to
$x_{j}$ will be denoted by the ordered pair $(x_{i},x_{j}).$ We let
$E(\overrightarrow{D})$ denote the set of arcs of $\overrightarrow{D}.$

    * (A) The directed graph $\overrightarrow{D}$ is acyclic.

    * Proof:

To begin with, we make some useful observations.

      * i)

If $i<j$ and $(x_{i},x_{j})$ is an arc, then $a_{\beta(i)}\in F_{0}\cup
A^{*}.$

        * Proof:

Suppose $i<j$ and $(x_{i},x_{j})$ is an arc. We have
$a_{\beta(j+1)}^{\prime}\in C_{\beta(i)}^{*}\cap T_{\beta(j)}.$ Since $K$ is a
simple path-chain, $a_{\beta(j+1)}^{\prime}\not\in T_{\beta(i)},$ and it
follows that $T_{\beta(i)}\neq C_{\beta(i)}^{*}.$ Thus $a_{\beta(i)}\in
F_{0}\cup A^{*}.$ $\square$

      * ii)

If $i<j,$ $(x_{i},x_{j})$ is an arc, and $a_{\beta(i)}\in F_{0}-A^{*},$ then
$a_{\beta(j)}\in A-(F_{0}\cup A^{*}).$

        * Proof:

Assume that for some $i<j$, $(x_{i},x_{j})$ is an arc where $a_{\beta(i)}\in
F_{0}-A^{*}.$ We have
$a_{\beta(j+1)}^{\prime}\in(C_{\beta(i)}^{*}-T_{\beta(i)})\cap T_{j}.$ If
$a_{\beta(j)}\in F_{0}-A^{*}$, then it follows by Lemma 8.1 d) that
$C_{\beta(i)}^{*}\cap T_{\beta(j)}=T_{\beta(i)}\cap T_{\beta(j)},$ which is a
contradiction. Thus $a_{\beta(j)}\not\in F_{0}-A^{*}.$ If $a_{\beta(j)}\in
A^{*},$ then by Lemma 8.1 a), $C_{\beta(i)}^{*}\cap T_{\beta(j)}=\emptyset,$ a
contradiction. Thus $a_{\beta(i)}\in A-(F_{0}\cup A^{*}).$ $\square$

      * iii)

Suppose $(x_{i},x_{j})$ is an arc where
$\\{a_{\beta(i)},a_{\beta(j)}\\}\subseteq A^{*}.$ Then $F_{\beta(i)}\subseteq
F_{\beta(j)}.$ Moreover, if $i<j,$ then $F_{\beta(i)}\subset F_{\beta(j)}.$

        * Proof:

We have $a_{\beta(j+1)}^{\prime}\in C_{\beta(i)}^{*}\cap T_{\beta(j)}.$ It
follows by Lemma 8.1 a) that $a_{\beta(i)}\in F_{\beta(j)}$ and thus
$F_{\beta(i)}\subseteq F_{\beta(j)}.$ If $i<j$, then
$a_{\beta(j+1)}\in(C_{\beta(i)}^{*}-T_{\beta(i)})\cap T_{\beta(j)}.$ It
follows by Lemma 8.1 c) that $F_{\beta(i)}\subset F_{\beta(j)}.$ $\square$

      * iv)

If $i<j,$ $(x_{j},x_{i})$ is an arc, and $a_{\beta(j)}\in A-(F_{0}\cup
A^{*})$, then $a_{\beta(i)}\in A-(F_{0}\cup A^{*}).$

        * Proof:

Assume that $i<j,$ $(x_{j},x_{i})$ is an arc, and $a_{\beta(j)}\in
A-(F_{0}\cup A^{*}).$ Suppose $a_{\beta(i)}\in F_{0}\cup A^{*}$. Since
$a_{\beta(i+1)}^{\prime}\in C_{\beta(j)}^{*}\cap T_{\beta(i)},$ it follows by
Lemma 8.1 a) that $a_{\beta(i)}\in F_{0}-A^{*}.$ However, this contradicts our
assumptions since $a_{\beta(j)}\in A-(F_{0}\cup A^{*})$ and
$a_{\beta(i+1)}^{\prime}\in T_{\beta(i)}\cap C_{\beta(j)}^{*}=T_{\beta(i)}\cap
T_{\beta(j)}.$ Thus $a_{\beta(i)}\in A-(F_{0}\cup A^{*})$. $\square$

Suppose to the contrary that there is a directed cycle $x_{i_{1}}\rightarrow
x_{i_{2}}\rightarrow\cdots\rightarrow x_{i_{\ell}}\rightarrow x_{i_{1}}.$ We
may assume that $\beta(i_{1})=\min\\{\beta(i_{j})\ \big{|}\
j=1,\dots,\ell\\}.$ Since $i_{1}<i_{2}$ and $(x_{i_{1}},x_{i_{2}})$ is an arc,
it follows by i) that $a_{\beta(i_{1})}\in F_{0}\cup A^{*}.$ If
$a_{\beta(i_{2})}\in A-(F_{0}\cup A^{*}),$ then it follows by i) and iv) that
$\beta(i_{2})>\beta(i_{3})>\cdots>\beta(i_{\ell})>\beta(i_{1})$ and
$a_{\beta(i_{j})}\in A-(F_{0}\cup A^{*}),\ j=1,\dots\ell.$ This yields a
contradiction since $a_{\beta(i_{1})}\in F_{0}\cup A^{*}.$ It follows that
$a_{\beta(i_{2})}\in F_{0}\cup A^{*}.$ In fact, the above reasoning shows that
$\forall j\in[\ell],$ $a_{\beta(i_{j})}\in F_{0}\cup A^{*}$. Suppose
$a_{\beta(i_{1})}\in F_{0}-A^{*}.$ Then it follows by ii) that
$a_{\beta(i_{2})}\in A-(F_{0}\cup A^{*}),$ yielding a contradiction. Thus
$a_{\beta(1)}\in A^{*}.$ If $a_{\beta(2)}\in A^{*},$ then it follows by iii)
that $F_{\beta(1)}\subset F_{\beta(2)}.$ There exists
$2\leq\ell^{\prime}<\ell$ such that $\forall j\in[\ell^{\prime}-1],\
a_{\beta(i_{j})}\in A^{*}$ and $a_{\beta(i_{\ell^{\prime}})}\not\in A^{*}.$
For if no such $\ell^{\prime}$ existed, then we would have $\forall
j\in[\ell],\ a_{\beta(i_{j})}\in A^{*}$ and consequently
$F_{\beta(i_{1})}\subset F_{\beta(i_{2})}\subseteq\cdots\subseteq
F_{\beta(i_{\ell})}\subseteq F_{\beta(i_{1})},$ a contradiction. Since
$a_{\beta(i_{\ell^{\prime}})}\not\in A^{*},$ it follows that
$a_{\beta(i_{\ell^{\prime}})}\in F_{0}-A^{*}.$

If $\beta(i_{\ell^{\prime}})<\beta(i_{\ell^{\prime}+1}),$ then it follows by
ii) that $a_{\beta(i_{\ell^{\prime}+1})}\in A-(F_{0}\cup A^{*}),$ a
contradiction. Thus $\beta(i_{\ell^{\prime}+1})<\beta({i_{\ell^{\prime}}}).$
Since $a_{\beta(i_{\ell^{\prime}+1}+1)}^{\prime}\in
C_{\beta(i_{\ell^{\prime}})}^{*}\cap T_{\beta(i_{\ell^{\prime}+1})},$ it
follows by Lemma 8.1 c), that $a_{\beta(i_{\ell^{\prime}+1})}\not\in A^{*}.$
Thus $a_{\beta(i_{\ell^{\prime}+1})}\in F_{0}-A^{*}.$ Following the same
reasoning, we obtain that
$\beta(i_{\ell^{\prime}})>\beta(i_{\ell^{\prime}+1})>\dots>\beta(i_{\ell})>\beta(i_{1})$,
and $\forall j\in\\{1,\ell^{\prime},\ell^{\prime}+1,\dots,\ell\\},$
$a_{\beta(i_{j})}\in F_{0}-A^{*}$. This gives a contradiction because
$a_{\beta(i_{1})}\in A^{*}.$ $\square$

    * (B) For all $2\leq s\leq t-1,$ there is a cocircuit $C^{*}$ in $N$ such that

$C^{*}\cap\left((A-\\{a_{\beta(s)},\dots,a_{\beta(t-1)}\\})\cup\\{a_{\beta(s)}^{\prime},\dots,a_{\beta(t)}^{\prime}\\}\right)=\\{a_{\beta(s-1)},a_{\beta(s)}^{\prime}\\}.$

    * Proof:

Let $\overrightarrow{D}^{\prime}$ be the directed graph $\overrightarrow{D}$
restricted to the vertices $x_{s-1},\dots,x_{t-1}$. By Lemma 10.2, there is a
partition $(X,Y)$ of the vertices of $\overrightarrow{D}^{\prime}$ where
$x_{s-1}\in X$ and for all $i=s-1,\dots,t-1$, the sum
$\Sigma_{i}=\mathbf{1}_{X}(x_{i})+|X\cap
N_{\overrightarrow{D}^{\prime}}^{-1}(x_{i})|$ is odd if and only if $i=s-1.$
Let $C^{*}=\bigtriangleup_{x_{i}\in X}C_{\beta(i)}^{*}$. Since $\Sigma_{s-1}$
is odd, it follows that $a_{\beta(s)}^{\prime}\in C^{*}$, and furthermore,
$a_{\beta(s-1)}\in C^{*}.$ Since $\Sigma_{i}$ is even for $i=s,\dots,t-1$, it
follows that for $i=s,\dots,t-1$, $a_{\beta(i+1)}^{\prime}\not\in C^{*}.$ Thus
we see that $C^{*}$ is a cocircuit for which
$C^{*}\cap\left((A-\\{a_{\beta(s)},\dots,a_{\beta(t-1)})\cup\\{a_{\beta(s)}^{\prime},\dots,a_{\beta(t)}^{\prime}\\}\right)=\\{a_{\beta(s-1)},a_{\beta(s)}^{\prime}\\}.$
$\square$

    * (C) There is a cocircuit $C^{*}$ in $N$ such that $C^{*}\cap\left((A-\\{a_{\beta(1)},\dots,a_{\beta(t-1)}\\})\cup\\{a_{\beta(1)}^{\prime},\dots,a_{\beta(t)}^{\prime}\\}\right)=\\{a_{\beta(t)},a_{\beta(1)}^{\prime}\\}.$

    * Proof:

By Lemma 10.2, there is a partition $(X,Y)$ of the vertices of
$\overrightarrow{D}$ where $x_{t}\in X$ and for all $i=1,\dots,t$, the sum
$\Sigma_{i}=\mathbf{1}_{X}(x_{i})+|X\cap
N_{\overrightarrow{D}^{\prime}}^{-1}(x_{i})|$ is odd if and only if $i=t.$ Let
$C^{*}=\bigtriangleup_{x_{i}\in X}C_{\beta(i)}^{*}$. Since $\Sigma_{t}$ is
odd, it follows that $a_{\beta(1)}^{\prime}\in C^{*}$ (and $a_{\beta(t)}\in
C^{*}$). Since $\Sigma_{i}$ is even for $i=1,\dots,t-1$, we see that $\forall
i\in[t-1],\ a_{\beta(i+1)}^{\prime}\not\in C^{*}.$ Thus $C^{*}$ is a cocircuit
for which
$C^{*}\cap\left((A-\\{a_{\beta(1)},\dots,a_{\beta(t-1)}\\})\cup\\{a_{\beta(1)}^{\prime},\dots,a_{\beta(t)}^{\prime}\\}\right)=\\{a_{\beta(t)},a_{\beta(1)}^{\prime}\\}.$
$\square$

    * (D) $A-\\{a_{\beta(1)},\dots,a_{\beta(t-1)}\\}+\\{a_{\beta(2)}^{\prime},\dots,a_{\beta(t)}^{\prime}\\}$ is a basis for $N.$

    * Proof:

We will first show that $A^{1}=A-a_{\beta(t-1)}+a_{\beta(t)}^{\prime}$ is a
basis of $N.$ If $a_{\beta(t-1)}=a_{\beta(t)}^{\prime},$ then $A^{1}=A,$ and
hence it is a basis. Thus we may assume $a_{\beta(t-1)}\neq
a_{\beta(t)}^{\prime}.$ We see that $(A+a_{\beta(t)}^{\prime})\cap
C_{\beta(t-1)}^{*}=\\{a_{\beta(t-1)},a_{\beta(t)}^{\prime}\\}$ and hence it
follows that $A^{1}$ is a basis.

Suppose that for some $2\leq s\leq t-1$,
$A^{t-s}=A-\\{a_{\beta(s)},\cdots,a_{\beta(t-1)}\\}+\\{a_{\beta(s+1)}^{\prime},\cdots,a_{\beta(t)}^{\prime}\\}$
is a basis. We claim that
$A^{t-s+1}=A^{t-s}-a_{\beta(s-1)}+a_{\beta(s)}^{\prime}$ is a basis. If
$a_{\beta(s)}^{\prime}=a_{\beta(s-1)},$ then $A^{t-s+1}=A^{t-s}$ and the
assertion is true. Thus we may assume that $a_{\beta(s)}^{\prime}\neq
a_{\beta(s-1)}.$ By ( ‣ Proof:), there is a cocircuit $C^{*}$ in $N$ for which
$C^{*}\cap(A^{s-t}+a_{\beta(s)}^{\prime})=\\{a_{\beta(s-1)},a_{\beta(s)}^{\prime}\\}$.
Thus it follows that $A^{t-s+1}$ is a basis. Continuing inductively, we see
that
$A^{t-1}=A-\\{a_{\beta(1)},\dots,a_{\beta(t-1)}\\}+\\{a_{\beta(2)}^{\prime},\dots,a_{\beta(t)}^{\prime}\\}$
is a basis of $N$. $\square$

Finally, we shall show that
$A^{t}=A-\\{a_{\beta(1)},\dots,a_{\beta(t)}\\}+\\{a_{\beta(1)}^{\prime},\dots,a_{\beta(t)}^{\prime}\\}$
is a basis for $N.$ By (10), there is a cocircuit $C^{*}$ such that
$C^{*}\cap\left((A-\\{a_{\beta(1)},\dots,a_{\beta(t-1)}\\})\cup\\{a_{\beta(1)}^{\prime},\dots,a_{\beta(t)}^{\prime}\\}\right)=\\{a_{\beta(t)},a_{\beta(1)}^{\prime}\\}.$
Thus $C^{*}\cap A^{t-1}=\\{a_{\beta(t)},a_{\beta(1)}\\}.$ It follows that
$A^{t}=A^{t-1}-a_{\beta(t)}+a_{\beta(1)}^{\prime}$ is a basis. $\square$

###  10.1 Finding a path-chain

As before, let $A_{0}=F_{0}-(F_{0})_{A}$ and $Y_{0}=\psi_{V}^{-1}(A_{0}).$ Let
$\mathcal{T}=(T_{1},\dots,T_{k})$ be an $F_{0}$-target. Let
$A^{\spadesuit}=A-(F_{0}\cup A^{*}).$ Here we shall make the critical
assumption that $\eta>c_{0}+c_{1},$ where $c_{0}$ and $c_{1}$ are the
constants specified by Lemmas 7.2 and 7.5. Our goal in this section is to
prove the following:

###### Proposition 10.4

There is a function $\gamma:[s]\rightarrow[k]$ and a path-chain consistent
with $\mathcal{T}$, $K^{\prime}=(P_{\gamma(1)},\dots,P_{\gamma(s)}),$ where

  * •

$\forall i\in[s],\
y_{\gamma(i)}\xrightarrow[W]{P_{\gamma(i)}}y_{\gamma(i)}^{\prime}.$

  * •

$a_{\gamma(s)}\in A^{\spadesuit}$

  * •

$a_{\gamma(1)}^{\prime}=\psi_{V}(y_{\gamma(1)}^{\prime})\in A_{0}\cap
T_{\gamma(s)}.$

  * Proof:

By Lemma 7.2, $\delta_{p}(F_{0})\geq r_{N}(F_{0})\eta-c_{0}.$ We also have
that $\delta_{p}((F_{0})_{A})\leq
r_{N}((F_{0})_{A})\eta=\omega_{W}(F_{0})\eta.$ Thus it follows that

$\delta_{p}(Y_{0})=\delta_{p}(A_{0})=\delta_{p}(F_{0})-\delta_{p}((F_{0})_{A})\geq(r_{N}(F_{0})-\omega_{W}(F_{0}))\eta-
c_{0}\geq\eta-c_{0}.$

Since $\delta_{p}(Y_{0})>0,$ it follows by Lemma 6.2 that there is a
$Y_{0}$-path $P_{i_{1}}$ from some vertex $y_{i_{1}}\in\overline{V}_{W}$ to a
vertex $y_{i_{1}}^{\prime}\in\widetilde{Y}_{0}.$ Let
$a_{i_{1}}^{\prime}=\psi_{V}(y_{i_{1}}^{\prime}),$ noting that
$\delta_{p}(a_{i_{1}}^{\prime})>0.$ Let $\Upsilon_{0}=A_{0}$,
$\Upsilon_{1}=A_{0}\cup T_{i_{1}}$ and let
$Y_{1}=\psi_{V}^{-1}(\Upsilon_{1}).$ Suppose that
$\delta_{p}(\Upsilon_{1})\geq 2\eta-c_{0}-c_{1}.$ By Lemma 6.4, since
$\lceil\frac{\eta-c_{0}-c_{1}}{\eta}\rceil>0$, there is a vertex
$v\in\overline{V}_{W}-y_{i_{1}}$ for which there is a $Y_{1}$-path from $v$ to
a vertex in $\widetilde{Y}_{1}.$ Let $y_{i_{2}}\in\overline{V}_{W}-y_{i_{1}}$
be such a vertex and let $P_{i_{2}}$ be a $Y_{1}$-path from $y_{i_{2}}$ to
$y_{i_{2}}^{\prime}$ and let
$a_{i_{2}}^{\prime}=\psi_{V}(y_{i_{2}}^{\prime}).$ Let
$\Upsilon_{2}=\Upsilon_{1}\cup T_{i_{2}}$ and let
$Y_{2}=\psi_{V}^{-1}(\Upsilon_{2}).$ If $\delta_{p}(\Upsilon_{2})\geq 3\eta-
c_{0}-c_{1},$ then given $\lceil\frac{\eta-c_{0}-c_{1}}{\eta}\rceil>0$, Lemma
6.4 implies that there is a vertex $v\in\overline{V}_{W}-y_{i_{1}}-y_{i_{2}}$
for which there is a $Y_{2}$-path from $v$ to a vertex in $\widetilde{Y}_{2}.$
Let $y_{i_{3}}\in\overline{V}_{W}-y_{i_{1}}-y_{i_{2}}$ be such a vertex and
let $P_{i_{3}}$ be a $Y_{2}$-path from $y_{i_{3}}$ to $y_{i_{3}}^{\prime}$.
Let $a_{i_{3}}^{\prime}=\psi_{V}(y_{i_{3}}^{\prime}).$ Since the process must
eventually terminate, we may assume that for some $t>0$ we have generated
$\Upsilon_{1},\dots,\Upsilon_{t}$. and $\delta_{p}(\Upsilon_{t})<(t+1)\eta-
c_{0}-c_{1}.$ We now make the key assertion that
$\displaystyle{A_{0}\subseteq\bigcup_{j\in[t],\ a_{i_{j}}\in
A^{\spadesuit}}T_{i_{j}}}$; that is, the union of all the target sets
$T_{i_{j}}$ where $a_{i_{j}}\in A^{\spadesuit},$ contains the set $A_{0}.$
This will follow from the next claim.

###### Claim 3

Let $A^{1}\subseteq A^{\spadesuit}$ and let $A^{2}\subseteq A\cap(F_{0}\cup
A^{*}).$ Suppose that $A_{0}\not\subseteq\bigcup_{a_{i}\in A^{1}}T_{i}.$ Then
$\delta_{p}\left(A_{0}\cup\bigcup_{a_{i}\in(A^{1}\cup
A^{2})}T_{i}\right)\geq(|A^{1}|+|A^{2}|+1)\eta-c_{0},-c_{1}.$

  * Proof:

Let $A^{21}=A^{2}-A^{*}$ and let $A^{22}=A^{2}\cap A^{*}$. By Lemma 7.5 we
have

$\delta_{p}\left(\bigcup_{a_{i}\in
A^{22}}T_{i}\right)=\delta_{p}\left(\bigcup_{a_{i}\in
A^{22}}C_{i}^{*}\right)\geq|A^{22}|\eta-c_{1}.$

Let $F=\bigcap_{a_{i}\in A^{1}}H_{i}.$ Then $r_{N}(F)\leq k-|A^{1}|.$ We also
see that

$\delta_{p}\left(\bigcup_{a_{i}\in
A^{1}}T_{i}\right)=\delta_{p}\left(\bigcup_{a_{i}\in
A^{1}}C_{i}^{*}\right)=\delta_{p}(N)-\delta_{p}(F)=k\eta-\delta_{p}(F).$

Let $\varepsilon_{1}\geq 0$ be such that
$\delta_{p}(F)=r_{N}(F)\eta-\varepsilon_{1}.$ Then

$\delta_{p}\left(\bigcup_{a_{i}\in
A^{1}}T_{i}\right)=(k-r_{N}(F)\eta+\varepsilon_{1}\geq|A^{1}|\eta+\varepsilon_{1}.$

Let $F_{0}^{\prime}=F\cap F_{0}.$ We note that $(F_{0})_{A}\subseteq
F_{0}^{\prime}.$ It follows by Lemma 7.1 that $\delta_{p}(F_{0}^{\prime})\geq
r_{N}(F_{0}^{\prime})\eta-c_{0}-\varepsilon_{1}.$ Since
$A_{0}\not\subseteq\bigcup_{a_{i}\in A^{1}}T_{i}=\bigcup_{a_{i}\in
A^{1}}C_{i}^{*}$, it follows that $F_{0}^{\prime}\cap A_{0}\neq\emptyset$ and
hence $r_{N}(F_{0}^{\prime})>r_{N}((F_{0})_{A})=\omega_{W}(F_{0}).$ Note that
for all $a_{i}\in A^{21},$ $F_{i}=F_{0}$ and thus
$T_{i}=F_{i}^{\prime\prime}=C_{i}^{*}\cap F_{0}.$ For all $a_{i}\in A^{21},$
let
$T_{i}^{\prime}=T_{i}\cap(F_{0})_{A}=F_{i}^{\prime\prime}\cap(F_{0})_{A}=C_{i}^{*}\cap(F_{0})_{A}.$
Let $\delta_{p}((F_{0})_{A})=r_{N}((F_{0})_{A})\eta-\varepsilon_{2}.$ Then

$\displaystyle\delta_{p}(A_{0}\cap F_{0}^{\prime})$
$\displaystyle=\delta_{p}(F_{0}^{\prime})-\delta_{p}((F_{0})_{A})$
$\displaystyle\geq r_{N}(F_{0}^{\prime})\eta-
c_{0}-\varepsilon_{1}-r_{N}((F_{0})_{A})\eta+\varepsilon_{2}$
$\displaystyle=(r_{N}(F_{0}^{\prime})-r_{N}((F_{0})_{A})\eta-
c_{o}-\varepsilon_{1}+\varepsilon_{2}.$

Furthermore, we also see that

$\displaystyle\delta_{p}\left(\bigcup_{a_{i}\in A^{21}}T_{i}^{\prime}\right)$
$\displaystyle=\delta_{p}((F_{0})_{a})-\delta_{p}\left((F_{0})_{A}\cap\bigcap_{a_{i}\in
A^{21}}H_{i}\right)$
$\displaystyle\geq\delta_{p}((F_{0})_{a})-(r_{N}((F_{0})_{A})-|A^{21}|)\eta$
$\displaystyle=|A^{21}|\eta-\varepsilon_{2}.$

Thus we have

$\displaystyle\delta_{p}\left(A_{0}\cup\bigcup_{a_{i}\in(A^{1}\cup
A^{21})}T_{i}\right)$ $\displaystyle=\delta_{p}\left(\bigcup_{a_{i}\in
A^{1}}T_{i}\right)+\delta_{p}(A_{0}\cap
F_{0}^{\prime})+\delta_{p}\left(\bigcup_{a_{i}\in
A^{21}}T_{i}^{\prime}\right)$
$\displaystyle\geq|A^{1}|\eta+\varepsilon_{1}+(r_{N}(F_{0}^{\prime})-r_{N}((F_{0})_{A})\eta-
c_{o}-\varepsilon_{1}+\varepsilon_{2}+|A^{21}|\eta-\varepsilon_{2}$
$\displaystyle=(|A^{1}|+|A^{21}|)\eta+(r_{N}(F_{0}^{\prime})-r_{N}((F_{0})_{A})\eta-
c_{0}$ $\displaystyle\geq(|A^{1}|+|A^{21}+1)\eta-c_{0}.$

It follows by Lemma 8.1 a) that for all $a_{i}\in A^{1}\cup A^{21}$ and
$a_{j}\in A^{22}$, $T_{i}\cap T_{j}=\emptyset$. Thus

$\delta_{p}\left(A_{0}\cup\bigcup_{a_{i}\in(A^{1}\cup
A^{2})}T_{i}\right)\geq(|A^{1}|+|A^{21}+1)\eta-c_{0}+|A^{22}|\eta-
c_{1}=(|A^{1}|+|A^{2}|+1)\eta-c_{0}-c_{1}.$

$\square$

Let $\beta:[t]\rightarrow[k]$ be the function defined such that
$\beta(j)=i_{j},\ j\in[t].$ Let $K=(P_{\beta(1)},\dots,P_{\beta(t)})$ be the
corresponding path-tangle, consistent with $\mathcal{T}$, and rooted at
$Y_{0}$ where for all $j\in[t],\
y_{\beta(j)}\xrightarrow[W]{P_{\beta(j)}}y_{\beta(j)}^{\prime}.$ We shall now
construct the path-chain $K^{\prime}$ described in the proposition. By Claim
3, we have $\displaystyle{A_{0}\subseteq\bigcup_{j\in[t],a_{\beta(j)}\in
A^{\spadesuit}}T_{\beta(j)}}$. For convenience, we may assume that
$a_{\beta(t)}\in A^{\spadesuit}.$ Let
$K_{1}=(P_{\beta_{1}(1)},\dots,P_{\beta_{1}(t_{1})})$ be a path-chain in $K$
from $Y_{0}$ to $y_{\beta(t)}.$ That is, $\beta_{1}$ is a function
$\beta_{1}:[t_{1}]\rightarrow\\{\beta(1),\dots,\beta(t)\\}$ where
$y_{\beta_{1}(i)}\xrightarrow[W]{P_{\beta_{1}(i)}}y_{\beta_{1}(i)}^{\prime},\
i\in[t_{1}],$ $a_{\beta_{1}(1)}^{\prime}\in A_{0},$
$\beta_{1}(t_{1})=\beta(t),$ and for $i=2,\dots,t_{1},$
$a_{\beta_{1}(i)}^{\prime}\in T_{\beta_{1}(i-1)}$. If
$a_{\beta_{1}(1)}^{\prime}\in T_{\beta_{1}(t_{1})},$ then $K^{\prime}=K_{1}$
is the desired path-chain. Thus we may assume that
$a_{\beta_{1}(1)}^{\prime}\not\in T_{\beta_{1}(t_{1})}.$ Since
$\displaystyle{A_{0}\subseteq\bigcup_{j\in[t],\ a_{\beta(j)}\in
A^{\spadesuit}}T_{\beta(j)}}$, there exists $i^{\prime}\in[t]$ for which
$a_{\beta(i^{\prime})}\in A^{\spadesuit}$ and $a_{\beta_{1}(1)}^{\prime}\in
T_{\beta(i^{\prime})}.$ Now let
$K_{2}=(P_{\beta_{2}(1)},\dots,P_{\beta_{2}(t_{2})})$ be a path-chain in $K$
from $Y_{0}$ to $y_{\beta(i^{\prime})}.$ Here $\beta_{2}$ is a function
$\beta_{2}:[t_{2}]\rightarrow\\{\beta(1),\dots,\beta(t)\\}$ where
$y_{\beta_{2}(i)}\xrightarrow[W]{P_{\beta_{2}(i)}}y_{\beta_{2}(i)}^{\prime},\
i\in[t_{2}],$ and for $i=2,\dots,t_{2},$ $a_{\beta_{2}(i)}^{\prime}\in
T_{\beta_{2}(i-1)}$, $a_{\beta_{2}(1)}^{\prime}\in A_{0},$ and
$a_{\beta_{1}(1)}^{\prime}\in T_{\beta_{2}(t_{2})}$. If
$a_{\beta_{2}(1)}^{\prime}\in T_{\beta_{2}(t_{2})},$ then $K^{\prime}=K_{2}$
is the desired path-chain. On the other hand, if $a_{\beta_{2}(1)}^{\prime}\in
T_{\beta_{1}(t_{1})},$ then $K^{\prime}=K_{1}\circ K_{2},$ the composition of
$K_{2}$ with $K_{1}$, is the desired path-chain. Thus we may assume that
$a_{\beta_{2}(1)}^{\prime}\not\in T_{\beta_{1}(t_{1})}\cup
T_{\beta_{2}(t_{2})}.$ Continuing, there exists $i^{\prime\prime}\in[t]$ for
which $a_{\beta(i^{\prime\prime})}\in A^{\spadesuit}$ and
$a_{\beta_{2}(1)}^{\prime}\in T_{\beta(i^{\prime\prime})}.$

Let $K_{3}=(P_{\beta_{3}(1)},\dots,P_{\beta_{3}(t_{3})})$ be a path-chain in
$K$ from $Y_{0}$ to $y_{\beta(i^{\prime\prime})}.$ Here $\beta_{3}$ is a
function $\beta_{3}:[t_{3}]\rightarrow\\{\beta(1),\dots,\beta(t)\\}$ where
$y_{\beta_{3}(i)}\xrightarrow[W]{P_{\beta_{3}(i)}}y_{\beta_{3}(i)}^{\prime},\
i\in[t_{3}],$ $a_{\beta_{3}(1)}^{\prime}\in A_{0}$,
$a_{\beta_{2}(1)}^{\prime}\in T_{\beta_{3}(t_{3})},$ and for
$i=2,\dots,t_{3},$ $a_{\beta_{3}(i)}^{\prime}\in T_{\beta_{3}(i-1)}$. If
$a_{\beta_{3}(1)}^{\prime}\in T_{\beta_{3}(t_{3})},$ then $K^{\prime}=K_{3}$
is the desired path-chain. If $a_{\beta_{3}(1)}^{\prime}\in
T_{\beta_{2}(t_{2})},$ then $K^{\prime}=K_{2}\circ K_{3}$ is the desired path-
chain. If $a_{\beta_{3}(1)}^{\prime}\in T_{\beta_{1}(t_{1})},$ then
$K^{\prime}=K_{1}\circ K_{2}\circ K_{3}$ is the desired path-chain. Thus we
may assume that
$a_{\beta_{3}(1)}^{\prime}\not\in\bigcup_{i=1}^{3}T_{\beta_{i}(t_{i})}.$
Seeing as this process can not continue indefinitely, we must eventually
arrive at the desired path-chain $K^{\prime}$. $\square$

###  10.2 Finding a simple path-chain

One can use Proposition 10.4 to prove the following:

###### Proposition 10.5

There is a function $\xi:[s^{\prime}]\rightarrow[k]$ and a simple path-chain
consistent with $\mathcal{T}$, $K^{\prime}=(Q_{1},\dots,Q_{s^{\prime}})$,
where

  * •

$\forall i\in[s^{\prime}],\
y_{\xi(i)}\xrightarrow[W]{Q_{i}}y_{\xi(i)}^{\prime}$

  * •

$a_{\xi(s^{\prime})}\in A^{\spadesuit}$

  * •

$a_{\xi(1)}^{\prime}=\psi_{V}(y_{\xi(1)}^{\prime})\in A_{0}$

  * •

There is no pair $i,j\in[s^{\prime}],$ $0\leq j-i\leq s^{\prime}-2,$ for which
$a_{\xi(i)}^{\prime}=\psi_{V}(y_{\xi(i)}^{\prime})\in A_{0}$ and
$a_{\xi(j)}\in A^{\spadesuit}.$

  * Proof:

By Proposition 10.4, there is a function $\gamma:[s]\rightarrow[k]$ for which
$K^{\prime}=(P_{\gamma(1)},\dots,P_{\gamma(s)})$ is a path-chain where
$a_{\gamma(s)}\in A^{\spadesuit}$, and
$a_{\gamma(1)}^{\prime}=\psi_{V}(y_{\gamma(1)}^{\prime})\in A_{0}\cap
T_{\gamma(s)}.$ Among such path-chains, let $K^{\prime\prime}$ be one for
which the number of paths is minimum. Let $\xi:[s^{\prime}]\rightarrow[k]$ be
such that $K^{\prime\prime}=(Q_{1},\dots,Q_{s^{\prime}})$, where $\forall\
i\in[s^{\prime}],\ y_{\xi(i)}\xrightarrow[W]{Q_{i}}y_{\xi(i)}^{\prime}$ and
$a_{\xi(s^{\prime})}\in A^{\spadesuit}$ and
$a_{\xi(1)}^{\prime}=\psi_{V}(y_{\xi(1)}^{\prime})\in A_{0}.$ By minimality,
the paths $Q_{1},\dots,Q_{s^{\prime}}$ are vertex-disjoint; for if two of
these paths intersected, then Observation 6.5 implies that one reduce the
number of paths in $K^{\prime\prime}.$ By minimality, we also see that for
$j=2,\dots,t,$ $a_{\xi(j)}^{\prime}=\psi_{V}(y_{\xi(j)}^{\prime})\in
T_{\xi(j-1)}\backslash\bigcup_{j^{\prime}<j-1}T_{\xi(j^{\prime})}.$ Thus
$K^{\prime\prime}$ is a simple path-chain. The minimality of
$K^{\prime\prime}$ also implies that for all $1\leq j_{1}\leq j_{2}\leq t$
where $j_{2}-j_{1}\leq t-2,$ either $a_{\xi(j_{1})}^{\prime}\not\in A_{0},$ or
$a_{\xi(j_{2})}\not\in A^{\spadesuit}.$ $\square$

###  10.3 Proof of Theorem 10.1

By Proposition 10.5, there is a function $\xi:[s^{\prime}]\rightarrow[k]$ and
a simple path-chain consistent with $\mathcal{T}$,
$K^{\prime\prime}=(Q_{1},\dots,Q_{s^{\prime}}),$ where $\forall
i\in[s^{\prime}],\ y_{\xi(i)}\xrightarrow[W]{Q_{i}}y_{\xi(i)}^{\prime},$ and
$a_{\xi(s^{\prime})}\in A^{\spadesuit},$
$a_{\xi(1)}^{\prime}=\psi_{V}(y_{\xi(1)}^{\prime})\in A_{0}$, and for all
$1\leq i\leq j\leq s^{\prime}$, if $j-i\leq s^{\prime}-2,$ then either
$a_{\xi(i)}^{\prime}=\psi_{V}(y_{\xi(i)}^{\prime})\not\in A_{0},$ or
$a_{\xi(j)}\not\in A^{\spadesuit}.$ It now follows by Proposition 10.3 that
$A^{\prime}=A-\\{a_{\xi(1)},\dots,a_{\xi(s^{\prime})}\\}+\\{a_{\xi(1)}^{\prime},\dots,a_{\xi(s^{\prime})}^{\prime}\\}$
is a basis for $N.$ Thus the matching $W^{\prime}$ obtained from $W$ by
exchanging the matching edges of $W$ in $Q_{1}\cup\cdots\cup Q_{s^{\prime}}$
with the non-matching edges will produce a matching $W^{\prime}$ for which
$E_{W^{\prime}}$ is a basis for $M$ (since
$\psi_{V}(\overline{V}_{W^{\prime}})=A^{\prime}$). We claim that $W\preceq
W^{\prime}.$ Since $K^{\prime\prime}$ is consistent with $\mathcal{T}$ (an
$F_{0}$-target), we have that for all $i\in[s^{\prime}-1],$
$a_{\xi(i+1)}^{\prime}\in T_{\xi(i)}.$ Suppose $a_{\xi(i)}\in F_{0}\cup
A^{*}.$ Then $T_{\xi(i)}=F_{\xi(i)}^{\prime\prime}$ and this means that
$a_{\xi(i+1)}^{\prime}\in F_{\xi(i)}^{\prime\prime}.$ Thus when we replace
$a_{\xi(i)}$ by $a_{\xi(i+1)}^{\prime}$, the new basis element
$a_{\xi(i+1)}^{\prime}$ will also belong to $F_{\xi(i)}.$ Because of this, we
insure that $W\preceq W^{\prime}.$ Furthermore, since we replace
$a_{\xi(s^{\prime})}\in A-(F_{0}\cup A^{*})$ by $a_{\xi(1)}^{\prime}\in
F_{0}\cap T_{\xi(s^{\prime})},$ we have that
$\omega_{W^{\prime}}(F_{0})>\omega_{W}(F_{0})$.

Note that for each path $Q_{i},$ $\delta_{p}(y_{\xi(i)}^{\prime})>0$. As such,
we have $\forall v\in\overline{V}_{W^{\prime}},\ \delta_{p}(v)>0.$ If
$\omega_{W^{\prime}}(F_{0})<r_{N}(F_{0})$, then we can continue finding a
matching $W^{\prime\prime}$ for which
$\omega_{W^{\prime}}(F_{0})>\omega_{W^{\prime}}(F_{0})$ and $W^{\prime}\preceq
W^{\prime\prime}.$ Continuing the above process, one can find a matching
$W^{\prime\prime\prime}$ for which $W\preceq W^{\prime\prime\prime}$,
$\omega_{W^{\prime\prime}}(F_{0})=r_{N}(F_{0}).$ If there are sets
$F\in\mathfrak{F}$ for which $\omega_{W^{\prime\prime\prime}}(F)<r_{N}(F),$
then pick one such set of smallest rank, say $F_{0}^{\prime}$, and repeat the
previous process with $F_{0}^{\prime}$ in place of $F_{0}$, and
$W^{\prime\prime\prime}$ in place of $W.$ Repeating this procedure, we
eventually arrive at a matching $W^{*}$ for which $\forall F\in\mathfrak{F},\
\omega_{W^{*}}(F)=r_{N}(F).$

##  11 Proof of Theorem 1.2

We may assume that we have removed matchings $W_{1},\dots,W_{p}$ from $G$
where for all $i\in[p],$ $E_{W_{i}}$ is a basis in $M.$ Assuming
$\eta=n-p>c_{0}+c_{1},$ it follows by Theorem 10.1, one can find a matching
$W=W_{p+1}$ in $G_{p}$ for which $E_{W}$ is a basis, and i) $\forall e\in
E,\delta_{p+1}(e)\geq 0,$ and ii) $\forall F\in\mathfrak{F},\
\omega_{W}=r_{N}(F).$ Here $G_{p+1}=G_{p}-W_{p+1}.$ It follows that (6) holds
for all flats $F$ in $N$ and this in turn implies that for all flats $F\in N,$
$\delta_{p+1}(F)\leq r_{N}(F)(\eta-1).$ By Lemma 5.1, the graph $G_{p+1}$
contains a matching $W=W_{p+2}$ for which $E_{W_{p+2}}$ is a basis of $M.$ If
$\eta-1>c_{0}+c_{1}$, then the process can continue where one alters $W$ etc.
as before. Continuing, it is seen that one can construct at least
$n-c_{0}-c_{1}-1$ matchings $W_{1},W_{2},\dots$ for which $E_{W_{i}}$ is a
basis of $M.$

## References

  * [1] N. Alon and M. Tarsi.  Colorings and orientations of graphs.  Combinatorica, 12(2):125–134, 1992.
  * [2] J. Bondy and U. Murty.  Graph theory, volume 244 of Graduate Texts in Mathematics.  Springer, second edition, 2008.
  * [3] M. Bucić, M. Kwan, A. Pokrovskiy, and B. Sudakov.  Halfway to Rota’s Basis Conjecture.  International Mathematics Research Notices, 02 2020.  rnaa004.
  * [4] W. Chan.  An exchange property of matroid.  Discrete Math., 146(1-3):299–302, 1995.
  * [5] M. Cheung.  Computational proof of Rota’s basis conjecture for matroids of rank 4.  educ.jmu.edu/~duceyje/undergrad/2012/mike.pdf, 2012.  unpublished.
  * [6] S. Dong and J. Geelen.  Improved Bounds for Rota’s Basis Conjecture.  Combinatorica, 39(2):265–272, 2019.
  * [7] A. A. Drisko.  On the number of even and odd Latin squares of order $p+1$.  Adv. Math., 128(1):20–35, 1997.
  * [8] B. Friedman and S. McGuinness.  The Alon-Tarsi conjecture: a perspective on the main results.  Discrete Math., 342(8):2234–2253, 2019.
  * [9] J. Geelen and P. J. Humphries.  Rota’s basis conjecture for paving matroids.  SIAM J. Discrete Math., 20(4):1042–1045, 2006.
  * [10] D. G. Glynn.  The conjectures of Alon-Tarsi and Rota in dimension prime minus one.  SIAM J. Discrete Math., 24(2):394–399, 2010.
  * [11] R. Huang and G.-C. Rota.  On the relations of various conjectures on Latin squares and straightening coefficients.  Discrete Math., 128(1-3):225–236, 1994.
  * [12] G. Liu and R. Yu.  Graph Factors and Matching Extensions, volume 1.  Higher Education Press, first edition, 2009.
  * [13] S. Onn.  A colorful determinantal identity, a conjecture of Rota, and Latin squares.  Amer. Math. Monthly, 104(2):156–159, 1997.
  * [14] J. Oxley.  Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics.  Oxford University Press, Oxford, second edition, 2011.
  * [15] A. Pokrovskiy.  Rota’s basis conjecture holds asymptotically.  arXiv:2008.06045v1, 2020.
  * [16] M. Wild.  On Rota’s problem about $n$ bases in a rank $n$ matroid.  Adv. Math., 108(2):336–345, 1994.