Subject to announced results by Geelen, Gerards, and Whittle [ Towards a structure theory for matrices and matroids, in Proceedings of the International Congress of Mathematicians, Vol. III, 2006, pp. 827--842], we completely characterize the highly connected members of the classes of dyadic, near-regular, and sixth-root-of-unity matroids.

The classes of even-cycle matroids, even-cycle matroids with a blocking pair, and even-cut matroids each have hundreds of excluded minors. We show that the number of excluded minors for these classes can be drastically reduced if we consider in each class only the highly connected matroids of sufficient size.

A binary frame template is a device for creating binary matroids from graphic or cographic matroids. Such matroids are said to conform or coconform to the template. We introduce a preorder on these templates and determine the nontrivial templates that are minimal with respect to this order. As an application of our main result, we determine the eventual growth rates of certain minor-closed classes of binary matroids, including the class of binary matroids with no minor isomorphic to $PG(3,2)$. Our main result applies to all highly connected matroids in a class, not just those of maximum size. As a second application, we characterize the highly connected 1-flowing matroids.

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.

For a class C of binary linear codes, we write θC: (0, 1) → [0, (1/2)] for the maximum-likelihood decoding threshold function of C, the function whose value at R ∈ (0, 1) is the largest bit-error rate p that the codes in C can tolerate with a negligible probability of maximum-likelihood decoding error across a binary symmetric channel. We show that, if C is the class of cycle codes of graphs, then θC(R) ≤ ((1 - √R)2/2(1 + R)) for each R, and show that equality holds only when R is asymptotically achieved by the cycle codes of regular graphs.

A matroid is GF$(q)$-regular if it is representable over all proper superfields of the field GF$(q)$. We show that, for highly connected matroids having a large projective geometry over GF$(q)$ as a minor, the property of GF$(q)$-regularity is equivalent to representability over both GF$(q^2)$ and GF$(q^t)$ for some odd integer $t \ge 3$. We do this by means of an exact structural description of all such matroids.

Let C = (C1, C2, ...) be a sequence of codes such that each Ciis a linear [ni, ki, di]-code over some fixed finite field F, where niis the length of the code words, kiis the dimension, and diis the minimum distance. We say that C is asymptotically good if, for some ε > 0 and for all i ∈ ℤ>0, we have ni≥ i and min(ki/ni, di/ni) ≥ ε. Sequences of asymptotically good codes exist. We prove that if C is a class of GF(pn)-linear codes (where p is prime and n ≥ 1), closed under puncturing and shortening, and if C contains an asymptotically good sequence, then C must contain all GF(p)-linear codes. Our proof relies on a powerful new result from matroid structure theory.

Let $M$ be a representable matroid and $Q, R, S, T$ 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 $l$. We prove that if $M$ is sufficiently large, then there is an element $e$ such that in one of $M\backslash e$ and $M\!/e$ both connectivities are preserved. For matroids representable over a finite field we prove a stronger result: we show that we can remove $e$ such that both a connectivity and a minor of $M$ are preserved. (A corrected version is attached.)

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 consider a game-theoretical variant of the Steiner forest problem in which each player j, out of a set of k players, strives to connect his terminal pair $(s_j, t_j)$ of vertices in an undirected, edge-weighted graph G. In this paper we show that a natural adaptation of the primal-dual Steiner forest algorithm of Agrawal, Klein, and Ravi [SIAM J. Comput., 24 (1995), pp. 445–456] yields a 2-budget balanced and cross-monotonic cost sharing method for this game. We also present a negative result, arguing that no cross-monotonic cost sharing method can achieve a budget balance factor of less than 2 for the Steiner tree game. This shows that our result is tight. Our algorithm gives rise to a new linear programming relaxation for the Steiner forest problem which we term the lifted-cut relaxation. We show that this new relaxation is stronger than the standard undirected cut relaxation for the Steiner forest problem.