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.     

Capturing two elements in unavoidable minors of 3-connected binary matroids

Let M be a 3-connected binary matroid and let n   be an integer exceeding 2. Ding, Oporowski, Oxley, and Vertigan proved that there is an integer f(n)$f(n)$ so that if |E(M)|>f(n)$|E(M)|>f(n)$, then M has a minor isomorphic to one of the rank-n wheel, the rank-n   tipless binary spike, or the cycle or bond matroid of _K3,n$K_{3,n}$. This result was recently extended by Chun, Oxley, and Whittle to show that there is an integer g(n)$g(n)$ so that if |E(M)|>g(n)$|E(M)|>g(n)$ and x∈E(M)$x\in E(M)$, then x is an element of a minor of M isomorphic to one of the rank-n wheel, the rank-n   binary spike with a tip and a cotip, or the cycle or bond matroid of _K1,1,1,n$K_{1,1,1,n}$. In this paper, we prove that, for each i   in {2,3}$\{2,3\}$, there is an integer _hi(n)$h_i(n)$ so that if |E(M)|>_hi(n)$|E(M)|>h_i(n)$ and Z is an i-element rank-2 subset of M, then M has a minor from the last list whose ground set contains Z.     

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

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.     

On fixing elements in matroid minors

LetF be a collection of 3-connected matroids which is (3, 1)-rounded, that is, whenever a 3-connected matroidM has a minor in F ande is an element ofM, thenM has a minor in F whose ground set contains.e. The aim of this note is to prove that, for all sufficiently largen, the collection ofn-element 3-connected matroids having some minor inF is also (3, 1)-rounded.This research was partially supported by the National Science Foundation under Grant No. DMS-8500494.     

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.     

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.     

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

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