Abstract Hliněný’s Theorem shows that any sentence in the monadic second-order logic of matroids can be tested in polynomial time, when the input is limited to a class of $${\mathbb {F}}$$ F -representable matroids with bounded branch-width (where $${\mathbb {F}}$$ F is a finite field). If each matroid in a class can be decomposed by a subcubic tree in such a way that only a bounded amount of information flows across displayed separations, then the class has bounded decomposition-width. We introduce the pigeonhole property for classes of matroids: if every subclass with bounded branch-width also has bounded decomposition-width, then the class is pigeonhole. An efficiently pigeonhole class has a stronger property, involving an efficiently-computable equivalence relation on subsets of the ground set. We show that Hliněný’s Theorem extends to any efficiently pigeonhole class. In a sequel paper, we use these ideas to extend Hliněný’s Theorem to the classes of fundamental transversal matroids, lattice path matroids, bicircular matroids, and $$H$$ H -gain-graphic matroids, where H is any finite group. We also give a characterisation of the families of hypergraphs that can be described via tree automata: a family is defined by a tree automaton if and only if it has bounded decomposition-width. Furthermore, we show that if a class of matroids has the pigeonhole property, and can be defined in monadic second-order logic, then any subclass with bounded branch-width has a decidable monadic second-order theory.

A connected matroid $M$ is unbreakable if, for each of its flats $F$, the matroid $M/F$ is connected or, equivalently, if $M^*$ has no two skew circuits. Pfeil showed that a simple graphic matroid $M(G)$ is unbreakable exactly when $G$ is either a cycle or a complete graph. We extend this result to describe which graphs are the underlying graphs of unbreakable frame matroids.

A sufficiently large connected matroid $M$ contains a big circuit or a big cocircuit. Wu showed that we can ensure that $M$ has a big circuit or a big cocircuit containing any chosen element of $M$. In this paper, we prove that, for a fixed connected matroid $N$, if $M$ is a sufficiently large connected matroid having $N$ as a minor, then, up to duality, either $M$ has a big connected minor in which $N$ is a spanning restriction and the deletion of $E(N)$ is a large connected uniform matroid, or $M$ has, as a minor, the $2$-sum of a big circuit and a connected single-element extension or coextension of $N$. In addition, we find a set of unavoidable minors for the class of graphs that have a cycle and a bond with a big intersection.

Let $\mathcal{N}$ be a set of matroids. A matroid $M$ is strictly $\mathcal{N}$-fragile if $M$ has a member of $\mathcal{N}$ as minor and, for all $e \in E(M)$, at least one of $M\hspace{-0.5pt}\backslash e$ and $M/e$ has no minor in $\mathcal{N}$. In this paper we give a structural description of the strictly $\{U_{2,5},U_{3,5}\}$-fragile matroids that have six inequivalent representations over $\mathrm{GF}(5)$. Roughly speaking, these matroids fall into two classes. The matroids without an $\{X_8, Y_8, Y_8^{*}\}$-minor are constructed, up to duality, from one of two matroids by gluing wheels onto specified triangles. On the other hand, those matroids with an $\{X_8, Y_8, Y_8^{*}\}$-minor can be constructed from a matroid in $\{X_8, Y_8, Y_8^{*}\}$ by repeated application of elementary operations, and are shown to have path width 3. The characterization presented here will be crucial in finding the explicit list of excluded minors for two classes of matroids: the Hydra-5-representable matroids and the 2-regular matroids.

We prove that the maximum size of a simple binary matroid of rank $r \geq 5$ with no $AG(3,2)$-minor is $\binom{r+1}{2}$ and characterize those matroids achieving this bound. When $r \geq 6$, the graphic matroid $M(K_{r+1})$ is the unique matroid meeting the bound, but there are a handful of matroids of lower ranks meeting or exceeding this bound. In addition, we determine the size function for nongraphic simple binary matroids with no $AG(3,2)$-minor and characterize the matroids of maximum size for each rank.

Let $\mathrm{AG}(3,2)\>\raisebox{-0.5pt}{\rotatebox{90}{$\Bowtie$}}\>U_{1,1}$ denote the binary matroid obtained from $\mathrm{AG}(3,2)\oplus U_{1,1}$ by completing the 3-point lines between every element in $\mathrm{AG}(3,2)$ and the element of $U_{1,1}$. We prove that every internally 4-connected binary matroid that does not have a minor isomorphic to $M(K_{5}\backslash e)$ is isomorphic to a minor of $(\mathrm{AG}(3,2)\>\raisebox{-0.5pt}{\rotatebox{90}{$\Bowtie$}}\>U_{1,1})^{*}$.

Seymour's decomposition theorem [J. Combin. Theory Ser. B, 28 (1980), pp. 305–359] for regular matroids states that any matroid representable over both $\mathrm{GF}(2)$ and $\mathrm{GF}(3)$ can be obtained from matroids that are graphic, cographic, or isomorphic to $R_{10}$ by 1-, 2-, and 3-sums. It is hoped that similar characterizations hold for other classes of matroids, notably for the class of near-regular matroids. Suppose that all near-regular matroids can be obtained from matroids that belong to a few basic classes through k-sums. Also suppose that these basic classes are such that, whenever a class contains all graphic matroids, it does not contain all cographic matroids. We show that, in that case, 3-sums will not suffice.

We investigate an approach to matroid complexity that involves describing a matroid via a list of independent sets, bases, circuits, or some other family of subsets of the ground set. The computational complexity of algorithmic problems under this scheme appears to be highly dependent on the choice of input type. We define an order on the various methods of description, and we show how this order acts upon 10 types of input. We also show that under this approach several natural algorithmic problems are complete in classes thought not to be equal to P.