$(v^{\prime},r^{\prime})\in\textit{Frontier}_{P^{\prime},R_{P^{\prime},d^{\prime},opt}}(d^{\prime})$
because any tuple
$(v^{\prime},r^{\prime\prime})\in\textit{Frontier}_{P^{\prime},R_{P^{\prime},d^{\prime},opt}}(d^{\prime})$
with $r^{\prime}\triangleleft r^{\prime\prime}$ would together with lemma 4.4
imply that there exists
$(v,r^{\prime\prime\prime})\in\textit{Frontier}_{P}(d)$ with $r\triangleleft
r^{\prime\prime\prime}$ which would mean that
$(v,r)\notin\textit{Frontier}_{P,R_{P,d,opt}}(d).$ Since for every
$(v^{\prime},r^{\prime})\in\textit{Frontier}_{P^{\prime},R_{P^{\prime},d^{\prime},opt}}(d^{\prime})$
there exists by definition no
$(v^{\prime},r^{\prime\prime})\in\textit{Frontier}_{P^{\prime}}(d^{\prime})$
with $r^{\prime}\triangleleft r^{\prime\prime},$ we can use lemma 4.4 to
follow that there exists $(v,r)\in\textit{Frontier}_{P}(d)$ such that
$v=\gamma(v^{\prime},1)$ and $r\equiv r^{\prime}.$ And similar to the argument
above we can follow from lemma 4.6 that
$(v,r)\in\textit{Frontier}_{P,R_{P,d,opt}}(d)$ proving the lemma.

######  Theorem 4.9.

For a parity game $P=(V,E,W_{0},\Omega),$ a nice $\vec{\mathcal{S}}$-DAG
$(T,\sigma)$ of $D=(V,E)$ and $d\in V(T)$ with
$\mathsf{N}^{\mathsf{out}}_{T}(d)=\\{c_{1},c_{2}\\},$ from
$\textit{Frontier}_{P,R_{P,c_{1},opt}}(c_{1})$ and
$\textit{Frontier}_{P,R_{P,c_{2},opt}}(c_{2})$ the set
$\textit{Frontier}_{P,R_{P,d,opt}}(d)$ can be calculated in $O(|V(D)|^{u(k)})$
for a function $u$ where $k$ is the width of $(T,\sigma).$

######  Proof 4.10.

The frontiers for $c_{1}^{\prime}$ and $c_{2}^{\prime}$ in the DAG
decomposition $(T^{\prime},(X_{t})_{t\in V(T)})$ are the same as the frontiers
$P$ has for $c_{1}$ and $c_{2}$ because the subgraphs of $D^{\prime}$ below
$c_{1}^{\prime}$ and $c_{2}^{\prime}$ are isomorphic to the subgraphs of $D$
below $c_{1}$ and $c_{2}$ with the isomorphism
$h(v^{\prime})=\gamma(v^{\prime},1)$ for $v^{\prime}\in X_{\succcurlyeq
c_{i}^{\prime}}$ for $i\in\\{1,2\\}.$ Given this, we can derive
$\textit{Frontier}_{P^{\prime},R_{P^{\prime},c_{1}^{\prime},opt}}(c_{1}^{\prime})$
and
$\textit{Frontier}_{P^{\prime},R_{P^{\prime},c_{2}^{\prime},opt}}(c_{2}^{\prime})$
from $\textit{Frontier}_{P,R_{P,c_{1},opt}}(c_{1})$ and
$\textit{Frontier}_{P,R_{P,c_{2},opt}}(c_{2}).$ We use the construction in
[BDH+12, Theorem 24] to obtain a nice DAG decomposition from
$(T^{\prime},(X_{t})_{t\in V(T)}).$ We then use theorem 4.1 to calculate
$\textit{Frontier}_{P^{\prime},R_{d^{\prime}}}(d^{\prime}).$ Since the sizes
of $X_{c_{1}^{\prime}},$ $X_{c_{2}^{\prime}},$ $X_{d^{\prime}}$ and
$X_{d_{\bot}^{\prime}}$ are all bounded by at most twice the width of
$(T,\sigma),$ this can be done in $O(|V(D)|^{u(k)})$ where $k$ is the width of
$(T,\sigma).$ By lemma 4.1 we know that
$R_{P^{\prime},d^{\prime},opt}\subseteq R_{d^{\prime}}\subseteq
R_{P^{\prime},d^{\prime},all}.$ Thus, we construct
$\textit{Frontier}_{P^{\prime},R_{P^{\prime},d^{\prime},opt}}(d^{\prime})$ by
removing all tuples $(v,r)$ from
$\textit{Frontier}_{P,R_{d^{\prime}}}(d^{\prime})$ for which there exists
$(v,r^{\prime})\in\textit{Frontier}_{P^{\prime},R_{d^{\prime}}}(d^{\prime})$
with $r\triangleleft r^{\prime}.$ The computation time for doing this by brute
force is in
$O(|\textit{Frontier}_{P^{\prime},R_{d^{\prime}}}(d^{\prime})|\cdot k)\subset
O(|V|^{u(k)}).$ Since
$\textit{Frontier}_{P^{\prime},R_{P^{\prime},d^{\prime},opt}}(d^{\prime})\equiv\textit{Frontier}_{P,R_{P,d,opt}}(d)$
by lemma 4.8 we can construct $\textit{Frontier}_{P,R_{P,d,opt}}(d)$ from
$\textit{Frontier}_{P^{\prime},R_{P^{\prime},d^{\prime},opt}}(d^{\prime})$ in
time linear to the size of
$\textit{Frontier}_{P^{\prime},R_{P^{\prime},d^{\prime},opt}}(d^{\prime}).$

See 1.2

######  Proof 4.11.

Having shown that for any type of successors we can calculate
$\textit{Frontier}_{P,R_{P,d,opt}}(d)$ of the predecessor $d$ in
$O(|V(D)|^{u(k)}),$ we can calculate the frontier
$\textit{Frontier}_{P,R_{P,s,opt}}(s)$ for the source $s$ in
$O((|V(D)|^{u(k)})).$ Since $V_{s}=V$ there are no finite plays in $V_{s}$
meaning that the only possible results in
$\textit{Frontier}_{P,R_{P,s,opt}}(s)$ are a win for the Odd player or a win
for the Even player. Since $\textit{Frontier}_{P,R_{P,s,opt}}(s)$ only
considers optimal strategies for the Even player
$\textit{Frontier}_{P,R_{P,s,opt}}(s)$ contains for each $v\in V$ the tuple
$(v,\textit{winEven})$ if there exists a strategy for the Even player which
wins the game when starting in $v$ and contains $(v,\textit{winOdd})$
otherwise. Thus, we can directly decide the winner of the parity game on $D$
for each starting vertex and subsequently decide the winner of the parity game
$P$.

## References

  * [ACP87] Stefan Arnborg, Derek G Corneil, and Andrzej Proskurowski.  Complexity of finding embeddings in a k-tree.  SIAM Journal on Algebraic Discrete Methods, 8(2):277–284, 1987\.
  * [AP89] Stefan Arnborg and Andrzej Proskurowski.  Linear time algorithms for np-hard problems restricted to partial k-trees.  Discrete applied mathematics, 23(1):11–24, 1989.
  * [BDH+12] Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, and Jan Obdržálek.  The dag-width of directed graphs.  Journal of Combinatorial Theory, Series B, 102(4):900–923, 2012\.
  * [BDHK06] Dietmar Berwanger, Anuj Dawar, Paul Hunter, and Stephan Kreutzer.  Dag-width and parity games.  In STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006. Proceedings 23, pages 524–536. Springer, 2006.
  * [BJG08] Jørgen Bang-Jensen and Gregory Z Gutin.  Digraphs: theory, algorithms and applications.  Springer Science & Business Media, 2008.
  * [BKTW21] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width i: tractable fo model checking.  ACM Journal of the ACM (JACM), 69(1):1–46, 2021.
  * [CJK+17] Cristian S Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.  Deciding parity games in quasipolynomial time.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 252–263, 2017.
  * [Cou90] Bruno Courcelle.  The monadic second-order logic of graphs. i. recognizable sets of finite graphs.  Information and computation, 85(1):12–75, 1990.
  * [DMŠ21] Clément Dallard, Martin Milanič, and Kenny Štorgel.  Treewidth versus clique number. ii. tree-independence number.  arXiv preprint arXiv:2111.04543, 2021.
  * [EGW01] Wolfgang Espelage, Frank Gurski, and Egon Wanke.  How to solve np-hard graph problems on clique-width bounded graphs in polynomial time.  In Graph-Theoretic Concepts in Computer Science: 27th InternationalWorkshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 Proceedings 27, pages 117–128. Springer, 2001.
  * [EJ91] E Allen Emerson and Charanjit S Jutla.  Tree automata, mu-calculus and determinacy.  In FoCS, volume 91, pages 368–377. Citeseer, 1991.
  * [GHK+16] Robert Ganian, Petr Hliněnỳ, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar.  Are there any good digraph width measures?  Journal of Combinatorial Theory, Series B, 116:250–286, 2016.
  * [Hat23] Meike Hatzel.  Dualities in graphs and digraphs.  Universitätsverlag der TU Berlin, 2023.
  * [HK08] Paul Hunter and Stephan Kreutzer.  Digraph measures: Kelly decompositions, games, and orderings.  Theoretical Computer Science, 399(3):206–219, 2008.
  * [JRST01] Thor Johnson, Neil Robertson, Paul D Seymour, and Robin Thomas.  Directed tree-width.  Journal of Combinatorial Theory, Series B, 82(1):138–154, 2001\.
  * [KLM09] Marcin Kamiński, Vadim V Lozin, and Martin Milanič.  Recent developments on graphs of bounded clique-width.  Discrete Applied Mathematics, 157(12):2747–2761, 2009.
  * [KO11] Stephan Kreutzer and Sebastian Ordyniak.  Digraph decompositions and monotonicity in digraph searching.  Theoretical Computer Science, 412(35):4688–4703, 2011.
  * [MBK21] Benjamin Merlin Bumpus and Zoltan A Kocsis.  Spined categories: generalizing tree-width beyond graphs.  arXiv e-prints, pages arXiv–2104, 2021.
  * [Obd06] Jan Obdrzálek.  Dag-width: connectivity measure for directed graphs.  In SODA, volume 6, pages 814–821, 2006.
  * [OOT93] Bogdan Oporowski, James Oxley, and Robin Thomas.  Typical subgraphs of 3-and 4-connected graphs.  Journal of Combinatorial Theory, Series B, 57(2):239–257, 1993\.
  * [Oum05] Sang-il Oum.  Rank-width and vertex-minors.  Journal of Combinatorial Theory, Series B, 95(1):79–100, 2005.
  * [Ree99] Bruce Reed.  Introducing directed tree width.  Electronic Notes in Discrete Mathematics, 3:222–229, 1999.
  * [RS84] Neil Robertson and Paul D Seymour.  Graph minors. iii. planar tree-width.  Journal of Combinatorial Theory, Series B, 36(1):49–64, 1984.
  * [RS86] Neil Robertson and Paul D Seymour.  Graph minors. v. excluding a planar graph.  Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986.


# Obstructions for Bounded Branch-depth
in Matroids

J. Pascal Gollin Supported by the Institute for Basic Science (IBS-R029-C1).
Kevin Hendrey111Note that there is also a different notion of branch-depth of
a matroid introduced by Kardoš, Král’, Liebenau, and Mach [KKLM-depth]. The
differences between these notions are discussed in [branchdepth]. Dillon
Mayhew Supported by a Rutherford Discovery Fellowship, managed by the Royal
Society Te Apārangi. Sang-il Oum111Note that there is also a different notion
of branch-depth of a matroid introduced by Kardoš, Král’, Liebenau, and Mach
[KKLM-depth]. The differences between these notions are discussed in
[branchdepth].

###### Abstract

DeVos, Kwon, and Oum introduced the concept of branch-depth of matroids as a
natural analogue of tree-depth of graphs. They conjectured that a matroid of
sufficiently large branch-depth contains the uniform matroid $U_{n,2n}$ or the
cycle matroid of a large fan graph as a minor. We prove that matroids with
sufficiently large branch-depth either contain the cycle matroid of a large
fan graph as a minor or have large branch-width. As a corollary, we prove
their conjecture for matroids representable over a fixed finite field and
quasi-graphic matroids, where the uniform matroid is not an option.

title = Obstructions for Bounded Branch-depth in Matroids, author = J. Pascal
Gollin, Kevin Hendrey, Dillon Mayhew, and Sang-il Oum, plaintextauthor = J.
Pascal Gollin, Kevin Hendrey, Dillon Mayhew, and Sang-il Oum, keywords =
matroids, branch-depth, branch-width, twisted matroids, representable
matroids, quasi-graphic matroids, year=2021, number=4, received=1 April 2020,
revised=22 January 2021, published=24 May 2021, doi=10.19086/aic.24227,

[classification=text]

##  1 Introduction

Motivated by the notion of tree-depth of graphs, DeVos, Kwon, and Oum
[branchdepth] introduced the branch-depth111Note that there is also a
different notion of branch-depth of a matroid introduced by Kardoš, Král’,
Liebenau, and Mach [KKLM-depth]. The differences between these notions are
discussed in [branchdepth]. of a matroid $M$ as follows. Recall that the
connectivity function $\lambda_{M}$ of a matroid $M$ is defined as
${\lambda_{M}(X)=r(X)+r(E(M)\setminus X)-r(E(M))}$, where $r$ is the rank
function of $M$. A _decomposition_ is a pair ${(T,\sigma)}$ consisting of a
tree $T$ with at least one internal node and a bijection $\sigma$ from
${E(M)}$ to the set of leaves of $T$. For an internal node $v$ of $T$, the
_width_ of $v$ is defined as

$\max_{\mathcal{P}^{\prime}\subseteq\mathcal{P}_{v}}\lambda_{M}\left(\bigcup_{X\in\mathcal{P}^{\prime}}X\right),$

where ${\mathcal{P}_{v}}$ is the partition of ${E(M)}$ into sets induced by
components of ${T-v}$ under $\sigma^{-1}$. The _width_ of a decomposition
${(T,\sigma)}$ is defined as the maximum width of its internal nodes. The
radius of ${(T,\sigma)}$ is the radius of $T$. A decomposition is a _$(k,r)$
-decomposition_ if its width is at most $k$ and its radius is at most $r$. The
_branch-depth_ of a matroid $M$ is defined to be the minimum integer $k$ for
which $M$ admits a ${(k,k)}$-decomposition if ${E(M)}$ has more than one
element, and is defined to be $0$ otherwise.

It is well known that graphs of large tree-depth contain a long path as a
subgraph (see the book of Nešetřil and Ossona de Mendez [NO2012]*Proposition
6.1). DeVos, Kwon, and Oum [branchdepth] made an analogous conjecture for
matroid branch-depth as follows. Since the cycle matroid of a path graph has
branch-depth at most $1$, paths no longer are obstructions for small branch-
depth. Instead, they use the cycle matroid of fans.

The _fan matroid_ ${M(F_{n})}$ is the cycle matroid of a fan $F_{n}$, which is
the union of a star $K_{1,n}$ together with a path with $n$ vertices through
the leaves of the star, see Figure 1. Note that the path with ${2n-1}$
vertices is a fundamental graph of ${M(F_{n})}$ (we will define the
fundamental graph of a matroid with respect to a base in Section 3).

Figure 1: The fan $F_{7}$. The fan matroid ${M(F_{7})}$ is the cycle matroid
of a fan $F_{7}$.

DeVos, Kwon, and Oum [branchdepth]*Propositions 4.1, 4.2, and Lemma 5.17
showed that the fan matroid ${M(F_{n})}$ has branch-depth ${\Theta(\log
n/\log\log n)}$. Hence, fan matroids are indeed obstructions for bounded
branch-depth.

We write $U_{n,2n}$ to denote the uniform matroid of rank $n$ on ${2n}$
elements. Now, here is the conjecture.

######  Conjecture 1.1 (DeVos, Kwon, and Oum [branchdepth]).

For every positive integer $n$, there is an integer $d$ such that every
matroid of branch-depth at least $d$ contains a minor isomorphic to
${M(F_{n})}$ or ${U_{n,2n}}$.

Our main theorem verifies their conjecture for matroids of bounded branch-
width as follows. Note that $U_{n,2n}$ has large branch-width if $n$ is big
and so there is no need for the following theorem to mention $U_{n,2n}$.

######  Theorem 1.2.

For positive integers $n$ and $w$, every matroid of branch-depth at least
${3(3w)^{2n}}$ contains a minor isomorphic to ${M(F_{n})}$ or has branch-width
more than $w$.

This allows us to obtain the following corollary for matroids representable
over a fixed finite field, since we can use a well-known grid theorem for
matroids of high branch-width by Geelen, Gerards, and Whittle [GGW:large-
branchwidth].

######  Corollary 1.3.

For every positive integer $n$ and every finite field $\operatorname{GF}(q)$,
there is an integer $d$ such that every $\operatorname{GF}(q)$-representable
matroid with branch-depth at least $d$ contains a minor isomorphic to
${M(F_{n})}$.

Previously, Kwon, McCarty, Oum, and Wollan [obstructions]*Corollary 4.9
verified the conjecture for binary matroids, as a corollary of their main
result about vertex-minors and rank-depth.

In a big picture, our proof follows the strategy of Kwon, McCarty, Oum, and
Wollan [obstructions]. As the branch-width is small, we can find, in every
large set, a large subset having small connectivity function value. We use
that recursively to find a long path in a fundamental graph, which results in
a minor isomorphic to the fan matroid.

The paper is organized as follows. In Section 2, we will introduce our
notations and a few results for matroids, branch-depth, and branch-width. In
Section 3, we will discuss the concept of twisted matroids introduced by
Geelen, Gerards, and Kapoor [GGK2000]. In Section 4, we prove our main
theorem, Theorem 1.2 by finding a ‘lollipop’ inside a twisted matroid. In
Section 5, we prove its consequences for matroids representable over a fixed
finite field and quasi-graphic matroids.

##  2 Preliminaries

###  2.1 Set systems

A _set system $S$_ is a pair ${(E,\mathcal{P})}$ consisting of a finite set
$E$ and a subset $\mathcal{P}$ of the power set of $E$. We call $E$ the
_ground set of $S$_ and may denote it by ${E(S)}$.

For ${i\in\\{1,2\\}}$ let ${S_{i}=(E_{i},\mathcal{P}_{i})}$ be set systems. A
map ${\varphi\colon E_{1}\to E_{2}}$ is an _isomorphism between $S_{1}$ and
$S_{2}$_ if it is bijective and ${P\in\mathcal{P}_{1}}$ if and only if
${\varphi(P)\in\mathcal{P}_{2}}$. We say $S_{1}$ and $S_{2}$ are _isomorphic_
if there is such an isomorphism.

Given two sets $X$ and $Y$, we denote by

${X\triangle Y:=(X\setminus Y)\cup(Y\setminus X)}$

the _symmetric difference of $X$ and $Y$_.

Given a set system ${S=(E,\mathcal{P})}$ and a subset ${X\subseteq E}$ we
define

$\mathcal{P}\triangle X:=\\{P\triangle X\colon
P\in\mathcal{P}\\}\qquad\textnormal{ and }\qquad\mathcal{P}|X:=\\{P\subseteq
X\colon P\in\mathcal{P}\\}.$

Given an integer $n$, we write ${[n]}$ for the set ${\\{i\in\mathbb{Z}\colon
1\leq i\leq n\\}}$ of positive integers up to $n$.

###  2.2 Matroids

Whitney [whitney] introduced matroids. We mostly follow the notation in
[oxley].

A _matroid_ $M$ is a set system ${(E,\mathcal{B})}$ satisfying the following
properties:

  1. (B1)

$\mathcal{B}$ is non-empty.

  2. (B2)

For every ${B_{1},B_{2}\in\mathcal{B}}$ and every ${x\in B_{1}\setminus
B_{2}}$, there exists an element $y\in B_{2}\setminus B_{1}$ such that
${(B_{1}\setminus\\{x\\})\cup\\{y\\}\in\mathcal{B}}$.

An element of $\mathcal{B}$ is called a _base_ of $M$. We denote the set of
bases of a matroid $M$ by ${\mathcal{B}(M)}$. A set $X$ is _independent_ if it
is a subset of a base, and we denote the set of independent sets of $M$ by
${\mathcal{I}(M)}$. A set $X$ is _dependent_ if it is not independent. A
_circuit_ is a minimal dependent set, and we denote the set of circuits of $M$
by ${\mathcal{C}(M)}$. The _rank_ of a set $X$ in a matroid $M$, denoted by
${r_{M}(X)}$, is defined as the size of a maximum independent subset of $X$.
We write ${r(M)}$ to denote ${r_{M}(E(M))}$, the _rank_ of $M$. The rank
function satisfies the _submodular inequality_ : for all ${X,Y\subseteq
E(M)}$,

$r_{M}(X)+r_{M}(Y)\geq r_{M}(X\cap Y)+r_{M}(X\cup Y).$ (1)

The _dual matroid_ of $M$, denoted by $M^{*}$, is the matroid on ${E(M)}$
where a set $B$ is a base of $M^{*}$ if and only if ${E(M)\setminus B}$ is a
base of $M$. It is well known that

$r_{M^{*}}(X)=r_{M}(E(M)\setminus X)+{\lvert{X}\rvert}-r(M).$

For a set ${X\subseteq E(M)}$, we write ${M\setminus X}$ for the matroid
${(E(M)\setminus X,\mathcal{B}^{\prime})}$, where $\mathcal{B}^{\prime}$ is
the set of maximal elements of ${\mathcal{I}(M)|(E(M)\setminus X)}$. This
operation is called the _deletion_. The _contraction_ is defined as
${M/X=(M^{*}\setminus X)^{*}}$. The _restriction_ is defined as
${M|X=M\setminus(E(M)\setminus X)}$. A matroid $N$ is a _minor_ of a matroid
$M$ if ${N=M\setminus X/Y}$ for some disjoint subsets $X$ and $Y$ of ${E(M)}$.
Note that if $N$ is a minor of $M$, then there are sets ${X,Y\subseteq E(M)}$,
where $X$ is independent in $M^{\ast}$ and $Y$ is independent in $M$, such
that ${N=M\setminus X/Y}$, see [oxley]*Lemma 3.3.2.

The _connectivity function_ $\lambda_{M}$ of a matroid $M$ is defined as

$\lambda_{M}(X)=r_{M}(X)+r_{M}(E(M)\setminus X)-r(M).$

It is easy to check that ${\lambda_{M}(X)=\lambda_{M^{*}}(X)}$.

The connectivity function satisfies the following three inequalities.

######  Proposition 2.1.

Let $M$ be a matroid.

  1. (F1)

${0\leq\lambda_{M}(X)\leq{\lvert{X}\rvert}}$ for all ${X\subseteq E(M)}$.

  2. (F2)

${\lambda_{M}(X)=\lambda_{M}(E(M)\setminus X)}$ for all ${X\subseteq E(M)}$.

  3. (F3)

${\lambda_{M}(X)+\lambda_{M}(Y)\geq\lambda_{M}(X\cap Y)+\lambda_{M}(X\cup Y)}$
for all ${X,Y\subseteq E(M)}$.

A matroid $M$ is _connected_ if ${\lambda_{M}(X)\neq 0}$ for all non-empty
proper subsets $X$ of ${E(M)}$. A _component_ of a matroid $M$ with
${{\lvert{E(M)}\rvert}\neq 0}$ is a minimal non-empty set $X$ such that
${\lambda_{M}(X)=0}$, and the empty set is the unique component of the empty
matroid ${(\emptyset,\\{\emptyset\\})}$. So a matroid is connected if and only
if it has exactly $1$ component, namely its ground set. By a slight abuse of
notation, if $C$ is a component of $M$, we may also refer to the matroid
${M|C}$ as a component of $M$.

For a matroid ${M=(E,\mathcal{B})}$, a base ${B\in\mathcal{B}}$, and an
element ${e\in E\setminus B}$, the _fundamental circuit of $e$ with respect to
$B$_, denoted by $C_{M}(e,B)$, is the circuit that is a subset of
${B\cup\\{e\\}}$. It is straightforward to see that such a circuit exists and
is unique.

We omit the subscript $M$ in $r_{M}$, $C_{M}$, $\lambda_{M}$ if it is clear
from the context.

######  Lemma 2.2.

If $N$ is a minor of a matroid $M$ and $X$ is a subset of ${E(N)}$, then

$\lambda_{M}(X)\leq\lambda_{M}(E(N))+\lambda_{N}(X).$

###### Proof.

Let ${N=M\setminus D/C}$. We may assume that $C$ is independent. Let
${Z:=C\cup D}$. Let ${E:=E(M)}$ and let ${Y:=E(N)\setminus X}$. Let
${r:=r_{M}}$ be the rank function of $M$. Then

  * •

${r_{N}(X)=r(X\cup C)-r(C)}$,

  * •

${r_{N}(Y)=r(Y\cup C)-r(C)}$, and

  * •

${r_{N}(X\cup Y)=r(X\cup Y\cup C)-r(C)}$.

Since $r$ is submodular, we deduce the following:

$\displaystyle\lambda_{M}(Z)+\lambda_{N}(X)$ $\displaystyle=r(Z)+r(X\cup
Y)-r(E)+r(X\cup C)+r(Y\cup C)-r(X\cup Y\cup C)-r(C)$
$\displaystyle=\big{(}r(X\cup C)+r(X\cup Y)-r(X\cup Y\cup
C)\big{)}+\big{(}r(Y\cup C)+r(Z)-r(C)\big{)}-r(E)$ $\displaystyle\geq
r(X)+r(Y\cup Z)-r(E)=\lambda_{M}(X).\qed$

######  Lemma 2.3.

If $N$ is a minor of a matroid $M$ and $X$ is a subset of ${E(M)}$, then

$\lambda_{M}(X)\leq\lambda_{N}(X\cap E(N))+{\lvert{E(M)\setminus
E(N)}\rvert}.$

###### Proof.

It is enough to prove the inequality when
${{\lvert{E(M)}\rvert}-{\lvert{E(N)}\rvert}=1}$. We may assume that
${N=M\setminus\\{e\\}}$ for some ${e\in E(M)}$ by taking the dual if
necessary. By (F2) applied to $\lambda_{M}$ and $\lambda_{N}$, we may assume
that ${e\in X}$. Let $r$ be the rank function of $M$. Observe that
${r(X\setminus\\{e\\})+r(\\{e\\})\geq r(X)}$ by equation (1) and
${r(E(M)\setminus\\{e\\})\leq r(E(M))}$. Thus

$\displaystyle\lambda_{M}(X)$ $\displaystyle=r(X)+r(E(M)\setminus X)-r(E(M))$
$\displaystyle\leq r(X\setminus\\{e\\})+r(\\{e\\})+r(E(M)\setminus
X)-r(E(M)\setminus\\{e\\})$
$\displaystyle\leq\lambda_{N}(X\setminus\\{e\\})+1.\qed$

###  2.3 Branch-depth

We will use the following lemma of DeVos, Kwon, and Oum [branchdepth]. Here we
state it for matroids.

######  Lemma 2.4 (DeVos, Kwon, and Oum [branchdepth]*Lemma 2.3).

Let ${m}$ be a non-negative integer, let $M$ be a matroid, and let
${\\{E_{i}\colon i\in[m]\\}}$ be a partition of ${E(M)}$ into non-empty sets
such that ${\lambda_{M}(E_{i})=0}$ for all ${i\in[m]}$. Let $k_{i}$ be the
branch-depth of ${M|E_{i}}$ for ${i\in[m]}$, and let ${k:=\max\\{k_{i}\colon
i\in[m]\\}}$. Then the branch-depth of $M$ is $k$ or ${k+1}$. Moreover, if the
branch-depth of $M$ is ${k+1}$, then it has a ${(k,k+1)}$-decomposition.

######  Lemma 2.5.

Let $m$ be a non-negative integer. Let $M$ be a matroid of branch-depth $m$
and let $X$, $Y$ be disjoint subsets of ${E(M)}$ such that ${X\cup
Y\neq\emptyset}$. Then ${M\setminus X/Y}$ has a component of branch-depth at
least ${m-{\lvert{X}\rvert}-{\lvert{Y}\rvert}}$.

###### Proof.

We follow the idea of [obstructions]*Lemma 2.6. If ${{\lvert{X\cup
Y}\rvert}\geq m}$, then there is nothing to prove. So we may assume that
${0<{\lvert{X\cup Y}\rvert}<m}$.

Let ${d:=m-{\lvert{X\cup Y}\rvert}-1}$, and suppose that every component of
${M\setminus X/Y}$ has branch-depth at most $d$. Let ${\\{C_{i}\colon
i\in[t]\\}}$ be the set of components of ${M\setminus X/Y}$. For each
${i\in[t]}$, if ${{\lvert{C_{i}}\rvert}\geq 2}$, then let
${(T_{i},\sigma_{i})}$ be a ${(d,d)}$-decomposition with a node $r_{i}$ of
$T_{i}$ having distance at most $d$ to every node of $T_{i}$. If
${{\lvert{C_{i}}\rvert}=1}$, then we let $T_{i}$ be the one-node graph on
${\\{r_{i}\\}}$ and take ${\sigma_{i}\colon C_{i}\to\\{r_{i}\\}}$.

We construct a decomposition ${(T,\sigma)}$ of $M$ by letting $T$ be a tree
obtained from the disjoint union of all $T_{i}$’s by adding a new node $r$ and
adding edges ${rr_{i}}$ for all ${i\in[t]}$, letting $\sigma$ map ${v\in
C_{i}}$ to ${\sigma_{i}(v)}$, and appending ${{\lvert{X\cup Y}\rvert}}$ leaves
to $r$ and letting $\sigma$ map each element of ${X\cup Y}$ to a distinct leaf
attached to $r$. Then ${(T,\sigma)}$ has radius at most ${d+1}$, which is
strictly less than $m$ since ${\lvert{X\cup Y}\rvert}\neq 0$. Furthermore, $r$
has width at most ${{\lvert{X\cup Y}\rvert}\leq m-1}$ by Lemma 2.3, and all
other internal nodes of $T$ have width at most ${d+{\lvert{X\cup
Y}\rvert}=m-1}$ by Lemma 2.2. This contradicts our assumption that $M$ has
branch-depth $m$. Thus we conclude that ${M\setminus X/Y}$ has a component
inducing a matroid of branch-depth at least
${d+1=m-{\lvert{X}\rvert}-{\lvert{Y}\rvert}}$. ∎

######  Lemma 2.6.

Let $m$ and $k$ be non-negative integers, let $M$ be a matroid, and let
$N_{1}$ and $N_{2}$ be minors of $M$ such that ${(E(N_{1}),E(N_{2}))}$ is a
partition of ${E(M)}$ and ${\lambda_{M}(E(N_{1}))\leq k}$. If all components
of both $N_{1}$ and ${N_{2}}$ have branch-depth at most $m$, then $M$ has
branch-depth at most ${\max(m+k,m+2)}$.

###### Proof.

By Lemma 2.4, both ${N_{1}}$ and ${N_{2}}$ have branch-depth at most ${m+1}$
and if any of them has branch-depth equal to ${m+1}$, then it has a
${(m,m+1)}$-decomposition.

For ${i\in[2]}$, if ${{\lvert{E(N_{i})}\rvert}>1}$, then let
${(T_{i},\sigma_{i})}$ be a ${(m,m+1)}$-decomposition of ${N_{i}}$ and let
$r_{i}$ be a node of $T_{i}$ within distance ${m+1}$ from every node of
$T_{i}$. If ${{\lvert{E(N_{i})}\rvert}=1}$, then let ${(T_{i},\sigma_{i})}$ be
the one-node tree on ${\\{r_{i}\\}}$ and take ${\sigma_{i}\colon
E(N_{i})\to\\{r_{i}\\}}$.

Let $T$ be a tree obtained from the disjoint union of $T_{1}$ and $T_{2}$ by
adding a new node $r$ and adding two edges ${rr_{1}}$ and ${rr_{2}}$. Let
$\sigma$ be the bijection from ${E(M)}$ to the set of leaves of $T$ induced by
$\sigma_{1}$ and $\sigma_{2}$. Then ${(T,\sigma)}$ is a decomposition of
radius at most ${m+2}$. Furthermore by Lemma 2.2, the width of ${(T,\sigma)}$
is at most ${m+k}$. Thus, the branch-depth of $M$ is at most
${\max(m+k,m+2)}$. ∎

###  2.4 Branch-width

Robertson and Seymour [graphminorsX] introduced the concept of branch-width. A
_subcubic_ tree is a tree such that every node has degree $1$ or $3$. A
_branch-decomposition_ of a matroid $M$ is defined as a pair ${(T,\sigma)}$
consisting of a subcubic tree $T$ and a bijection $\sigma$ from ${E(M)}$ to
the set of leaves of $T$. The _width_ of an edge $e$ in $T$ is defined as
${\lambda_{M}(A_{e})+1}$, where ${(A_{e},B_{e})}$ is the partition of ${E(M)}$
induced by the components of ${T\setminus e}$ under $\sigma^{-1}$. The _width_
of a branch-decomposition ${(T,\sigma)}$ is the maximum width of edges in $T$.
The _branch-width_ of a matroid $M$, denoted by $\operatorname{bw}(M)$, is
defined to be the minimum integer $k$ for which $M$ admits a branch-
decomposition of width $k$ if ${E(M)}$ has more than one element, and is
defined to be $1$ otherwise.

Here is a classical lemma on branch-width. For the completeness of this paper,
we include its proof. An equivalent lemma appears in [ggrw]*Lemma 4.2,
[os2006]*Theorem 5.1.

######  Lemma 2.7.

Let $w$ and $k$ be positive integers. Let $M$ be a matroid of branch-width at
most $w$ and let ${Z\subseteq E(M)}$. If ${{\lvert{Z}\rvert}\geq 3k+1}$, then
there is a partition $(X,Y)$ of $E(M)$ such that

$\lambda(X)<w\quad\text{ and }\quad\min({\lvert{Z\cap X}\rvert},{\lvert{Z\cap
Y}\rvert})>k.$

###### Proof.

Let ${(T,\sigma)}$ be a branch-decomposition of width at most $w$. We
construct a directed multigraph $D$ on $V(T)$ as follows. For each edge
${e=uv}$ of $T$, we add a directed edge from $w$ to $v$ if the component of
${T-e}$ containing $v$ has more than $k$ leaves in ${\sigma(Z)}$. If between
two nodes there are edges oriented in both directions, then that gives a
desired partition ${(A_{e},B_{e})}$. So we may assume that
${{\lvert{E(D)}\rvert}\leq{\lvert{E(T)}\rvert}}$. Since
${{\lvert{E(T)}\rvert}<{\lvert{V(T)}\rvert}}$, there is a node $v$ of $T$
having no outgoing edges in $D$. Since ${k\geq 1}$, every edge of $D$ incident
with a leaf of $T$ is oriented away from the leaf and therefore $v$ is an
internal node of $T$. However $v$ has degree $3$ in $T$, and so
${{\lvert{Z}\rvert}\leq 3k}$, contrary to the assumption that
${{\lvert{Z}\rvert}>3k}$. ∎

The following lemma is well-known and is an easy consequence of the
definitions.

######  Lemma 2.8 (Dharmatilake [Dharmatilake1996]).

If $N$ is a minor of $M$, then the branch-width of $N$ is at most the branch-
width of $M$. ∎

The branch-width of a graph $G$ is defined as follows. Let $T$ be a subcubic
tree, and let $\sigma$ be a bijection from ${E(G)}$ to the set of leaves of
$T$. Then we say that ${(T,\sigma)}$ is a _branch-decomposition_ of $G$. Let
$e$ be an edge of $T$, and let ${(A_{e},B_{e})}$ be a partition of ${E(G)}$
induced by the components of ${T\setminus e}$. The _width_ of $e$ is the
number of vertices that are incident with edges in both $A_{e}$ and $B_{e}$.
The _width_ of the branch-decomposition is the maximum width of an edge in
$T$. The _branch-width_ of $G$ is the minimum integer $k$ such that $G$ has a
branch-decomposition of width $k$ when $G$ has at least two edges (otherwise
the branch-width of $G$ is defined to be $0$).

Hicks and McMurray [HM07] and, independently, Mazoit and Thomassé [MT07]
proved that the branch-width of the graph $G$ is equal to the branch-width of
the graphic matroid ${M(G)}$, if $G$ has a cycle of length at least $2$.

##  3 Fundamental graphs and twisted matroids

###  3.1 The fundamental graph

Let $M$ be a matroid on ground set $E$ and let $B$ be a base of $M$. We define
the _fundamental graph ${G(M,B)}$ of $M$ with respect to $B$_ as the bipartite
graph with bipartition classes $B$ and ${E\setminus B}$ such that there is an
edge between ${b\in B}$ and ${e\in E\setminus B}$ if and only if $b$ is in the
fundamental circuit ${C_{M}(e,B)}$ of $e$ with respect to $B$.

The following statements about the fundamental graph are well known and are
easy consequences of the relevant definitions.

######  Proposition 3.1.

Let $M$ be a matroid and let $B$ be a base of $M$. Then the following
statements are true.

  1. (i)

$M$ is connected if and only if ${G(M,B)}$ is connected (see
[oxley]*Proposition 4.3.2).

  2. (ii)

${G(M,B)}$ and ${G(M^{*},E(M)\setminus B)}$ are equal.

It is well known that a matroid is binary if and only if for any base $B$, any
circuit $C$ is the symmetric difference of all fundamental circuits ${C(e,B)}$
with ${e\in C\setminus B}$ [oxley]*Theorem 9.1.2. Hence, every binary matroid
is completely determined by its fundamental graph and a colour class of any
proper $2$-colouring of that fundamental graph that is a base of the matroid.

For general matroids, such a complete determination fails; two distinct
matroids may have the same fundamental graph with respect to the same base.
But one can ask how a fundamental graph with respect to some base will change
when doing base exchange.

Note that if ${G(M,B)}$ has an edge $uv$, then
${B^{\prime}:=B\triangle\\{u,v\\}}$ is a base of $M$. The operation of
constructing ${G(M,B^{\prime})}$ from ${G(M,B)}$ is called a _pivot_ on $uv$.

######  Proposition 3.2 (Geelen, Gerards, and Kapoor [GGK2000]).

Let $M$ be a matroid, let $B$ be a base of $M$, and let $uv$ be an edge of
${G:=G(M,B)}$. Then with ${B^{\prime}:=B\triangle\\{u,v\\}}$ the following
statements about ${G^{\prime}:=G(M,B^{\prime})}$ are true.

  1. (i)

$\operatorname{N}_{G^{\prime}}(u)=\operatorname{N}_{G}(v)\triangle\\{u,v\\}$,
and
$\operatorname{N}_{G^{\prime}}(v)=\operatorname{N}_{G}(u)\triangle\\{u,v\\}$.

  2. (ii)

If ${x\notin\operatorname{N}_{G}(u)\cup\operatorname{N}_{G}(v)}$, then
$\operatorname{N}_{G^{\prime}}(x)=\operatorname{N}_{G}(x)$.

  3. (iii)

If ${x\in\operatorname{N}_{G}(u)}$ and
${y\in\operatorname{N}_{G}(v)\setminus\operatorname{N}_{G}(x)}$, then $xy$ is
an edge of $G^{\prime}$.

  4. (iv)

If ${G[\\{x,y,u,v\\}]}$ is a cycle of length $4$, then $xy$ is an edge of
$G^{\prime}$ if and only if ${B\triangle\\{x,y,u,v\\}}$ is a base of $M$.

Note that the first three rules of the proposition allow us to determine from
the graph $G$ the adjacency or non-adjacency in $G^{\prime}$ of some pairs of
vertices $x$ and $y$. This is not true of the fourth rule. However, if in
addition to the edge set of the fundamental graph we were given a list of
‘hyperedges’ ${\\{x,y,u,v\\}}$ for which ${B\triangle\\{x,y,u,v\\}}$ is a
base, then we could apply all four rules.

As an extension of that idea, Geelen, Gerards, and Kapoor [GGK2000] introduced
_twisted matroids_ , which can in a sense be viewed as ‘fundamental
hypergraphs’. We introduce their machinery in the next subsection.

###  3.2 Twisted matroids

Let ${S=(E,\mathcal{P})}$ be a set system and let ${X\subseteq E}$. We define
the _twist of $S$ by $X$_ as

$S\ast X:=(E,\mathcal{P}\triangle X).$

Moreover, we define the _restriction of $S$ to $X$_ as

$S[X]:=(E,\mathcal{P}|X),$

where, as noted before, ${\mathcal{P}|X:=\\{P\subseteq X\colon
P\in\mathcal{P}\\}}$.

######  Remark 3.3.

Let ${S=(E,\mathcal{P})}$ be a set system and let ${X,Y\subseteq E}$. Then

$(S\ast X)\ast Y=S\ast(X\triangle Y).$

A _twisted matroid_ $W$ is a set system $(E,\mathcal{F})$ satisfying the
following properties:

  1. (T1)

${\emptyset\in\mathcal{F}}$.

  2. (T2)

For every ${F_{1},F_{2}\in\mathcal{F}}$ and every ${e\in F_{1}\triangle
F_{2}}$, there is an ${f\in F_{1}\triangle F_{2}}$ such that
${F_{1}\triangle\\{e,f\\}\in\mathcal{F}}$.

  3. (T3)

There is a set ${B\subseteq E}$ such that ${{\lvert{B\cap
F}\rvert}={\lvert{(E\setminus B)\cap F}\rvert}}$ for all ${F\in\mathcal{F}}$.

We call $E$ the _ground set_ of $W$ and may denote it by ${E(W)}$. We call the
elements of $\mathcal{F}$ _feasible_ (with respect to $W$), and may denote the
set $\mathcal{F}$ by ${\mathcal{F}(W)}$. We call a set $B$ which satisfies
(T3) a _base of $W$_. We denote by ${\mathcal{B}(W)}$ the set of bases of $W$.

We observe that (T3) implies that every feasible set has even size. And in
fact it is enough to restrict our attention to feasible sets of size two, as
the following proposition will show.

######  Proposition 3.4.

Let ${W=(E,\mathcal{F})}$ be a set system satisfying (T1) and (T2). Then (T3)
is equivalent to the following axiom.

  1. (T3′)

There is a set ${B\subseteq E}$ such that ${{\lvert{B\cap
F}\rvert}={\lvert{(E\setminus B)\cap F}\rvert}}$ for all ${F\in\mathcal{F}}$
with ${\lvert{F}\rvert}\leq 2$.

Moreover, a set $B$ satisfies (T3) if and only if it satisfies (T3′).

###### Proof.

Assume (T3′) holds and let ${B\subseteq E}$ be as required. We will show that
$B$ satisfies (T3). Suppose for a contradiction that there is a set
${F\in\mathcal{F}}$ of minimum size for which ${{\lvert{B\cap
F}\rvert}\neq{\lvert{(E\setminus B)\cap F}\rvert}}$. Let
${X,Y\in\\{B,(E\setminus B)\\}}$ with ${{\lvert{X\cap F}\rvert}<{\lvert{Y\cap
F}\rvert}}$. By applying (T2) to $\emptyset$, $F$, and some ${e\in F}$, there
is an ${f\in F}$ such that
${\\{e,f\\}=\emptyset\triangle\\{e,f\\}\in\mathcal{F}}$ and hence ${e\neq f}$
by (T3′). By (T3′), exactly one of $e$ or $f$ is in $B$, so ${X\cap F}$ is
non-empty. Applying (T2) again to $F$, $\emptyset$, and some ${x\in X\cap F}$,
there is some ${z\in F}$ such that

${F^{\prime}:=F\triangle\\{x,z\\}=F\setminus\\{x,z\\}\in\mathcal{F}}.$

Now

${\lvert{F^{\prime}\cap X}\rvert}<{\lvert{F\cap X}\rvert}\leq{\lvert{F\cap
Y}\rvert}-1\leq{\lvert{F^{\prime}\cap Y}\rvert},$

contradicting that $F$ was a set of minimum size for which ${{\lvert{B\cap
F}\rvert}\neq{\lvert{(E\setminus B)\cap F}\rvert}}$. ∎

Note that this axiomatic definition of twisted matroids does not coincide with
the original definition of Geelen, Gerards, and Kapoor [GGK2000], in which
they defined twisted matroids to be the twist ${M\ast B}$ of a matroid $M$
with a base $B$ of $M$. The following proposition establishes together with
Remark 3.3 the equivalence of these definitions.

######  Proposition 3.5.

Let ${M=(E,\mathcal{B})}$ and ${W=(E,\mathcal{F})}$ be set systems and let
${B\subseteq E}$ such that ${W=M\ast B}$ (equivalently ${M=W\ast B}$). Then
the following statements are equivalent.

  1. (a)

$M$ is a matroid and ${B\in\mathcal{B}}$.

  2. (b)

$W$ is a twisted matroid and ${B\in\mathcal{B}(W)}$.

###### Proof.

Suppose (a) holds. Then ${\emptyset\in\mathcal{B}\triangle B=\mathcal{F}}$.
Since $M$ satisfies (B2), $W$ satisfies (T2). Finally, every element of
${\mathcal{F}\triangle B=\mathcal{B}}$ has size ${{\lvert{\emptyset\triangle
B}\rvert}={\lvert{B}\rvert}}$, so $B$ satisfies (T3).

Suppose (b) holds. By (T1) we have ${B\in\mathcal{B}}$ and hence (B1) holds.
For (B2), consider bases ${B_{1},B_{2}\in\mathcal{B}}$ and ${e\in
B_{1}\setminus B_{2}}$. Let ${F_{1}:=B_{1}\triangle B}$ and
${F_{2}:=B_{2}\triangle B}$. Then ${F_{1},F_{2}\in\mathcal{F}}$. Note that

${(B_{1}\setminus B_{2})\cup(B_{2}\setminus B_{1})=F_{1}\triangle F_{2}}.$

Then ${e\in F_{1}\triangle F_{2}}$ and hence by (T2) there is an ${f\in
F_{1}\triangle F_{2}}$ such that ${F_{1}\triangle\\{e,f\\}\in\mathcal{F}}$. If
${f\in B_{1}\setminus B_{2}}$, then either $F_{1}$ or
${F_{1}\triangle\\{e,f\\}}$ will contradict (T3). Hence, ${f\in B_{2}\setminus
B_{1}}$. ∎

For a twisted matroid $W$ we define

$\mathcal{M}(W):=\big{\\{}(M,B)\colon\textnormal{$M$ is a matroid and~{}$B$ is
a base of~{}$M$ such that }M\ast B=W\big{\\}}.$

If ${(M,B)\in\mathcal{M}(W)}$, then we say $M$ is _associated with $W$_. Note
that for a twisted matroid $W$ and a base $B$ of $W$ we have ${(W\ast
B,B)\in\mathcal{M}(W)}$ by Proposition 3.5 and Remark 3.3.

We define the _fundamental graph $G(W)$ of $W$_ as the graph on vertex set $E$
such that there is an edge between ${x,y\in E}$ if and only if
${\\{x,y\\}\in\mathcal{F}(W)}$. By (T3), the fundamental graph of $W$ is
bipartite. In fact, by (T3′), a set $B$ is a base of $W$ if and only if there
is a proper $2$-colouring of $G(W)$ in which $B$ is a colour class.

######  Proposition 3.6.

Let ${W=(E,\mathcal{F})}$ be a twisted matroid, let ${(M,B)\in\mathcal{M}(W)}$
and ${X\subseteq E}$. Then the following statements are true.

  1. (i)

${X\in\mathcal{F}(W)}$ if and only if ${B\triangle X\in\mathcal{B}(M)}$.

  2. (ii)

The fundamental graph ${G(M,B)}$ is equal to the fundamental graph ${G(W)}$.

  3. (iii)

${(M^{*},E\setminus B)\in\mathcal{M}(W)}$.

  4. (iv)

If $M$ is connected, then $\mathcal{M}(W)=\\{(M,B),(M^{*},E\setminus B)\\}$.

###### Proof.

For (i), suppose ${X\in\mathcal{F}}$. Then $M$ has a base ${B^{\prime}}$ such
that ${X=B\triangle B^{\prime}}$. By the properties of the symmetric
difference we obtain ${B^{\prime}=B\triangle X}$. Conversely, if ${B\triangle
X=B^{\prime}\in\mathcal{B}}$, then ${X=B^{\prime}\triangle B\in\mathcal{F}}$.

For (ii), note that $f$ is on the fundamental circuit of $e$ with respect to
$B$, if and only if ${(B\setminus\\{f\\})\cup\\{e\\}}$ is a base of $M$. So
${\\{e,f\\}=((B\setminus\\{f\\})\cup\\{e\\})\triangle B}$ is feasible if and
only if ${ef}$ is an edge of ${G(M,B)}$.

For (iii), note that for ${(M,B)\in\mathcal{M}(W)}$ we have

${\mathcal{B}(M^{*})=\mathcal{B}(M)\triangle E(M)=(\mathcal{F}\triangle
B)\triangle E(M)=\mathcal{F}\triangle(E(M)\setminus B)}.$

For (iv), suppose $M$ is connected. By Proposition 3.1(ii), ${G(M,B)=G(W)}$ is
connected and hence every proper 2-colouring of ${G(W)}$ has $B$ and
${E\setminus B}$ as its colour classes. ∎

###  3.3 Minors of twisted matroids

######  Proposition 3.7.

Let ${W=(E,\mathcal{F})}$ be a twisted matroid and let ${X,F\subseteq E}$.
Then the following statements are true.

  1. (i)

${W\ast F}$ is a twisted matroid if and only if ${F\in\mathcal{F}}$.
Additionally, ${W\ast F=M\ast(B\triangle F)}$ for any
${(M,B)\in\mathcal{M}(W)}$.

  2. (ii)

${W[X]}$ is a twisted matroid for which

${G(W[X])=G(W)[X]}\ \text{ and }\ {\\{B\cap X\colon
B\in\mathcal{B}(W)\\}\subseteq\mathcal{B}(W[X])}$

  3. (iii)

If ${F\in\mathcal{F}|X}$, then ${W[X]\ast F=(W\ast F)[X]}$.

  4. (iv)

For ${(M,B)\in\mathcal{M}(W)}$, we have

${W[X]\ast(B\cap X)=\big{(}M/(B\setminus X)\big{)}|X}.$

###### Proof.

For (i), suppose ${F\in\mathcal{F}}$. If ${(M,B)\in\mathcal{M}(W)}$, then

${W\ast F=(M\ast B)\ast F=M\ast(B\triangle F)}.$

Now ${W\ast F}$ is a twisted matroid by Propositions 3.6(i) and 3.5.
Conversely, suppose that ${W\ast F}$ is a twisted matroid. Now
${\emptyset\in\mathcal{F}(W\ast F)=\mathcal{F}\triangle F}$ by (T1). Hence
${F\in\mathcal{F}}$.

Both (ii) and (iii) are trivial consequences of the definitions.

For (iv), note that if $B^{\prime}$ is a base of $M$ for which
${F^{\prime}:=B^{\prime}\triangle B\subseteq X}$, then

${B^{\prime}\cap X=((B^{\prime}\triangle B)\triangle B)\cap
X=((B^{\prime}\triangle B)\cap X)\triangle(B\cap X)=F^{\prime}\triangle(B\cap
X)},$

and hence

$\big{\\{}B^{\prime}\cap X\colon B^{\prime}\in\mathcal{B}(M)\textnormal{ and
}B^{\prime}\triangle B\subseteq X\big{\\}}=\big{\\{}F^{\prime}\triangle(B\cap
X)\colon F^{\prime}\in\mathcal{F}|X\big{\\}}.$

Now since

${\mathcal{B}\big{(}(M/(B\setminus X))|X\big{)}=\big{\\{}B^{\prime}\cap
X\colon B^{\prime}\in\mathcal{B}(M)\textnormal{ and }B^{\prime}\triangle
B\subseteq X\big{\\}}}$

and

$\mathcal{F}(W[X])\triangle(B\cap X)=\big{\\{}F^{\prime}\triangle(B\cap
X)\colon F^{\prime}\in\mathcal{F}|X\big{\\}},$

we obtain (iv). ∎

A twisted matroid $U$ is called a _minor_ of a twisted matroid
${W=(E,\mathcal{F})}$ if there are sets ${X\subseteq E}$ and
${F\in\mathcal{F}}$ such that ${U=(W\ast F)[X]}$.

######  Proposition 3.8.

Let $U$ and $W$ be twisted matroids. Then the following statements are true.

  1. (i)

If $U$ is a minor of $W$, then every matroid $M$ associated with $W$ has a
minor $N$ associated with $U$.

  2. (ii)

If some matroid $M$ associated with $W$ has a minor $N$ associated with $U$,
then $U$ is a minor of $W$.
In particular, $M$ has a base $B$ such that ${(M\ast B)[E(U)]=N\ast(B\cap
E(U))=U}$.

###### Proof.

For (i), let ${(M,B^{\prime})\in\mathcal{M}(W)}$ and ${X\subseteq E}$ and
${F\in\mathcal{F}}$ such that ${U=(W\ast F)[X]}$. Then

${M=W\ast B^{\prime}=W\ast(B^{\prime}\triangle F\triangle F)=(W\ast
F)\ast(B^{\prime}\triangle F)},$

and hence for ${B:=B^{\prime}\triangle F}$ we have ${(M,B)\in\mathcal{M}(W\ast
F)}$. By Proposition 3.7(iv), we have that ${U\ast(B\cap X)}$ is a minor of
$M$, as desired.

For (ii), suppose for ${(M,B^{\prime})\in\mathcal{M}(W)}$ and
${(N,B^{\prime\prime})\in\mathcal{M}(U)}$ we have that $N$ is a minor of $M$.
Note that by the Scum Theorem [oxley]*Theorem 3.3.1 there is a set
${Z\subseteq E(M)\setminus E(N)}$ such that ${N=(M/Z)|E(N)}$ and the rank of
${M/Z}$ is equal to the rank of $N$. Without loss of generality $Z$ is
independent. Now $B^{\prime\prime}$ is independent in ${M/Z}$. By the equality
of the ranks, ${B:=B^{\prime\prime}\cup Z}$ is a base of $M$, and so
${N=(M/(B\setminus E(N)))|E(N)}$. Now since ${F:=B\triangle
B^{\prime}\in\mathcal{F}(W)}$ we obtain that ${(M,B)\in\mathcal{M}(W\ast F)}$,
and hence by Proposition 3.7(iv)

${(W\ast F)[E(N)]\ast(B\cap E(N))=N=U\ast B^{\prime\prime}=U\ast(B\cap
E(N))}.$

Therefore, ${(M\ast B)[E(U)]=(W\ast F)[E(N)]=U}$, as desired. ∎

Lastly, let us remark that the minor relation of twisted matroids is
transitive.

######  Proposition 3.9.

Let ${W=(E,\mathcal{F})}$ be a twisted matroid, let ${X^{\prime}\subseteq
X\subseteq E}$, let ${F\in\mathcal{F}}$, and ${F^{\prime}\in\mathcal{F}(W\ast
F)|X}$. Then

${F\triangle F^{\prime}\in\mathcal{F}}\ \text{ and }\ {(W\ast(F\triangle
F^{\prime}))[X^{\prime}]=(((W\ast F)[X])\ast F^{\prime})[X^{\prime}]}.$

###### Proof.

By Proposition 3.7(i), ${(W\ast F)\ast F^{\prime}}$ is a twisted matroid.
Since ${(W\ast F)\ast F^{\prime}=W\ast(F\triangle F^{\prime})}$, we have that
${F\triangle F^{\prime}\in\mathcal{F}}$ again by Proposition 3.7(i).

Now by Proposition 3.7(iii) we have

$(((W\ast F)[X])\ast F^{\prime})[X^{\prime}]=(((W\ast F)\ast
F^{\prime})[X])[X^{\prime}]=(W\ast(F\triangle F^{\prime}))[X^{\prime}].\qed$

###  3.4 More on the fundamental graph and twisted matroids

######  Proposition 3.10.

Let ${W=(E,\mathcal{F})}$ be a twisted matroid and let ${X\subseteq E}$. Then
the following statements are true.

  1. (i)

If $X\in\mathcal{F}$, then ${G(W)[X]}$ has a perfect matching (Brualdi
[brualdi]).

  2. (ii)

If ${G(W)[X]}$ has a unique perfect matching, then ${X\in\mathcal{F}}$
(Krogdahl [krogdahl]).

We deduce the following two propositions easily from the above proposition.

######  Proposition 3.11.

Let $M_{1}$ and $M_{2}$ be matroids on the common ground set $E$ sharing a
common base $B$. If the fundamental graphs of $M_{1}$ and $M_{2}$ with respect
to $B$ are equal and have no cycles, then ${M_{1}=M_{2}}$.

###### Proof.

Let ${X\subseteq E}$. Let $G$ denote the common fundamental graph with respect
to $B$, which by Proposition 3.6(ii) is equal to $G(M_{1}\ast B)=G(M_{2}\ast
B)$. Since $G$ is a forest, every induced subgraph has at most one perfect
matching and so for ${i\in[2]}$ by Proposition 3.10, $X$ is feasible in
${M_{i}\ast B}$ if and only if ${G[X]}$ has a perfect matching. Therefore,
${M_{1}\ast B=M_{2}\ast B}$, and hence ${M_{1}=M_{2}}$. ∎

######  Proposition 3.12.

Let $n$ be a positive integer. A matroid $M$ has a minor isomorphic to
${M(F_{n})}$ if and only if $M$ has a base $B$ such that $G(M,B)$ has an
induced path on ${2n-1}$ vertices, starting and ending in $B$.

###### Proof.

Suppose that $M$ has a minor $N$ isomorphic to ${M(F_{n})}$. Let $B^{\prime}$
be the base of $N$ corresponding to the star $K_{1,n}$ in ${M(F_{n})}$. Then
the fundamental graph of $N$ with respect to $B^{\prime}$ is a path on
${2n-1}$ vertices, starting and ending in $B^{\prime}$. By Proposition
3.8(ii), $M$ has a base $B$ such that ${(M\ast B)[E(N)]=N\ast(B\cap E(N))}$.
Now ${B\cap E(N)}$ is a base of $N$ by Proposition 3.5, so ${F:=(B\cap
E(N))\triangle B^{\prime}}$ is in ${\mathcal{F}(M\ast B)|E(N)}$, and hence in
${\mathcal{F}(M\ast B)}$. It follows that ${\hat{B}:=B\triangle F}$ is a base
of $M$ by Proposition 3.6(i). Note that

$\hat{B}\cap E(N)=(B\triangle((B\cap E(N))\triangle B^{\prime}))\cap
E(N)=B^{\prime},$

and hence ${(M\ast\hat{B})[E(N)]=N\ast B^{\prime}}$. Thus
${G(M,\hat{B})[E(N)]=G(N,B^{\prime})}$ by Propositions 3.6(ii) and 3.7(ii),
which is the required path.

Conversely, suppose there is a base $B$ of $M$ and a set ${X\subseteq E(M)}$
such that ${G(M,B)[X]}$ is a path on ${2n-1}$ vertices, starting and ending in
$B$. Let ${W:=M\ast B}$ and ${U:=(M\ast B)[X]}$. Since $U$ is a minor of $W$,
for some ${B^{\prime}\in\mathcal{B}(U)}$ the matroid ${N:=U\ast B^{\prime}}$
is a minor of $M$ by Proposition 3.8(i). Again, by Propositions 3.6(ii) and
3.7(ii), we have that

${G(M,B)[X]=G(U)=G(N,B^{\prime})}.$

Since ${G(M,B)[X]}$ is a forest, by Proposition 3.11, there is a unique
matroid with base $B^{\prime}$ whose fundamental graph is ${G(M,B)[X]}$, and
that matroid is isomorphic to $M(F_{n})$, as desired. ∎

We will need the following result about the change of the fundamental graph of
a twisted matroid when twisting with a feasible set, which in particular will
not change for the vertices not involved in the twist.

######  Proposition 3.13.

Let ${W=(E,\mathcal{F})}$ be a twisted matroid, let ${F\in\mathcal{F}}$, let
${e\in E\setminus F}$ such that there is no ${f\in F}$ for which ${\\{e,f\\}}$
is feasible, and let ${x\in E}$. Then ${\\{e,x\\}\in\mathcal{F}}$ if and only
if ${\\{e,x\\}\in\mathcal{F}\triangle F}$.

###### Proof.

If ${\\{e,x\\}\in\mathcal{F}\triangle F}$, then
${F^{\prime}:=\\{e,x\\}\triangle F\in\mathcal{F}}$. Since ${e\in F^{\prime}}$,
by (T1) and (T2) there is a ${y\in F^{\prime}}$ such that
${\\{e,y\\}\in\mathcal{F}}$. Now by the premise of this proposition, ${y=x}$,
as desired.

If ${\\{e,x\\}\in\mathcal{F}}$, then applying (T1) and (T2) for ${W\ast F}$,
there is a ${y\in\\{e,x\\}\triangle F}$ for which
${\\{e,y\\}\in\mathcal{F}\triangle F}$. So by the previous paragraph,
${\\{e,y\\}\in\mathcal{F}}$ and hence ${y\notin F}$. But then ${y=x}$, as
desired. ∎

If a matroid property is invariant under dualising components then for a
twisted matroid $W$ that property will be shared by every matroid associated
with $W$. So for such properties we are justified to call these properties of
the twisted matroid.

For example, we have the following proposition.

######  Proposition 3.14.

Let ${W}$ be a twisted matroid. Then for all
${(M,B),(M^{\prime},B^{\prime})\in\mathcal{M}(W)}$ and all ${X\subseteq E(W)}$
the following statements are true.

  1. (i)

$\lambda_{M^{\prime}}(X)=\lambda_{M}(X)$.

  2. (ii)

$X$ is a component of $M^{\prime}$ if and only if $X$ is a component of $M$.

  3. (iii)

$M^{\prime}$ is connected if and only if $M$ is connected.

  4. (iv)

The branch-depth of $M^{\prime}$ is equal to the branch-depth of $M$.

  5. (v)

The branch-width of $M^{\prime}$ is equal to the branch-width of $M$. ∎

Motivated by this proposition, we make the following definitions for a twisted
matroid ${W}$. Let ${(M,B)\in\mathcal{M}(W)}$ be arbitrary. We define the
_connectivity function_ $\lambda_{W}$ of $W$ as $\lambda_{M}$. A _component_
of $W$ is a component of $M$, and $W$ is _connected_ if $M$ is connected. We
define the _branch-depth_ and the _branch-width_ of $W$, respectively, as the
branch-depth and the branch-width of $M$, respectively.

Given these definitions, the related results for matroids in Section 2 also
hold for twisted matroids, and we will apply them for twisted matroids without
further explanation.

##  4 Lollipop minors of twisted matroids

In this section we complete the proof of Theorem 1.2. To do this, we introduce
the following class of twisted matroids.

###  4.1 Lollipops

######  Definition 4.1.

Let $a$, $b$ be non-negative integers. A twisted matroid $L$ on ground set
${S\dot{\cup}\\{z\\}\dot{\cup}C}$ with fundamental graph ${G:=G(L)}$ is called
an _${(a,b)}$ -lollipop_ if

  1. (1)

${{\lvert{S}\rvert}\geq a}$;

  2. (2)

$G$ is connected;

  3. (3)

${G[S\cup\\{z\\}]}$ is a path with terminal vertex $z$;

  4. (4)

${G[C]}$ is a connected component of ${G-z}$; and

  5. (5)

${L[C]}$ has branch-depth at least $b$.

We call the tuple ${(S,z,C)}$ the _witness_ of $L$, the twisted matroid
${L[C]}$ the _candy_ of $L$, and the graph ${G[S\cup\\{z\\}]}$ the _stick_ of
$L$.

In order to prove Theorem 1.2, we prove the following theorem.

######  Theorem 4.2.

For all non-negative integers $a$, $b$, and $w$, there is an integer $d$ such
that every twisted matroid $W$ of branch-width at most $w$ and branch-depth at
least $d$ has a minor which is an ${(a,b)}$-lollipop. Moreover, we may take
${d=b+3(3w)^{a}}$.

As we noted in Proposition 3.12, induced paths in the fundamental graph are
the correct object to look for when looking for fan matroids as a minor of a
matroid. So lollipops are defined in terms of a long path in the fundamental
graph to recover these minors, as we note in the following corollary of
Proposition 3.12. This corollary also shows that Theorem 4.2 implies Theorem
1.2.

######  Corollary 4.3.

Let $n$ be a positive integer and let $L$ be a ${(2n,0)}$-lollipop. Then every
matroid associated with $L$ contains a minor isomorphic to ${M(F_{n})}$. ∎

We also remark that Theorem 1.2 implies Theorem 4.2 because for all non-
negative integers $a$ and $b$, there is an integer $n$ such that for some base
$B$ of ${M(F_{n})}$ the twisted matroid ${M(F_{n})\ast B}$ is an
${(a,b)}$-lollipop, since $M(F_{n})$ has large branch-depth.

The reason for considering lollipops as opposed to fan matroids is that it
allows an inductive approach to find lollipop minors in twisted matroids of
sufficiently high branch-depth. If we find a lollipop whose candy has
sufficiently high branch-depth, then we can iteratively find another lollipop
as a minor of the candy. Having found a large enough number of such ‘nested’
lollipops, the small branch-width allows us to identify the stick of one of
the lollipops which we are able to ‘extend’ into its candy and ‘attach’ it to
a deletion minor of sufficiently large branch-depth. This way, we are able to
inductively find a lollipop with a longer stick.

Since lollipops are defined as twisted matroids, the choice of a base of the
original matroid is important. However, the following corollary of the results
of the previous section allows us a large amount of flexibility in exchanging
parts of the base of the matroid associated with the candy.

######  Corollary 4.4.

Let $a$ and $b$ be non-negative integers. Let $L$ be an $(a,b)$-lollipop with
witness ${(S,z,C)}$ and let ${F\in\mathcal{F}(L)|C}$. Then ${L\ast F}$ is an
${(a,b)}$-lollipop with witness ${(S,z,C)}$.

###### Proof.

Let ${G:=G(L)}$ and ${G^{\prime}:=G(L\ast F)}$. By Proposition 3.7(i), there
is a matroid $M$ associated with both $L$ and ${L\ast F}$. Since $G$ is
connected, so is $M$ by Proposition 3.1, and hence so is $G^{\prime}$.

By Proposition 3.7(iii), ${(L\ast F)[C]}$ is equal to ${L[C]\ast F}$, and
hence has branch-depth at least $b$ and is connected.

Now by Proposition 3.13, the neighbourhood of each ${s\in S}$ is the same in
$G$ and $G^{\prime}$. Hence ${G[S\cup\\{z\\}]=G^{\prime}[S\cup\\{z\\}]}$, and
no ${s\in S}$ has a neighbour in $C$ in $G^{\prime}$. Hence ${G^{\prime}[C]}$
is indeed a component of ${G^{\prime}-z}$. ∎

###  4.2 The induction

As mentioned in the previous subsection, we aim to prove Theorem 4.2 by
induction on $a$. For the start of the induction we consider the following
lemma.

######  Lemma 4.5.

Let $b$ be a non-negative integer. Every twisted matroid $W$ of branch-depth
at least ${b+2}$ has a minor which is a ${(0,b)}$-lollipop.

###### Proof.

By Lemma 2.4, $W$ has a component $C$ such that ${W[C]}$ has branch-depth at
least ${b+1}$. Let ${z\in C}$ be arbitrary. By Lemma 2.5,
${W[C\setminus\\{z\\}]}$ has a connected component $C^{\prime}$ of branch-
depth at least ${b}$. Now ${W[C^{\prime}\cup\\{z\\}]}$ is a $(0,b)$-lollipop
witnessed by ${(\emptyset,z,C^{\prime})}$ since
${G(W[C^{\prime}\cup\\{z\\}])}$ is connected. ∎

For the induction step, the following two lemmas are the main tools we will
need.

######  Lemma 4.6.

Let $a$, $b$, and $b^{\prime}$ be non-negative integers. Let $L$ be an
${(a,b)}$-lollipop with witness ${(S,z,C)}$ and let ${C^{\prime}\subseteq C}$
be non-empty such that

  1. (1)

${L[C^{\prime}]}$ is connected and has branch-depth at least ${b^{\prime}}$;
and

  2. (2)

the neighbourhood of $z$ in ${G:=G(L)}$ is disjoint from $C^{\prime}$.

Then there exist a set ${S^{\prime}\supseteq S}$ and an element
${z^{\prime}\in C\setminus C^{\prime}}$ such that
${L[S^{\prime}\cup\\{z^{\prime}\\}\cup C^{\prime}]}$ is an
${(a+1,b^{\prime})}$-lollipop with witness
${(S^{\prime},z^{\prime},C^{\prime})}$.

###### Proof.

There is a shortest path $P$ from $z$ to $C^{\prime}$ in ${G[C\cup\\{z\\}]}$.
Let $x$ be the unique vertex in ${V(P)\cap C^{\prime}}$, let $z^{\prime}$ be
the neighbour of $x$ in $P$, and let
${S^{\prime}:=S\cup(V(P)\setminus\\{x,z^{\prime}\\})}$. Now
${{\lvert{S^{\prime}}\rvert}\geq{\lvert{S}\rvert}+1\geq a+1}$, since $z$ has
no neighbour in $C^{\prime}$. Hence
${L^{\prime}:=L[S^{\prime}\cup\\{z^{\prime}\\}\cup C^{\prime}]}$ is an
${(a+1,b^{\prime})}$-lollipop witnessed by
${(S^{\prime},z^{\prime},C^{\prime})}$, as desired. ∎

If we can iteratively find lollipops in the candies of previously chosen
lollipops, the next lemma will allow us to find a feasible set $F$ such that
twisting by $F$ ‘displays’ all the lollipops at the same time.

######  Lemma 4.7.

Let $\ell$ be a positive integer and let $a$ and $g_{\ell}$ be non-negative
integers. Let $W$ be a twisted matroid and let ${(g_{i}\colon 0\leq i<\ell)}$
be a family of integers such that

  1. (1)

$W$ has branch-depth at least $g_{0}$;

  2. (2)

for all ${i<\ell}$, every minor of $W$ of branch-depth at least $g_{i}$
contains an ${(a,g_{i+1})}$-lollipop as a minor.

Then there is a feasible set $F$ and for each ${i\in[\ell]}$ there is a set
${E_{i}=S_{i}\dot{\cup}\\{z_{i}\\}\dot{\cup}C_{i}}$ such that for
${W^{\prime}:=W\ast F}$ the following properties hold.

  1. (i)

${L_{i}:=W^{\prime}[E_{i}]}$ is an ${(a,g_{i})}$-lollipop witnessed by
${(S_{i},z_{i},C_{i})}$ for all ${i\in[\ell]}$; and

  2. (ii)

${E_{i+1}\subseteq C_{i}}$ for all ${i\in[\ell-1]}$.

###### Proof.

Let ${W_{0}:=W}$ and let ${C_{0}:=E(W)}$. For ${i\in[\ell]}$ let
$L^{\prime}_{i}$ be an ${(a,g_{i})}$-lollipop with candy $W_{i}$ such that
$L^{\prime}_{i}$ is a minor of $W_{i-1}$. Note that $L^{\prime}_{i}$ exists by
the premise of the lemma. Let ${(S_{i},z_{i},C_{i})}$ be the witness of
$L^{\prime}_{i}$ and let ${E_{i}:=S_{i}\cup\\{z_{i}\\}\cup C_{i}}$.

Let ${F^{\prime}_{0}:=\emptyset}$. For ${i\in[\ell]}$, let
${F_{i-1}\in\mathcal{F}(W_{i-1})}$ be such that ${L^{\prime}_{i}=(W_{i-1}\ast
F_{i-1})[E_{i}]}$, and recursively define
${F^{\prime}_{i}:=F^{\prime}_{i-1}\triangle F_{i-1}}$. We now prove the
following.

######  Claim.

For ${i\in[\ell]}$, we have

  1. (a)

${F^{\prime}_{i}\in\mathcal{F}(W)}$,

  2. (b)

${L^{\prime}_{i}=(W\ast F^{\prime}_{i})[E_{i}]}$, and

  3. (c)

${F^{\prime}_{\ell-i}\triangle F^{\prime}_{\ell}\subseteq C_{\ell-i}}$.

###### Proof of Claim.

For ${i=1}$, (a) and (b) follow from the fact that ${F^{\prime}_{1}=F_{0}}$.
For ${i>1}$, assume inductively that ${F^{\prime}_{i-1}\in\mathcal{F}(W)}$ and
${L^{\prime}_{i-1}=(W\ast F^{\prime}_{i-1})[E_{i-1}]}$. Since
${W_{i-1}=L^{\prime}_{i-1}[C_{i-1}]}$, we have
${L^{\prime}_{i}=(L^{\prime}_{i-1}\ast F_{i-1})[E_{i}]}$. Therefore (a) and
(b) follow from Proposition 3.9.

For ${i=1}$, (c) follows from the fact that
${F^{\prime}_{\ell}=F^{\prime}_{\ell-1}\triangle F_{\ell-1}}$, and so
${F^{\prime}_{\ell-1}\triangle F^{\prime}_{\ell}=F_{\ell-1}}$. For ${i>1}$,
assume by induction that ${F^{\prime}_{\ell-(i-1)}\triangle
F^{\prime}_{\ell}\subseteq C_{\ell-(i-1)}}$. Since
${F^{\prime}_{\ell-(i-1)}=F^{\prime}_{\ell-i}\triangle F_{\ell-i}}$, we have
${F^{\prime}_{\ell-i}=F^{\prime}_{\ell-(i-1)}\triangle F_{\ell-i}}$ and hence
$F^{\prime}_{\ell-i}\triangle
F^{\prime}_{\ell}=(F^{\prime}_{\ell-(i-1)}\triangle
F^{\prime}_{\ell})\triangle F_{\ell-i}$. Hence, (c) follows from the inductive
hypothesis and the fact that both $C_{\ell-(i-1)}$ and $F_{\ell-i}$ are
subsets of $C_{\ell-i}$. ∎

Define ${F:=F^{\prime}_{\ell}}$. For ${i\in[\ell]}$, we have ${F\triangle
F^{\prime}_{i}\in\mathcal{F}(W\ast F)}$ by (a). Therefore, by (b) and (c), we
have

$\displaystyle L^{\prime}_{i}$ $\displaystyle=(W\ast F^{\prime}_{i})[E_{i}]$
$\displaystyle=(W\ast(F^{\prime}_{i}\triangle(F\triangle F)))[E_{i}]$
$\displaystyle=((W\ast F)[E_{i}])\ast(F\triangle F^{\prime}_{i}).$

Hence, by Corollary 4.4, ${L_{i}:=(W\ast F)[E_{i}]}$ is an
${(a,g_{i})}$-lollipop witnessed by ${(S_{i},z_{i},C_{i})}$, as required. ∎

Combining these two lemmas will be the heart of the induction step, as noted
in the following corollary of the previous two lemmas.

######  Corollary 4.8.

In the situation of Lemma 4.7, additionally let $b$ be a non-negative integer
and assume that

  1. $(\ast)$

there is an ${i\in[\ell]}$, a set ${C\subseteq C_{\ell}\subseteq C_{i}}$, and
a feasible set ${\hat{F}\in\mathcal{F}(L_{i})|C_{i}}$ such that

    1. (1)

$(L_{i}\ast\hat{F})[C]$ is connected and has branch-depth at least $b$; and

    2. (2)

the neighbourhood of $z$ in $G(L_{i}\ast\hat{F})$ is disjoint from $C$.

Then $W$ contains an ${(a+1,b)}$-lollipop as a minor. ∎

Up to this point, we have not used the fact that the twisted matroid has
bounded branch-width. In the next subsection we will prove the following
lemma, which will complete the proof of Theorem 4.2.

######  Lemma 4.9.

Let ${b\geq 0}$ and ${w>2}$ be integers. Suppose we are in the situation of
Lemma 4.7 with ${\ell:=3w-2}$ and ${g_{\ell}:=b+2w-1}$. If $W$ has branch-
width at most $w$, then we satisfy assumption $(\ast)$ ‣ 4.8 from Corollary
4.8.

###  4.3 Proof of Lemma 4.9

The following two lemmas are the final tools we will need for this proof.

######  Lemma 4.10.

Let ${w>2}$, ${k>0}$, and ${b\geq 0}$ be integers, let $W$ be a twisted
matroid of branch-width at most $w$ and let $Z$ and $C$ be disjoint subsets of
${E(W)}$ such that ${{\lvert{Z}\rvert}\geq 3k+1}$ and $W[C]$ has branch-depth
at least ${b+w-1}$. Then for some ${X\subseteq Z}$ and ${Y\subseteq C}$, the
following hold.

  1. (i)

${{\lvert{X}\rvert}\geq k+1}$;

  2. (ii)

${W[Y]}$ is connected and has branch-depth at least $b$;

  3. (iii)

${\lambda_{W[X\cup Y]}(X)<w}$.

###### Proof.

Since $W$ has branch-width at most $w$, so does ${W^{\prime}:=W[Z\cup C]}$ by
Lemma 2.8. Therefore, by Lemma 2.7, there exists a bipartition
${(X^{\prime},Y^{\prime})}$ of ${E(W^{\prime})}$ with
${\lambda_{W^{\prime}}(X^{\prime})<w}$ such that ${{\lvert{Z\cap
X^{\prime}}\rvert}>k}$ and ${{\lvert{Z\cap Y^{\prime}}\rvert}>k}$. Now we can
apply Lemma 2.6 to the matroids associated with ${W[X^{\prime}\cap C]}$ and
${W[Y^{\prime}\cap C]}$ as obtained from Proposition 3.8(i). Without loss of
generality $W[Y^{\prime}\cap C]$ has a component $Y$ of branch-depth at least
$b$. Let ${X:=X^{\prime}\cap Z}$. Since
${\lambda_{W^{\prime}}(X^{\prime})<w}$, it follows from Lemma 2.2 that
${\lambda_{W[X\cup Y]}(X)<w}$. ∎

######  Lemma 4.11.

Let ${w>2}$ be an integer and let $W$ be a twisted matroid. Then for every
bipartition ${(X,Y)}$ of ${E(W)}$ with ${{\lvert{X}\rvert}\geq w}$ and
${\lambda_{W}(X)<w}$ there is a base $B$ of $W$ and a set ${O\subseteq
X\setminus B}$ of size at most ${w}$ such that $O$ is a circuit in the matroid
${(W\ast B)/(B\cap X)}$.

###### Proof.

Let $B_{1}$ be a base of $W$. We set ${B_{2}:=E(W)\setminus B_{1}}$, as well
as ${M_{1}:=W\ast B_{1}}$ and ${M_{2}:=W\ast B_{2}}$. Note that
${M_{1}^{*}=M_{2}}$. Now we observe that

$\displaystyle\lambda_{W}(X)$
$\displaystyle=\lambda_{M_{1}}(X)=r_{M_{1}}(X)+r_{M_{2}}(X)-{\lvert{X}\rvert}$
$\displaystyle=(r_{M_{1}}(X)-{\lvert{X\cap
B_{1}}\rvert})+(r_{M_{2}}(X)-{\lvert{X\cap B_{2}}\rvert})$
$\displaystyle=r_{M_{1}/(B_{1}\cap X)}(X\setminus B_{1})+r_{M_{2}/(X\cap
B_{2})}(X\setminus B_{2}).$

Hence ${r_{M_{1}/(B_{1}\cap X)}(X\setminus B_{1})+r_{M_{2}/(X\cap
B_{2})}(X\setminus B_{2})<w}$. Since ${{\lvert{X}\rvert}\geq w}$, for some
base ${B\in\\{B_{1},B_{2}\\}}$ and for ${M:=W\ast B}$, we have that
${{\lvert{X\setminus B}\rvert}\geq r_{M/(B\cap X)}(X\setminus B)+1}$. It
follows that ${X\setminus B}$ contains a circuit $O$ of size at most ${w}$ in
${M/(B\cap X)}$. ∎

###### Proof of Lemma 4.9 .

By applying Lemma 4.10 to $W^{\prime}$, ${Z:=\\{z_{i}\colon i\in[\ell]\\}}$,
and $C_{\ell}$, there are sets ${X\subseteq Z}$ and ${Y\subseteq C_{\ell}}$
such that

  1. (i)

${{\lvert{X}\rvert}\geq w}$;

  2. (ii)

${W^{\prime}[Y]}$ is connected and has branch-depth at least ${b+w}$;

  3. (iii)

${\lambda_{W^{\prime}[X\cup Y]}(X)<w}$.

By applying Lemma 4.11 to ${W^{\prime\prime}:=W^{\prime}[X\cup Y]}$ there
exists a base $B$ of $W^{\prime\prime}$ and a set ${O\subseteq X\setminus B}$
of size at most ${w}$ such that $O$ is a circuit in ${(W^{\prime\prime}\ast
B)/(X\cap B)}$. Now, for the restriction of that matroid to ${O\cup Y}$, which
we call $M$, it follows that $O$ is a circuit of $M$. Note that since
${B\setminus E(M)=B\cap X}$, we get ${M=(W^{\prime\prime}[E(M)])\ast(B\cap
Y)}$ by Proposition 3.7(iv). Since ${M|Y=W^{\prime}[Y]\ast(B\cap Y)}$, it
follows from (ii) that $M$ has branch-depth at least ${b+w}$.

Let ${i\in[\ell]}$ be minimal such that ${z_{i}\in O}$. Then we obtain
${O\setminus\\{z_{i}\\}\subseteq C_{i}}$. Let $\hat{B}$ be a base of $M$ such
that ${z_{i}\notin\hat{B}}$ and $O$ is the fundamental circuit of $z_{i}$ with
respect to $\hat{B}$.

Since the branch-depth of ${M\ast\hat{B}}$ equals the branch-depth of $M$, by
Lemma 2.5 there is a component $C$ of ${(M\ast\hat{B})[E(M)\setminus O]}$ of
branch-depth at least $b$.

Now ${\hat{F}:=(B\cap E(M))\triangle\hat{B}}$ is feasible with respect to
${W^{\prime\prime}[E(M)]}$ by Proposition 3.6(i), and since
${z_{i}\notin\hat{F}}$ we get ${\hat{F}\in\mathcal{F}(L_{i})|C_{i}}$. By
Propositions 3.6(ii) and 3.7(ii),

${G(M,\hat{B})=G(W^{\prime}[E(M)]\ast\hat{F})=G(L_{i}\ast\hat{F})[E(M)]}.$

Hence, by our choice of $\hat{B}$ the neighbourhood of $z_{i}$ in
$G(L_{i}\ast\hat{F})$ is ${O\setminus z_{i}}$, which is disjoint from $C$. And
since $(L_{i}\ast\hat{F})[C]=(M\ast\hat{B})[C]$, we obtain condition $(\ast)$
‣ 4.8 of Corollary 4.8, as desired. ∎

###  4.4 Proof of Theorem 4.2

We now prove Theorem 4.2, which completes the proof of Theorem 1.2.

######  Definition 4.12.

Given non-negative integers $a$, $b$, $w$ and $i$ with ${w\geq 2}$, we make
the following definition, with ${\ell:=3w-2}$.

$g(a,b,w,i):=b+(2w-1)+\left((2w-1)\frac{(\ell^{a-1}-1)}{\ell-1}+2\ell^{a-1}\right)(\ell-i).$

For each integer ${w>2}$, we define a function
${f_{w}\colon\mathbb{N}^{2}\to\mathbb{N}}$ by ${f_{w}(a,b):=g(a,b,w,0)}$.

######  Lemma 4.13.

If $a$, $b$, $w$, and $i$ are non-negative integers with ${w\geq 2}$ and
${i<3w-2}$, then

  1. (i)

${f_{w}(0,b)=b+2}$,

  2. (ii)

${g(a,b,w,3w-2)=b+2w-1}$,

  3. (iii)

${g(a+1,b,w,i)=f_{w}(a,g(a+1,b,w,i+1))}$, and

  4. (iv)

${f_{w}(a,b)\leq b+3(3w-2)^{a}}$.

###### Proof.

Define ${\ell:=3w-2}$. For (i),

$\displaystyle f_{w}(0,b)$
$\displaystyle=g(0,b,w,0)=b+(2w-1)+\left((2w-1)\frac{\ell^{-1}-1}{\ell-1}+2\ell^{-1}\right)\ell$
$\displaystyle=b+(2w-1)+\left((2w-1)\frac{1-\ell}{\ell-1}+2\right)=b+2.$

Property (ii) is trivial. For (iii),

$\displaystyle f_{w}(a,g(a+1,b,w,i+1))$
$\displaystyle=g(a+1,b,w,i+1)+(2w-1)+\left((2w-1)\frac{\ell^{a-1}-1}{\ell-1}+2\ell^{a-1}\right)\ell$
$\displaystyle=\left(g(a+1,b,w,i)-\left((2w-1)\frac{\ell^{a}-1}{\ell-1}+2\ell^{a}\right)\right)+(2w-1)\frac{(\ell-1)+(\ell^{a}-\ell)}{\ell-1}+2\ell^{a}$
$\displaystyle=g(a+1,b,w,i).$

For (iv), note that ${2w-1\leq\ell-1}$, and hence

$\displaystyle
b+(2w-1)+\left((2w-1)\frac{\ell^{a-1}-1}{\ell-1}+2\ell^{a-1}\right)\ell$
$\displaystyle\leq b+\ell+(3\ell^{a-1}-1)\ell=b+3(3w-2)^{a}.\qed$

For convenience, we restate Theorem 4.2.

See 4.2

###### Proof.

We may assume without loss of generality that $w$ is at least $3$. We will
prove by induction on $a$ that the theorem holds with ${d:=f_{w}(a,b)}$ as in
Definition 4.12. The base case is true by Lemma 4.5 and Lemma 4.13(i). For the
induction step, let ${\ell:=3w-2}$, and note that the premise of Lemma 4.7
holds with the family ${(g_{i}\colon 0\leq i\leq\ell)}$, where ${g_{i}}$ is
defined as ${g(a+1,b,w,i)}$ as in Definition 4.12 for all ${i\in[\ell]}$, by
Lemma 2.8, Lemma 4.13, and the induction hypothesis. Hence, Lemma 4.9 together
with Corollary 4.8 completes the proof. ∎

##  5 Consequences

###  5.1 Matroids representable over a fixed finite field

Now we can prove Corollary 1.3, which we restate for the convenience of the
reader.

See 1.3

Since neither $U_{2,q+2}$ nor $U_{q,q+2}$ is representable over
$\operatorname{GF}(q)$, we will instead show the following stronger corollary,
implying Corollary 1.3.

######  Corollary 5.1.

For any positive integers $n$ and $q$, there is an integer $d$ such that every
matroid having no minor isomorphic to $U_{2,q+2}$ or $U_{q,q+2}$ with branch-
depth at least $d$ contains a minor isomorphic to ${M(F_{n})}$.

The _${m\times n}$ grid_ is the graph with vertices ${\\{(i,j)\colon
i\in[m],j\in[n]\\}}$, where ${(i,j)}$ and ${(i^{\prime},j^{\prime})}$ are
adjacent if and only if
${{\lvert{i-i^{\prime}}\rvert}+{\lvert{j-j^{\prime}}\rvert}=1}$. The above
corollary is obtained by using the following theorem of Geelen, Gerards, and
Whittle [GGW:large-branchwidth], because the cycle matroid of the ${n\times
n}$ grid contains ${M(F_{n})}$ as a minor.

######  Theorem 5.2 (Geelen, Gerards, and Whittle [GGW:large-
branchwidth]*Theorem 2.2).

For any positive integers $n$ and $q$, there is an integer ${w(n,q)}$ such
that every matroid having no minor isomorphic to $U_{2,q+2}$ or $U_{q,q+2}$
with branch-width at least ${w(n,q)}$ contains a minor isomorphic to the cycle
matroid of the ${n\times n}$ grid.

###### Proof of Corollary 5.1.

Let ${w:=w(n,q)}$ given by Theorem 5.2. Let $d$ be the integer given by
Theorem 1.2 for $n$ and $w$. Since the cycle matroid of the ${n\times n}$ grid
contains ${M(F_{n})}$ as a minor, we deduce the conclusion easily. ∎

###  5.2 Quasi-graphic matroids

Geelen, Gerards, and Whittle [quasi-graphic1] introduced the class of quasi-
graphic matroids, which includes the classes of graphic matroids, bicircular
matroids, frame matroids, and lift matroids. We will show that quasi-graphic
matroids of large branch-depth contain large fan minors, as a corollary of
Theorem 1.2.

Though the original definition of quasi-graphic matroids is due to Geelen,
Gerards, and Whittle [quasi-graphic1], we present the equivalent definition of
Bowler, Funk, and Slilaty [quasi-graphic2]. Let $G$ be a graph. A tripartition
${(\mathcal{B},\mathcal{L},\mathcal{F})}$ of cycles of $G$ into possibly empty
sets is called _proper_ if it satisfies the following properties.

  1. (i)

$\mathcal{B}$ satisfies the _theta property_ : if $C_{1}$, $C_{2}$ are two
cycles in $\mathcal{B}$ such that ${E(C_{1})\triangle E(C_{2})}$ is the edge
set of a cycle $C$, then $C$ is in $\mathcal{B}$.

  2. (ii)

Whenever $L$ is in $\mathcal{L}$ and $F$ is in $\mathcal{F}$, there is at
least one common vertex of $L$ and $F$.

A cycle is _balanced_ if it is in $\mathcal{B}$ and _unbalanced_ otherwise.
Let $X$ be a subset of ${E(G)}$. If the subgraph ${G[X]}$ contains no
unbalanced cycle, then we say that $X$ and ${G[X]}$ are _balanced_ , and
otherwise we say they are _unbalanced_. A _theta graph_ is a subgraph
consisting of three internally disjoint paths joining two distinct vertices.

For a graph $G$ and a proper tripartition
$(\mathcal{B},\mathcal{L},\mathcal{F})$ of its cycles, we define a matroid
${M=M(G,\mathcal{B},\mathcal{L},\mathcal{F})}$ by describing its circuits as
follows. A subset $X$ of ${E(G)}$ is a circuit of $M$ if and only if $X$ is
the edge set of one of the following:

  1. (1)

a balanced cycle,

  2. (2)

a theta graph containing no balanced cycle,

  3. (3)

the union of two edge-disjoint unbalanced cycles sharing exactly one vertex
(such a subgraph is called a _tight handcuff_),

  4. (4)

the union of two vertex-disjoint cycles in $\mathcal{L}$, and

  5. (5)

the union of two vertex-disjoint cycles in $\mathcal{F}$ and a minimal path
joining these two cycles (such a subgraph is called a _loose handcuff_).

If $\mathcal{B}$ contains every cycle of $G$, then ${M=M(G)}$ is a graphic
matroid. If $\mathcal{L}$ is empty, then $M$ is a _frame_ matroid, and if
$\mathcal{F}$ is empty, then $M$ is a _lift_ matroid. If both $\mathcal{B}$
and $\mathcal{L}$ are empty, then $M$ is a _bicircular_ matroid.

######  Proposition 5.3.

Let $G$ be a graph, and let ${(\mathcal{B},\mathcal{L},\mathcal{F})}$ be a
proper tripartition of the cycles of $G$. If $G$ has branch-width at most $w$,
then the quasi-graphic matroid ${M:=M(G,\mathcal{B},\mathcal{L},\mathcal{F})}$
has branch-width at most ${w+3}$.

###### Proof.

We may assume that $G$ has at least $2$ edges. Let ${(T,\sigma)}$ be a branch-
decomposition of the graph $G$ with width at most $w$. This means that
whenever $e$ is an edge of $T$, there are at most $w$ vertices incident with
both sides of a partition ${(A_{e},B_{e})}$ of ${E(G)}$ induced by the
components of ${T-e}$ under $L^{-1}$. We will demonstrate that
${\lambda_{M}(A_{e})\leq w+2}$ for every edge $e$, and then ${(T,\sigma)}$
will certify the branch-width of $M$ to be at most ${w+3}$.

Let $X$ be a subset of ${E(G)}$. Let ${c(X)}$ denote the number of connected
components in the subgraph ${G[X]}$, and let ${b(X)}$ denote the number of
these components that are balanced. Moreover, let ${\ell(X)}$ be $1$ if
${G[X]}$ contains a cycle in $\mathcal{L}$, and otherwise let ${\ell(X)}$ be
$0$. The rank ${r_{M}(X)}$ is given by the formula
${{\lvert{V(X)}\rvert}-b(X)}$ when ${G[X]}$ contains a cycle in $\mathcal{F}$,
and otherwise by ${{\lvert{V(X)}\rvert}-c(X)+\ell(X)}$ [quasi-graphic2]*Lemma
2.4.

Let $n$ be the number of vertices in $G$ and let ${E:=E(G)}$. Let $n_{A}$ and
$n_{B}$ be the number of vertices in the subgraphs ${G[A_{e}]}$ and
${G[B_{e}]}$, so that ${n_{A}+n_{B}-n}$ is the number of vertices incident
both with edges in $A_{e}$ and edges in $B_{e}$.

First assume that $\mathcal{F}$ is non-empty. Then ${r(M)=n-b(E)}$. We split
into three subcases depending on whether both, one, or neither of ${G[A_{e}]}$
and ${G[B_{e}]}$ contain cycles in $\mathcal{F}$. Assume that both
${G[A_{e}]}$ and ${G[B_{e}]}$ contain cycles in $\mathcal{F}$. Any subgraph of
a balanced subgraph is itself balanced, and it follows that
${b(A_{e})+b(B_{e})\geq b(E)}$. Therefore

$\displaystyle\lambda_{M}(A_{e})$
$\displaystyle=r_{M}(A_{e})+r_{M}(B_{e})-r(M)=(n_{A}-b(A_{e}))+(n_{B}-b(B_{e}))-(n-b(E))\leq{\lvert{V(A_{e})\cap
V(B_{e})}\rvert}\leq w$

as desired. Now assume that ${G[A_{e}]}$ contains a cycle in $\mathcal{F}$ but
that ${G[B_{e}]}$ does not. In this case ${b(A_{e})+c(B_{e})\geq b(E)}$, so

$\lambda_{M}(A_{e})=(n_{A}-b(A_{e}))+(n_{B}-c(B_{e})+\ell(B_{e}))-(n-b(E))\leq{\lvert{V(A_{e})\cap
V(B_{e})}\rvert}+\ell(B_{e})\leq w+1.$

If neither ${G[A_{e}]}$ nor ${G[B_{e}]}$ contains a cycle in ${\mathcal{F}}$,
then since ${c(A_{e})+c(B_{e})\geq c(E)\geq b(E)}$, we conclude that
${\lambda_{M}(A_{e})\leq w+\ell(A_{e})+\ell(B_{e})\leq w+2}$.

Now we assume that $\mathcal{F}$ is empty. Therefore

${r(M)=n-c(E)+\ell(E)},~{}{r(A_{e})=n_{A}-c(A_{e})+\ell(A_{e})},\textnormal{
and }{r(B_{e})=n_{B}-c(B_{e})+\ell(B_{e})}.$

As ${c(A_{e})+c(B_{e})\geq c(E)}$, it follows easily that
${\lambda_{M}(A_{e})\leq w+2}$, and this completes the proof. ∎

We will use the following grid theorem due to Robertson and Seymour. Note that
in [graphminorsV] they proved this theorem in terms of tree-width, but in
[graphminorsX] they established that graphs have small tree-width if and only
if they have small branch-width, yielding the following version of the
theorem.

######  Theorem 5.4 (Robertson and Seymour [graphminorsV]*(2.1) and
[graphminorsX]*(5.1)).

For any positive integer $n$, there is an integer $N(n)$ such that every graph
of branch-width at least ${N(n)}$ contains a minor isomorphic to the ${n\times
n}$ grid.

For a positive integer $n$, let $P_{n}^{\circ}$ be the graph obtained from the
path on $n$ vertices by adding one loop at each vertex. By comparing circuits,
it is easy to observe the following lemma.

######  Lemma 5.5.

For every positive integer $n$, the bicircular matroid
$M(P_{n}^{\circ},\emptyset,\emptyset,\mathcal{C}_{n}^{\circ})$ is isomorphic
to $M(F_{n})$, where $\mathcal{C}_{n}^{\circ}$ is the set of cycles of
$P_{n}^{\circ}$. ∎

######  Proposition 5.6.

For every positive integer ${n}$, there is an integer ${w}$ such that every
quasi-graphic matroid with branch-width at least $w$ contains a minor
isomorphic to ${M(F_{n})}$.

###### Proof.

We may assume that ${n>2}$. Let ${w:=N(n^{2})+3}$ where $N(n^{2})$ is the
integer given in Theorem 5.4.

Let ${M=M(G,\mathcal{B},\mathcal{L},\mathcal{F})}$ be a quasi-graphic matroid
of branch-width at least $w$. Assume for a contradiction that $M$ does not
have a minor isomorphic to ${M(F_{n})}$.

By Proposition 5.3, $G$ has branch-width at least $N(n^{2})$. By Theorem 5.4,
$G$ has a minor $G^{\prime}$ isomorphic to the ${n^{2}\times n^{2}}$ grid. We
may assume that $G^{\prime}$ is equal to the ${n^{2}\times n^{2}}$ grid.

As $G^{\prime}$ is obtained from $G$ by deleting edges and contracting non-
loop edges, it follows immediately from [quasi-graphic2]*Theorem 4.5 that
there is a proper tripartition
${(\mathcal{B}^{\prime},\mathcal{L}^{\prime},\mathcal{F}^{\prime})}$ of the
cycles of $G^{\prime}$ such that
${M^{\prime}:=M(G^{\prime},\mathcal{B}^{\prime},\mathcal{L}^{\prime},\mathcal{F}^{\prime})}$
is a minor of $M$.

First assume $\mathcal{L}^{\prime}$ contains a cycle of length $4$ with edge
set ${\\{c_{1},c_{2},c_{3},c_{4}\\}}$. By [quasi-graphic2]*Theorem 4.5,
${M^{\prime\prime}:=M^{\prime}/\\{c_{1},c_{2},c_{3}\\}}$ is a quasi-graphic
matroid. Let ${G^{\prime\prime}:=G^{\prime}/\\{c_{1},c_{2},c_{3}\\}}$, and let
${(\mathcal{B}^{\prime\prime},\mathcal{L}^{\prime\prime},\mathcal{F}^{\prime\prime})}$
be a proper tripartition of the cycles of $G^{\prime\prime}$ so that
${M^{\prime\prime}=M(G^{\prime\prime},\mathcal{B}^{\prime\prime},\mathcal{L}^{\prime\prime},\mathcal{F}^{\prime\prime})}$.
Again by [quasi-graphic2]*Theorem 4.5 we may assume that the cycle with edge
set $\\{c_{4}\\}$ is in $\mathcal{L}^{\prime\prime}$. Let $v$ be the vertex of
$G^{\prime\prime}$ that is incident with $c_{4}$. By definition, every cycle
in $\mathcal{F}^{\prime\prime}$ contains $v$. This means that
${M^{\prime\prime}=M(G^{\prime\prime},\mathcal{B}^{\prime\prime},\mathcal{L}^{\prime\prime}\cup\mathcal{F}^{\prime\prime},\emptyset)}$
(see [quasi-graphic2]*Section 2.3). For ${S\subseteq
E(M^{\prime\prime}/c_{4})}$, the set ${S\cup\\{c_{4}\\}}$ is dependent in
$M^{\prime\prime}$ if and only if $S$ contains the edge set of some cycle of
${G^{\prime\prime}/c_{4}}$, so
${M^{\prime\prime}/c_{4}=M(G^{\prime\prime}/c_{4})=M(G^{\prime}/\\{c_{1},c_{2},c_{3},c_{4}\\})}$.
As $n^{2}$ is greater than four, it follows that for some ${\alpha\in[n^{2}]}$
the graph $G^{\prime\prime}[\\{(i,j)\colon
i\in\\{\alpha,\alpha+1\\},~{}j\in[n^{2}]\\}]$ is a subgraph of
${G^{\prime\prime}/c_{4}}$ isomorphic to the ${2\times n^{2}}$ grid. By
contracting the edges in the path
${(\alpha,1)(\alpha,2)\cdots(\alpha,n^{2})}$, we obtain a minor isomorphic to
$F_{n^{2}}$. Now ${n^{2}>n}$ implies that $M$ has a minor isomorphic to
${M(F_{n})}$, a contradiction. Therefore $\mathcal{L}^{\prime}$ contains no
cycle of length $4$.

Consider the subgraph ${G_{1}:=G^{\prime}[\\{(i,j)\colon
i\in\\{1,2\\},~{}j\in[n^{2}]\\}]}$. If $G_{1}$ contains $n$ vertex-disjoint
cycles of length $4$ in $\mathcal{F}^{\prime}$, then $M^{\prime}$ has a minor
isomorphic to
${M(P_{n}^{\circ},\emptyset,\emptyset,\mathcal{C}_{n}^{\circ})}$, where
$\mathcal{C}_{n}^{\circ}$ is the set of cycles of $P_{n}^{\circ}$,
contradicting our assumption by Lemma 5.5.

Since the ${2\times n}$ grid contains $F_{n}$ as a minor, by our assumption,
any sequence of consecutive balanced cycles of length $4$ in $G_{1}$ contains
at most ${n-2}$ such cycles. As $G_{1}$ contains no cycles of length $4$ in
$\mathcal{L}^{\prime}$, and at most $n-1$ vertex-disjoint cycles of length $4$
in $\mathcal{F}^{\prime}$, it follows that $G_{1}$ contains at most
${(n-2)n+2(n-1)=n^{2}-2}$ cycles of length $4$. This is impossible, as $G_{1}$
has at least ${n^{2}-1}$ cycles of length $4$. ∎

Now it is routine to combine Proposition 5.6 with Theorem 1.2 to deduce the
following result.

######  Corollary 5.7.

For every positive integer ${n}$, there is an integer ${d}$ such that every
quasi-graphic matroid with branch-depth at least $d$ contains a minor
isomorphic to ${M(F_{n})}$. ∎

###  5.3 General matroids

The following conjecture about branch-width is due to Johnson, Robertson, and
Seymour.

######  Conjecture 5.8 (Johnson, Robertson, and Seymour; see [excluding-
uniform]*Conjecture 6.1).

For every positive integer ${n}$, there is an integer ${d}$ such that every
matroid of branch-width at least $d$ contains a minor isomorphic to either

  * •

the cycle matroid of the ${n\times n}$ grid;

  * •

the bicircular matroid of the ${n\times n}$ grid;

  * •

the dual of the bicircular matroid of the ${n\times n}$ grid; or

  * •

the uniform matroid $U_{n,2n}$.

Note that all matroids appearing in this conjecture have large branch-width,
making them necessary obstructions.

Hence, Theorem 1.2 yields the following corollary.

######  Corollary 5.9.

Conjecture 5.8 implies Conjecture 1.1.

###### Proof.

Since both the cycle matroid and the bicircular matroid of the ${n\times n}$
grid are quasi-graphic and both have large branch-depth, by Corollary 5.7, if
a matroid $M$ contains a minor isomorphic to one of them, it contains a minor
of the fan matroid as well. It follows that if a matroid $M$ contains a minor
isomorphic to the dual of the bicircular matroid of the ${n\times n}$ grid,
then it contains the dual of the fan matroid. By Propositions 3.12 and
3.1(ii), $M(F_{n})^{\ast}$ contains a minor isomorphic to $M(F_{n-1})$. ∎

## Acknowledgments

We wish to thank the reviewers for their many helpful suggestions. We are
particularly grateful to the anonymous reviewer who took the time to determine
the explicit bound in our main theorem from what was previously a somewhat
opaque recursive definition.

## References

[jpg] J. Pascal Gollin
Discrete Mathematics Group
Institute for Basic Science
Daejeon, Korea
pascalgollinibsrekr
https://dimag.ibs.re.kr/home/gollin [kh] Kevin Hendrey
Discrete Mathematics Group
Institute for Basic Science
Daejeon, Korea
kevinhendreyibsrekr
https://sites.google.com/view/kevinhendrey [dm] Dillon Mayhew
School of Mathematics and Statistics
Te Herenga Waka, Victoria University of Wellington
Wellington, New Zealand
dillonmayhewvuwacnz
https://homepages.ecs.vuw.ac.nz/~mayhew/ [so] Sang-il Oum
Discrete Mathematics Group Department of Mathematical Sciences Institute for
Basic Science KAIST Daejeon, Korea Daejeon, Korea
sangilibsrekr
https://dimag.ibs.re.kr/home/sangil