Splitting Operation and Connectedness in Binary Matroids

In [3], the authors have extended the splitting operation of graphs to binary matroids. In this paper we explore the relationship between the splitting operation and connectedness in binary matroids. We prove that repeated applications of splitting operation on a bridgeless disconnected binary matroid leads to a connected binary matroid. We extend splitting lemma of graphs [1] to binary matroids.     

Regular matroids with every circuit basis fundamental

Hartvigsen and Zemel have obtained a characterization of those graphs which have every circuit basis fundamental. We consider the corresponding problem for binary matroids. We show that, in general, the class of binary matroids for which every circuit basis is fundamental is not closed under the taking of minors. However, this class is closed under the taking of series-minors. We also describe some general properties of this class of matroids. We end by extending Hartvigsen and Zemel's result to the class of regular matroids, thus obtaining a set of excluded minors which are graphic for this class. © 1996 John Wiley & Sons, Inc.     

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.     

Tutte-martin polynomials and orienting vectors of isotropic systems

Isotropic systems are structures which unify some properties of 4-regular graphs and of pairs of dual binary matroids. In this paper we unify the properties of the symmetric Tutte polynomials (i.e. with equal variables) of binary matroids and of the Martin polynomials of 4-regular graphs. For this purpose we introduce the orienting vectors of an isotropic system in order to generalize the eulerian orientations of 4-regular graphs.     

Circuit and cocircuit partitions of binary matroids

We give an example of a class of binary matroids with a cocircuit partition and we give some characteristics of a set of cocircuits of such binary matroids which forms a partition of the ground set.     

Binary signed-graphic matroids: Representations and recognition algorithms

Recognition algorithms determining whether a given matroid is binary signed-graphic or not are presented in this work. Depending on whether the input is a cographic, a binary or a general matroid different algorithms are provided utilizing mainly decomposition results for the class of signed-graphic matroids. Finally, in order to devise such algorithms, necessary results regarding the representability of signed-graphic matroids in various fields are also given.     

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.     

Unions of oriented matroids

The union operation for pairs of (ordinary) matroids is a simple construction which can be used to derive examples of more complicated matroids from less complicated ones. In this paper, the analogue for oriented matroids of this operation is described, and is used to construct more complicated oriented matroids and polytopes from less complicated ones. In particular, an easy construction is given for the polyhedral set found by Klee and Walkup to be a counterexample to the Hirsch conjecture.     

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.     

Decompositions of signed-graphic matroids

We give a decomposition theorem for signed graphs whose frame matroids are binary and a decomposition theorem for signed graphs whose frame matroids are quaternary.     

ContributionsOn binary k-paving matroids and Reed-Muller codes

A matroid M of rank r k is k-paving if all of its circuits have cardinality exceeding r − k. In this paper, we develop some basic results concerning k-paving matroids and their connections with codes. Also, we determine all binary 2-paving 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.     

The 3-connected binary matroids with circumference 6 or 7

In this paper, we construct all 3-connected binary matroids with circumference equal to 6 or 7 having large rank.     

Kuratowski's and Wagner's theorems for matroids

In an earlier paper we proved the following theorem, which provides a strengthening of Tutte's well-known characterization of regular (totally unimodular) matroids: A binary matroid is regular if it does not have the Fano matroid or its dual as a series-minor (parallel-minor). In this paper we prove two theorems (Theorems 5.1 and 6.1) which provide the same kind of strengthening for Tutte's characterization of the graphic matroids (i.e., bond-matroids). One interesting aspect of these theorems is the introduction of the matroids of “type R”. It turns out that these matroids are, in at least two different senses, the smallest regular matroids which are neither graphic nor cographic (Theorems 6.2 and 6.3).     

ℓ-matrices and a characterization of binary matroids

?-matrices are defined and shown to be the incidence matrices of certain matroids (lines). The well-known characterizations of binary matroids of W.T. Tutte and A. Lehman are proved along with a new characterization. The proofs use ?-matrices.     

Minimally 3-connected isotropic systems

Isotropic systems are structures which unify some properties of 4-regular graphs and selfdual properties of binary matroids, such as connectivity and minors. In this paper, we find the minimally 3-connected isotropic systems. This result implies the binary part Tutte's wheels and whirls theorem.     

Bounding the beta invariant of 3-connected matroids

The beta invariant is related to the Chromatic and Tutte Polynomials and has been studied by Crapo [4], Brylawski [2], Oxley [7] and others. Crapo [4] showed that a matroid with at least two elements is connected if and only if its beta invariant is greater than zero. Brylawski [2] showed that a connected matroid has beta invariant one if and only if M is isomorphic to a serial-parallel network. Oxley [7] characterized all matroids with beta invariant two, three and four. In this paper, we first give a best possible lower bound on the beta invariant of 3-connected matroids, then we characterize all 3-connected matroids attaining the lower bound. We also characterize all binary matroids with beta invariant 5, 6, and 7.     

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.     

A matroid operation that commutes with duality

In this note, we propose an operation for matroids that commutes with duality having deletions and contractions as extremal cases. Crapo and Schmitt's free product of matroids is one of its consequences. A special case of this operation can be used as an inductive tool because it reduces the number of elements of a matroid by two and it is invariant by duality.