Abstract. A partitioned matroid [Formula: see text] consists of a matroid [Formula: see text] and a partition [Formula: see text] of its ground set. As such structures arise frequently in structural matroid theory, this paper introduces a general technique for analyzing those special properties of partitioned matroids that depend solely on the values of the connectivities [Formula: see text], the local connectivities [Formula: see text], and the dual local connectivities [Formula: see text]. In particular, we consider those partitioned matroids in which each [Formula: see text] is an independent, coindependent set of clones of cardinality [Formula: see text]. Calling such partitioned matroids clonal-core matroids, we show that special results of the above type for partitioned matroids can be verified in general by proving them just for clonal-core matroids. Aiming at the long-term goal of finding the unavoidable minors of 4-connected matroids, we illustrate this technique by studying 4-paths. These are sequences [Formula: see text] of sets that partition the ground set of a matroid so that the union of any proper initial segment of parts is 4-separating. Viewing the ends [Formula: see text] and [Formula: see text] as fixed, we call such a partition a 4-flexipath if [Formula: see text] is a 4-path for all permutations [Formula: see text] of [Formula: see text]. A straightforward simplification enables us to focus on [Formula: see text]-flexipaths for some [Formula: see text] in [Formula: see text], that is, those 4-flexipaths for which [Formula: see text] and [Formula: see text] for all distinct [Formula: see text] and [Formula: see text]. Our main result for 4-paths is that the only nontrivial case that arises here is when [Formula: see text]. In that case, there are essentially only two possible dual pairs of [Formula: see text]-flexipaths when [Formula: see text].

We consider matroids with the property that every subset of the ground set of size $t$ is contained in both an $\ell$-element circuit and an $\ell$-element cocircuit; we say that such a matroid has the $(t,\ell)$-property. We show that for any positive integer $t$, there is a finite number of matroids with the $(t,\ell)$-property for $\ell<2t$; however, matroids with the $(t,2t)$-property form an infinite family. We say a matroid is a $t$-spike if there is a partition of the ground set into pairs such that the union of any $t$ pairs is a circuit and a cocircuit. Our main result is that if a sufficiently large matroid has the $(t,2t)$-property, then it is a $t$-spike. Finally, we present some properties of $t$-spikes.

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.

Tutte's wheels-and-whirls theorem is a basic inductive tool for dealing with $3$-connected matroids. This paper proves a generalization of that theorem for the class of $2$-polymatroids. Such structures include matroids, and they model both sets of points and lines in a projective space and sets of edges in a graph. The main result proves that, in a $3$-connected $2$-polymatroid that is not a whirl or the cycle matroid of a wheel, one can obtain another $3$-connected $2$-polymatroid by deleting or contracting some element, or by performing a new operation that generalizes series contraction in a graph. Moreover, we show that unless one uses some reduction operation in addition to deletion and contraction, the set of minimal $2$-polymatroids that are not representable over a fixed field ${\mathbb F}$ is infinite, irrespective of whether ${\mathbb F}$ is finite or infinite.

Let $M$ be a matroid and let $Q$, $R$, $S$, and $T$ be subsets of the ground set such that the smallest separation that separates $Q$ from $R$ has order $k$ and the smallest separation that separates $S$ from $T$ has order $\ell$. We prove that if $E(M)-(Q\cup R\cup S\cup T)$ is sufficiently large, then there is an element $e$ of $M$ such that, in one of $M\backslash e$ or $M/e$, both connectivities are preserved.

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 introduce a new generalization of the maximum matching problem to matroids; this problem includes Gallai’s T‐path problem for graphs.

Let (X 1 ,X 2 ) be an exact k-separation of a matroid N. If M is a matroid that contains N as a minor and the k-separation (X 1 ,X 2 ) does not extend to a k-separation in M, then we say that Mbridges the k-separation (X 1 ,X 2 ) in N. One would hope that a minor minimal bridge for (X 1 ,X 2 ) would not be much larger than N. Unfortunately there are instances in which one can construct arbitrarily large minor-minimal bridges. We restrict our attention to the class of matroids representable over a fixed finite field and show that here minor-minimal bridges are bounded in size.

The parametrized complexity of a number of fundamental problems in the theory of linear codes and integer lattices is explored. Concerning codes, the main results are that MAXIMUM-LIKELIHOOD DECODING and WEIGHT DISTRUBUTION are hard for the parametrized complexity class W[1]. The NP-completeness of these two problems was established by Berlekamp, McEliece, and van Tilborg in 1978 using by means of a reduction from THREE-DIMENSIONAL MATCHING. On the other hand, our proof of hardness for W[1] is based on a parametric polynomial-time transformation from PERFECT CODE in graphs. An immediate consequence of our results is that bounded-distance decoding is likely to be hard for binary linear codes. Concerning lattices, we address the THETA SERIES problem of determining for an integer lattice $\L$ %given by a set of generators, and a positive integer k whether there is a vector $x \in \L$ of Euclidean norm k. We prove here for the first time that THETA SERIES is NP-complete and show that it is also hard for W[1]. Furthermore, we prove that the NEAREST VECTOR problem for integer lattices is hard for W[1]. These problems are the counterparts of WEIGHT DISTRUBUTION and MAXIMUM-LIKELIHOOD DECODING for lattices. Relations between all these problems and combinatorial problems in graphs are discussed.