On minors of non-binary matroids

No binary matroid has a minor isomorphic toU ₄ ² , the “four-point line”, and Tutte showed that, conversely, every non-binary matroid has aU ₄ ² minor. However, more can be said about the element sets ofU ₄ ² minors and their distribution. Bixby characterized those elements which are inU ₄ ² minors; a matroidM has aU ₄ ² minor using elementx if and only if the connected component ofM containingx is non-binary. We give a similar (but more complicated) characterization for pairs of elements. In particular, we prove that for every two elements of a 3-connected non-binary matroid, there is aU ₄ ² minor using them both.     

Decomposition of binary matroids

We prove results relating to the decomposition of a binary matroid, including its uniqueness when the matroid is cosimple. We extend the idea of “freedom” of an element in a matroid to “freedom” of a set, and show that there is a unique maximal integer polymatroid inducing a given binary matroid.     

Adjoints of oriented matroids

An adjoint of a geometric latticeG is a geometric lattice of the same rank into which there is an embeddinge mapping the copoints ofG onto the points of . In this paper we introduce oriented adjoints and prove that they can be embedded into the extension lattice of oriented matroids. Supported by Sonderforschungbereich 21 (DFG)     

Non-separating cocircuits in matroids

In this note, we obtain a lower bound for the number of connected hyperplanes of a 3-connected binary matroid M containing a fixed set A provided M|A is coloopless.     

Equivalent factor matroids of graphs

The factor matroid of a graphG is the matric matroid of the vertex-edge incidence matrix ofG interpreted over the real numbers. This paper presents a constructive characterization of the graphs hat have the same factor matroid as a given 4-connected bipartite graph.Research partially supported by NSF Grant ESS-8307796 and Office of Naval Research Grant N00014-86-K-0689.     

Inseparability graphs of oriented matroids

We determine the inseparability graphs of uniform oriented matroids and of graphic oriented matroids. For anyr, n such that 4rn–3, examples of rankr uniform oriented matroids onn elements with a given inseparability graph are obtained by simple constructions of polytopes having prescribed separation properties.     

On triangle-free 3-connected matroids

We present a method to construct any triangle-free 3-connected matroid starting from a matroid belonging to one of four infinite families and subsequently performing a sequence of small operations on it. This result extends to matroids a theorem proved by Kriesell for graphs.     

Connected hyperplanes in binary matroids

For a 3-connected binary matroid M, let dim_A(M) be the dimension of the subspace of the cocycle space spanned by the non-separating cocircuits of M avoiding A, where A⊆E(M). When A=∅, Bixby and Cunningham, in 1979, showed that dim_A(M)=r(M). In 2004, when |A|=1, Lemos proved that dim_A(M)=r(M)-1. In this paper, we characterize the 3-connected binary matroids having a pair of elements that meets every non-separating cocircuit. Using this result, we show that 2dim_A(M)?r(M)-3, when M is regular and |A|=2. For |A|=3, we exhibit a family of cographic matroids with a 3-element set intersecting every non-separating cocircuit. We also construct the matroids that attains McNulty and Wu’s bound for the number of non-separating cocircuits of a simple and cosimple connected binary matroid.     

Towards a splitter theorem for internally 4-connected binary matroids III

This paper proves a preliminary step towards a splitter theorem for internally 4-connected binary matroids. In particular, we show that, provided M   or M^?$M^{?}$ is not a cubic Möbius or planar ladder or a certain coextension thereof, an internally 4-connected binary matroid M with an internally 4-connected proper minor N   either has a proper internally 4-connected minor M^′$M^{\prime }$ with an N  -minor such that |E(M)−E(M^′)|?3$|E(M)-E(M^{\prime })|?3$ or has, up to duality, a triangle T and an element e of T   such that M\e$M\backslash e$ has an N-minor and has the property that one side of every 3-separation is a fan with at most four elements.     

On properties of almost all matroids

We give several results about the asymptotic behaviour of matroids. Specifically, almost all matroids are simple and cosimple and, indeed, are 3-connected. This verifies a strengthening of a conjecture of Mayhew, Newman, Welsh, and Whittle. We prove several quantitative results including giving bounds on the rank, a bound on the number of bases, the number of circuits, and the maximum circuit size of almost all matroids.     

Basis-exchange properties of sparse paving matroids

It has been conjectured that, asymptotically, almost all matroids are sparse paving matroids. We provide evidence for five long-standing, basis-exchange conjectures by proving them for this large class of matroids.     

On some combinatorial properties of algebraic matroids

It was proved implicitly by Ingleton and Main and explicitly by Lindström that if three lines in the algebraic matroid consisting of all elements of an algebraically closed field are not coplanar, but any two of them are, then they pass through one point. This theorem is extended to a more general result about the intersection of subspaces in full algebraic matroids. This result is used to show that the minimax theorem for matroid matching, proved for linear matroids by Lovász, remains valid for algebraic matroids.     

Inequivalent representations of matroids over prime fields

It is proved that for each prime field GF(p)$\mathit{GF}(p)$, there is an integer _np$n_p$ such that a 4-connected matroid has at most _np$n_p$ inequivalent representations over GF(p)$\mathit{GF}(p)$. We also prove a stronger theorem that obtains the same conclusion for matroids satisfying a connectivity condition, intermediate between 3-connectivity and 4-connectivity that we term “k-coherence”.     

Counterexamples to conjectures on 4-connected matroids

Tutte characterized binary matroids to be those matroids without aU ₄ ² minor. Bixby strengthened Tutte’s result, proving that each element of a 2-connected non-binary matroid is in someU ₄ ² minor. Seymour proved that each pair of elements in a 3-connected non-binary matroid is in someU ₄ ² minor and conjectured that each triple of elements in a 4-connected non-binary matroid is in someU ₄ ² minor. A related conjecture of Robertson is that each triple of elements in a 4-connected non-graphic matroid is in some circuit. This paper provides counterexamples to these two conjectures.     

Skew partial fields,multilinear representations of matroids,and a matrix tree theorem

We extend the notion of representation of a matroid to algebraic structures that we call skew partial fields. Our definition of such representations extends Tutte?s definition, using chain groups. We show how such representations behave under duality and minors, we extend Tutte?s representability criterion to this new class, and we study the generator matrices of the chain groups. An example shows that the class of matroids representable over a skew partial field properly contains the class of matroids representable over a skew field. Next, we show that every multilinear representation of a matroid can be seen as a representation over a skew partial field. Finally we study a class of matroids called quaternionic unimodular. We prove a generalization of the matrix tree theorem for this class.     

On the intersections of circuits and cocircuits in matroids

Seymour has shown that a matroid has a triad, that is, a 3-element set which is the intersection of a circuit and a cocircuit, if and only if it is non-binary. In this paper we determine precisely when a matroidM has a quad, a 4-element set which is the intersection of a circuit and a cocircuit. We also show that this will occur ifM has a circuit and a cocircuit meeting in more than four elements. In addition, we prove that if a 3-connected matroid has a quad, then every pair of elements is in a quad. The corresponding result for triads was proved by Seymour.     

A problem of P. Seymour on nonbinary matroids

The following statement fork=1, 2, 3 has been proved by Tutte [4], Bixby [1] and Seymour [3] respectively: IfM is ak-connected non-binary matroid andX a set ofk-1 elements ofM, thenX is contained in someU ₄ ² minor ofM. Seymour [3] asks whether this statement remains true fork=4; the purpose of this note is to show that it does not and to suggest some possible alternatives. Supported in part by the National Science Foundation