The circuit basis in binary matroids

The concept of a circuit basis for a matroid is introduced, as an algorithmically rapid way of determining several characteristics of a given matroid. It is used to give a short search for planarity in graphs, and also to begin the answer to a question of G.-C. Rota about “dependency among dependencies.” A circuit basis for a matroid is a least set of circuits which will generate all the circuits of the matroid by repeated use of symmetric differences of cells.     

A chain theorem for internally 4-connected binary matroids

Let M be a matroid. When M is 3-connected, Tutte's Wheels-and-Whirls Theorem proves that M has a 3-connected proper minor N with |E(M)−E(N)|=1 unless M is a wheel or a whirl. This paper establishes a corresponding result for internally 4-connected binary matroids. In particular, we prove that if M is such a matroid, then M has an internally 4-connected proper minor N with |E(M)−E(N)|?3 unless M or its dual is the cycle matroid of a planar or Möbius quartic ladder, or a 16-element variant of such a planar ladder.     

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.     

The universal partition theorem for oriented matroids

We consider realization spaces of a family of oriented matroids of rank three as point configurations in the affine plane. The fundamental problem arises as to which way these realization spaces partition their embedding space. The Universal Partition Theorem roughly states that such a partition can be as complicated as any partition of ℝ ⁿ into elementary semialgebraic sets induced by an arbitrary finite set of polynomials in ℤ[X]. We present the first proof of the Universal Partition Theorem. In particular, it includes the first complete proof of the so-called Universality Theorem. This work was supported by the Deutsche Forschungsgemeinschaft, Graduiertenkolleg “Analyse und Konstruktion in der Mathematik”.     

A maximum-rank minimum-term-rank theorem for matroids

M. Iri has proved that the maximum rank for a pivotal system of matrices (i.e., combivalence class) equals the minimum term rank. Here this and some of Iri's related results are generalized to matroids. These generalizations are presented using a representation of matroids with (0,1)-matrices. Then, with the aid of matroid basis graphs, these generalizations are restated graph-theoretically. Finally, related results about certain uniform basis graphs are derived.     

A unique factorization theorem for matroids

We study the combinatorial, algebraic and geometric properties of the free product operation on matroids. After giving cryptomorphic definitions of free product in terms of independent sets, bases, circuits, closure, flats and rank function, we show that free product, which is a noncommutative operation, is associative and respects matroid duality. The free product of matroids M and N is maximal with respect to the weak order among matroids having M as a submatroid, with complementary contraction equal to N. Any minor of the free product of M and N is a free product of a repeated truncation of the corresponding minor of M with a repeated Higgs lift of the corresponding minor of N. We characterize, in terms of their cyclic flats, matroids that are irreducible with respect to free product, and prove that the factorization of a matroid into a free product of irreducibles is unique up to isomorphism. We use these results to determine, for K a field of characteristic zero, the structure of the minor coalgebra of a family of matroids that is closed under formation of minors and free products: namely, is cofree, cogenerated by the set of irreducible matroids belonging to .     

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.     

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.     

Biased graphs whose matroids are special binary matroids

Abiased graph is a graph together with a class of polygons such that no theta subgraph contains exactly two members of the class. To a biased graph are naturally associated three edge matroids:G(), L(), L ₀ (). We determine all biased graphs for which any of these matroids is isomorphic to the Fano plane, the polygon matroid ofK ₄,K ₅ orK _3,3, any of their duals, Bixby's regular matroidR ₁₀, or the polygon matroid ofK _m form > 5. In each case the bias is derived from edge signs. We conclude by finding the biased graphs for whichL ₀ () is not a graphic [or, regular matroid but every proper contraction is.Research supported by National Science Foundation grant DMS-8407102 and SGPNR grant 85Z0701Visiting Research Fellow, 1984–1985     

An exchange theorem for bases of matroids

Theorem. Given two basesB₁andB₂of a matroid ($\text{M}$, r), and a partitionB₁ = X₁ ∪ Y₁, there is a partitionB₂ = X₂ ∪ Y₂such thatX₁ ∪ Y₂andX₂ ∪ Y₁are both bases of$\text{M}$.     

The biased graphs whose matroids are binary

A biased graph Φ consists of a graph and a class of distinguished polygons such that no theta subgraph contains exactly two distinguished polygons. There are three matroids naturally associated with Φ: the bias matroid G(Φ), the lift matroid L(Φ), and the complete lift L₀(Φ). We characterize those Φ for which any of these matroids is binary.     

Note on binary simplicial matroids

Using an earlier characterization of simplicial hypergraphs we obtain a characterization of binary simplicial matroids in terms of the existence of a special base.     

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.     

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.     

闭模糊拟阵模糊圈的算法研究

用闭模糊拟阵的基本序列来研究和描述它的模糊圈,找到了从闭模糊拟阵的模糊相关集或模糊独立集计算模糊圈的方法,并给出了相应的算法.     

On minor-minimally 3-connected binary matroids

A matroid M is called minor-minimally 3-connected if M is 3-connected and, for each e∈E(M), either M?e or M/e is not 3-connected. In this paper, we prove a chain theorem for the class of minor-minimally 3-connected binary matroids. As a consequence, we obtain a chain theorem for the class of minor-minimally 3-connected graphs.