Coxeter matroid polytopes

If Δ is a polytope in real affine space, each edge of Δ determines a reflection in the perpendicular bisector of the edge. The exchange groupW (Δ) is the group generated by these reflections, and Δ is a (Coxeter) matroid polytope if this group is finite. This simple concept of matroid polytope turns out to be an equivalent way to define Coxeter matroids. The Gelfand-Serganova Theorem and the structure of the exchange group both give us information about the matroid polytope. We then specialize this information to the case of ordinary matroids; the matroid polytope by our definition in this case turns out to be a facet of the classical matroid polytope familiar to matroid theorists. This work was supported in part by NSA grant MDA904-95-1-1056.     

On the intersection of infinite matroids

We show that the infinite matroid intersection conjecture of Nash-Williams implies the infinite Menger theorem proved by Aharoni and Berger in 2009.We prove that this conjecture is true whenever one matroid is nearly finitary and the second is the dual of a nearly finitary matroid, where the nearly finitary matroids form a superclass of the finitary matroids.In particular, this proves the infinite matroid intersection conjecture for finite-cycle matroids of 2-connected, locally finite graphs with only a finite number of vertex-disjoint rays.     

A characterization of orthogonal duality in matroid theory

An operation on matroids is a function defined from the collection of all matroids on finite sets to itself which preserves isomorphism of matroids and sends a matroid on a set S to a matroid on the same set S. We show that orthogonal duality is the only non-trivial operation on matroids which interchanges contraction and deletion.     

Quasi‐graphic matroids*

Frame matroids and lifted‐graphic matroids are two interesting generalizations of graphic matroids. Here, we introduce a new generalization, quasi‐graphic matroids, that unifies these two existing classes. Unlike frame matroids and lifted‐graphic matroids, it is easy to certify that a 3‐connected matroid is quasi‐graphic. The main result is that every 3‐connected representable quasi‐graphic matroid is either a lifted‐graphic matroid or a frame matroid.     

Characterizing binary simplical matroids

In an earlier paper we defined a class of matroids whose circuit are combinatorial generalizations of simple polytopes; these matroids are the binary analogue of the simplical geometrics of Crapo and Rota. Here we find necessary and sufficient conditions for a matroid to be isomorphic to such a binary simplical matroid.     

A decomposition theory for matroids. I. General results

A new matroid decomposition with several attractive properties leads to a new theorem of alternatives for matroids. A strengthened version of this theorem for binary matroids says roughly that to any binary matroid at least one of the following statements must apply: (1) the matroid is decomposable, (2) several elements can be removed (in any order) without destroying 3-connectivity, (3) the matroid belongs to one of 2 well-specified classes or has 10 elements or less. The latter theorem is easily specialized to graphic matroids. These theorems seem particularly useful for the determination of minimal violation matroids, a subject discussed in part II.     

闭模糊拟阵模糊基的判定

通过讨论闭模糊拟阵的导出拟阵序列和模糊基的结构,找到了判定闭模糊拟阵的模糊基的一个充要条件。根据此充要条件,给出了从导出拟阵序列得到闭模糊拟阵的模糊基的一种算法。     

Infinite matroids in graphs

It has recently been shown that infinite matroids can be axiomatized in a way that is very similar to finite matroids and permits duality. This was previously thought impossible, since finitary infinite matroids must have non-finitary duals.In this paper we illustrate the new theory by exhibiting its implications for the cycle and bond matroids of infinite graphs. We also describe their algebraic cycle matroids, those whose circuits are the finite cycles and double rays, and determine their duals. Finally, we give a sufficient condition for a matroid to be representable in a sense adapted to infinite matroids. Which graphic matroids are representable in this sense remains an open question.     

Linked tree-decompositions of represented infinite matroids

We prove that a represented infinite matroid having finite tree-width w has a linked tree-decomposition of width at most 2w. This result should be a key lemma in showing that any class of infinite matroids representable over a fixed finite field and having bounded tree-width is well-quasi-ordered under taking minors. We also show that for every finite w, a represented infinite matroid has tree-width at most w if and only if all its finite submatroids have tree-width at most w. Both proofs rely on the use of a notion of chordality for represented matroids.     

A decomposition theory for matroids. II. Minimal violation matroids

Two decomposition theorems of Part I are utilized to characterize minimal violation matroids of matroid properties that possess certain composition and extension properties. Graphicness, planarity, and regularity have all or almost all of the desired composition and extension properties, and rather simple arguments produce the well-known minimal violation matroids.     

On critical exponents of Dowling matroids

The critical problem in matroid theory is the problem to determine the critical exponent of a given representable matroid over a finite field. In this paper, we study the critical exponents of a class of representable matroids over finite fields, called Dowling matroids. Then the critical problem for a Dowling matroid is corresponding to the classical problem in coding theory to determine the maximum dimension k such that there exists an \([n,k,d]_q\) code for given n, d and q. We give a necessary and sufficient condition on the critical exponents of Dowling matroids by using a coding theoretical approach.     

Oriented matroids, complex manifolds, and a combinatorial model for BU

We introduce a new notion of complex oriented matroid and develop some basic properties of this object. Our definition of complex oriented matroids bears the same relationship to classical oriented matroids that the stratification of the complex plane into nine components corresponding to the signs of the complex and real parts has with the three-component sign stratification of the real line. We then use these complex oriented matroids to set up the foundations of a combinatorial version of complex geometry analogous to MacPherson's combinatorial differential manifolds; in this world, the representing object for the functor of (combinatorial) complex vector bundles is the nerve of a poset of complex oriented matroids. We conclude by showing that this space is homotopy equivalent to the complex Grassmannian, thus deducing that our combinatorial world is able to completely capture the notion of complex vector bundles.     

Cubes and orientability

We define and study a new class of matroids: cubic matroids. Cubic matroids include, as a particular case, all affine cubes over an arbitrary field. There is only one known orientable cubic matroid: the real affine cube. The main results establish as an invariant of orientable cubic matroids the structure of the subset of acyclic orientations with LV-face lattice isomorphic to the face lattice of the real cube or, equivalently, with the same signed circuits of length 4 as the real cube.     

Separating cocircuits in binary matroids

A cocircuit of a matroid is separating if deleting it leaves a separable matroid. We give an effecient algorithm which finds a separating cocircuit or a Fano minor in a binary matroid, thus proving constructively a theorem of Tutte. Using this algorithm and a new recursive characterization of bond matroids, we give a new method for testing binary matroids for graphicness. We also give an efficient algorithm for finding a special kind of separating cocircuit: one whose deletion leaves a matroid having a coloop.     

A short proof that every finite graph has a tree-decomposition displaying its tangles

We give a short proof that every finite graph (or matroid) has a tree-decomposition that displays all maximal tangles.This theorem for graphs is a central result of the graph minors project of Robertson and Seymour and the extension to matroids is due to Geelen, Gerards and Whittle.     

On the (co)girth of a connected matroid

This article studies the girth and cogirth problems for a connected matroid. The problem of finding the cogirth of a graphic matroid has been intensively studied, but studies on the equivalent problem for a vector matroid or a general matroid have been rarely reported. Based on the duality and connectivity of a matroid, we prove properties associated with the girth and cogirth of a matroid whose contraction or restriction is disconnected. Then, we devise algorithms that find the cogirth of a matroid M from the matroids associated with the direct sum components of the restriction of M. As a result, the problem of finding the (co)girth of a matroid can be decomposed into a set of smaller sub-problems, which helps alleviate the computation. Finally, we implement and demonstrate the application of our algorithms to vector matroids.     

Orientability of matroids

In this paper we define oriented matroids and develop their fundamental properties, which lead to generalizations of known results concerning directed graphs, convex polytopes, and linear programming. Duals and minors of oriented matroids are defined. It is shown that every coordinatization (representation) of a matroid over an ordered field induces an orientation of the matroid. Examples of matroids that are orientable but not coordinatizable and of matroids that are not orientable are presented. We show that a binary matroid is orientable if and only if it is unimodular (regular), and that every unimodular matroid has an orientation that is induced by a coordinatization and is unique in a certain straightforward sense.     

On Maximum-sized k-Regular Matroids

 Let k be an integer exceeding one. The class of k-regular matroids is a generalization of the classes of regular and near-regular matroids. A simple rank-r regular matroid has the maximum number of points if and only if it is isomorphic to M(K _r+1), the cycle matroid of the complete graph on r+1 vertices. A simple rank-r near-regular matroid has the maximum number of points if and only if it is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding a point to a 3-point line of M(K _r+2) and then contracting this point. This paper determines the maximum number of points that a simple rank-r k-regular matroid can have and determines all such matroids having this number. With one exception, there is exactly one such matroid. This matroid is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding k independent points to a flat of M(K _r+k+1) isomorphic to M(K _k+2) and then contracting each of these points. Revised: July 27, 1998     

Techniques in matroid reconstruction

Brylawski first raised the questions of whether a matroid can be reconstructed from its multisets of hyperplanes, single-element deletions, or minors. This paper explores the relationships between these questions, and resolves them for certain classes of matroids. In particular, finite Dowling lattices are shown to be reconstructible both by deletions and by contractions.