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 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.     

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.     

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.     

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.     

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.     

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”.     

A desarguesian theorem for algebraic combinatorial geometries

The points of an algebraic combinatorial geometry are equivalence classes of transcendentals over a fieldk; two transcendentals represent the same point when they are algebraically dependent overk. The points of an algebraically closed field of transcendence degree two (three) overk are the lines (resp. planes) of the geometry. We give a necessary and sufficient condition for two coplanar lines to meet in a point (Theorem 1) and prove the converse of Desargues’ theorem for these geometries (Theorem 2). A corollary: the “non-Desargues” matroid is non-algebraic. The proofs depend on five properties (or postulates). The fifth of these is a deep property first proved by Ingleton and Main [3] in their paper showing that the Vámos matroid is non-algebraic.     

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.     

On linear spaces and matroids of arbitrary cardinality

In this paper, we study linear spaces of arbitrary finite dimension on some (possibly infinite) set. We interpret linear spaces as simple matroids and study the problem of erecting some linear space of dimension n to some linear space of dimension n + 1 if possible. Several examples of some such erections are studied; in particular, one of these erections is computed within some infinite iteration process.Dedicated to the memory of Gian-Carlo Rota     

Proof of a conjecture of Kahn for non-binary matroids

This note proves a conjecture of Kahn by showing that ifX is a 3-element independent set in a 3-connected non-binary matroid M, thenM has a connected non-binary minor havingX as a basis. This research was partially supported by an LSU Summer Research Grant.     

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