Oriented matroids with few mutations

This paper defines a “connected sum” operation on oriented matroids of the same rank. This construction is used for three different applications in rank 4. First it provides nonrealizable pseudoplane arrangements with a low number of simplicial regions. This contrasts the case of realizable hyperplane arrangements: by a classical theorem of Shannon every arrangement ofn projective planes in ℝP ^d-1 contains at leastn simplicial regions and every plane is adjacent to at leastd simplicial regions [17], [18]. We construct a class of uniform pseudoarrangements of 4n pseudoplanes in ℝP³ with only 3n+1 simplicial regions. Furthermore, we construct an arrangement of 20 pseudoplanes where one plane is not adjacent to any simplicial region. Finally we disprove the “strong-map conjecture” of Las Vergnas [1]. We describe an arrangement of 12 pseudoplanes containing two points that cannot be simultaneously contained in an extending hyperplane.     

Oriented matroids from smooth manifolds

Results of Folkman and Lawrence and Mandel on representations of oriented matroids by topological spheres are used to prove a method of constructing oriented matroids from intersections of smooth topological hyperplanes. A class of such constructions is given corresponding to non real-representable matroids of rank ϱ on 2ϱ + 1 elements, ϱ ≥ 4.     

Oriented matroids and multiply ordered sets

The many different axiomatizations for matroids all have their uses. In this paper we show that Gutierrez Novoa's n-ordered sets are cryptomorphically the same as the oriented matroids, thereby establishing the existence of an axiomatization for oriented matroids in which the “oriented” bases of the matroid are the objects of paramount importance.     

Oriented matroids and complete-graph embeddings on surfaces

We provide a link between topological graph theory and pseudoline arrangements from the theory of oriented matroids. We investigate and generalize a function f that assigns to each simple pseudoline arrangement with an even number of elements a pair of complete-graph embeddings on a surface. Each element of the pair keeps the information of the oriented matroid we started with. We call a simple pseudoline arrangement triangular, when the cells in the cell decomposition of the projective plane are 2-colorable and when one color class of cells consists of triangles only. Precisely for triangular pseudoline arrangements, one element of the image pair of f is a triangular complete-graph embedding on a surface. We obtain all triangular complete-graph embeddings on surfaces this way, when we extend the definition of triangular complete pseudoline arrangements in a natural way to that of triangular curve arrangements on surfaces in which each pair of curves has a point in common where they cross. Thus Ringel's results on the triangular complete-graph embeddings can be interpreted as results on curve arrangements on surfaces. Furthermore, we establish the relationship between 2-colorable curve arrangements and Petrie dual maps. A data structure, called intersection pattern is provided for the study of curve arrangements on surfaces. Finally we show that an orientable surface of genus g admits a complete curve arrangement with at most 2g+1 curves in contrast to the non-orientable surface where the number of curves is not bounded.     

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.     

Unipancyclic matroids

Analogous to the concept of uniquely pancyclic graphs, we define a uniquely pancyclic (UPC) matroid of rank $r$ to be a (simple) rank-$r$ matroid containing exactly one circuit of each length $?$ for $3\le ?\le r+1$. Our discussion addresses the existence of graphic, binary, and transversal representations of UPC matroids. Using Shi’s results, which catalogued exactly seven non-isomorphic UPC graphs, we produce a nongraphic binary UPC matroid of rank 24. We consider properties of binary UPC matroids in general, and prove that all binary UPC matroids have a connectivity of $2$.     

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     

Properties of matroids characterizable in terms of excluded matroids

Some properties π of matroids are characterizable in terms of a set S(π) of exluded matroids, that is, a matroid M satisfies property π if and only if M has no minor (series-minor, parallel-minor) isomorphic to a matroid in S(π). This note presents a necessary and sufficient condition for a property to be characterizable in terms of excluded 3-connected matroids.     

Higher support matroids

The purpose of this paper is to provide links between matroid theory and the theory of subcode weights and supports in linear codes. We describe such weights and supports in terms of certain matroids arising from the vector matroids associated to the linear codes. Our results generalize classical results by Whitney, Tutte, Crapo and Rota, Greene, and other authors. As an application of our results, we obtain a new and elegant dual correspondence between the bond union and cycle union cardinalities of a graph.     

Orientable arithmetic matroids

The theory of matroids has been generalized to oriented matroids and, recently, to arithmetic matroids. We want to give a definition of “oriented arithmetic matroid” and prove some properties like the “uniqueness of orientation”.     

Non-regular simplicial matroids

Let (ks) denote the set of all k-element-subsets of a finite set S. A k-simplical matroid on a subset E of (ks) is a binary matroid the circuit of which are simplicial complexes {X1,…Xm} ? E with boundary 0 (mod 2). The k-simplical matroid on (ks) is called the full simplicial matroid Gk(S). The polygon matroid on the edges of a finite graph is 2-simplicial. Polygon-matroids and their duals are regular. The dual of Gk(S) is Gn?k(S) if the cardinnlity of S is n. More details on simplicial matroids can be found in [3, Chapter 6] and also in [4, pp. 180–181].Welsh asked if every simplicial matroid is regular. We prove that this is not the case, for all full k-simplicial matroids Gk(S) with 3?k?n?3 are non-regular (n is the cardinality of S). This result has also been proved σy R. Cordovil and M. Las Vergnas recently. Their proof is different from our proof, which is somewhat shorter.     

Recognizing graphic matroids

There is no polynomially bounded algorithm to test if a matroid (presented by an “independence oracle”) is binary. However, there is one to test graphicness. Finding this extends work of previous authors, who have given algorithms to test binary matroids for graphicness. Our main tool is a new result that ifM′ is the polygon matroid of a graphG, andM is a different matroid onE(G) with the same rank, then there is a vertex ofG whose star is not a cocircuit ofM.     

On minor-minimally-connected matroids

By a well-known result of Tutte, if e is an element of a connected matroid M, then either the deletion or the contraction of e from M is connected. If, for every element of M, exactly one of these minors is connected, then we call M minor-minimally-connected. This paper characterizes such matroids and shows that they must contain a number of two-element circuits or cocircuits. In addition, a new bound is proved on the number of 2-cocircuits in a minimally connected matroid.     

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.     

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.     

Bases in oriented matroids

Let M be an oriented matroid. One can define exactly two assignments of +1 and ?1 to permutations of bases of M canonically associated with the orientation of M.     

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.