What is a complex matroid?

Following an “ansatz” of Björner and Ziegler [BZ], we give an axiomatic development of finite sign vector systems that we callcomplex matroids. This includes, as special cases, the sign vector systems that encode complex arrangements according to [BZ], and the complexified oriented matroids, whose complements were considered by Gel'fand and Rybnikov [GeR]. Our framework makes it possible to study complex hyperplane arrangements as entirely combinatorial objects. By comparing complex matroids with 2-matroids, which model the more general 2-arrangements introduced by Goresky and MacPherson [GoM], the essential combinatorial meaning of a “complex structure” can be isolated. Our development features a topological representation theorem for 2-matroids and complex matroids, and the computation of the cohomology of the complement of a 2-arrangement, including its multiplicative structure in the complex case. Duality is established in the cases of complexified oriented matroids, and for realizable complex matroids. Complexified oriented matroids are shown to be matroids with coefficients in the sense of Dress and Wenzel [D1], [DW1], but this fails in general.     

Combinatorial obstructions to the lifting of weaving diagrams

This paper deals with various connections of oriented matroids [3] and weaving diagrams of lines in space [9], [16], [27]. We encode the litability problem of a particular weaving diagramD onn lines by the realizability problem of a partial oriented matroid χ _D with2n elements in rank 4. We prove that the occurrence of a certain substructure inD implies that χD is noneuclidean in the sense of Edmonds, Fukuda, and Mandel [12], [14]. Using this criterion we construct an infinite class of minor-minimal noneuclidean oriented matroids in rank 4. Finally, we give an easy algebraic proof for the nonliftability of the alternating weaving diagram on a bipartite grid of 4×4 lines [16].     

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.     

The switching game on unions of oriented matroids

In 1986, Hamidoune and Las Vergnas [3] introduced an oriented matroid version of the so-called Shannon’s switching game. They conjectured that the classification of the directed switching game on oriented matroids is identical to the classification of the non-oriented version. In this note, we support this conjecture by showing its validity for an infinite class of oriented matroids obtained as unions of rank-1 and/or rank-2 uniform oriented matroids.     

Circuit Admissible Triangulations of Oriented Matroids

All triangulations of euclidean oriented matroids are of the same PL-homeo-morphism type by a result of Anderson. That means all triangulations of euclidean acyclic oriented matroids are PL-homeomorphic to PL-balls and that all triangulations of totally cyclic oriented matroids are PL-homeomorphic to PL-spheres. For non-euclidean oriented matroids this question is wide open. One key point in the proof of Anderson is the following fact: for every triangulation of a euclidean oriented matroid the adjacency graph of the set of all simplices ``intersecting' a segment [p _- p ₊ ] is a path. We call this graph the [p _- p ₊ ] -adjacency graph of the triangulation. While we cannot solve the problem of the topological type of triangulations of general oriented matroids we show in this note that for every circuit admissible triangulation of an arbitrary oriented matroid the [p _- p ₊ ] -adjacency graph is a path. Received December 8, 2000, and in revised form May 23, 2001. Online publication November 7, 2001.     

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.     

Simplicial cells in arrangements and mutations of oriented matroids

We investigate the combinatorial and topological properties of simplicial cells in arrangements of (pseudo)hyperplanes, using their interpretations in terms of oriented matroids. Simplicial cells have various applications in computational geometry due to the fact that for an arrangement in general position they are in one-to-one correspondence to local changes (mutations) of its combinatorial type. Several characterizations for mutations of oriented matroids, and their relation to geometric realizability questions are being discussed.We give two short proofs for a result of Shannon [30] that every arrangement of n hyperplanes in E ^d has at least n simplicial cells, this bound being sharp for every n and d. The concatenation operation, a construction introduced by Lawrence and Weinberg [21], will be used to generate a large class of representable oriented matroids with this minimal number of mutations.A homotopy theorem is proved, stating that any two arrangements in general position can be transformed into each other be a sequence of representability preserving mutations. Finally, we give an example of an oriented matroid on eight elements with only seven mutations. As a corollary we obtain a new proof for the non-polytopality of the smallest non-polytopal matroid sphere M ⁹ ₉₆₃.Supported, in part, by an Alfred P. Sloane Doctoral Dissertation Fellowship.     

Polytopal and nonpolytopal spheres an algorithmic approach

The convexity theory for oriented matroids, first developed by Las Vergnas [17], provides the framework for a new computational approach to the Steinitz problem [13]. We describe an algorithm which, for a given combinatorial (d − 2)-sphereS withn vertices, determines the setC _d,n(S) of rankd oriented matroids withn points and face latticeS. SinceS is polytopal if and only if there is a realizableM εC _d,n(S), this method together with the coordinatizability test for oriented matroids in [10] yields a decision procedure for the polytopality of a large class of spheres. As main new result we prove that there exist 431 combinatorial types of neighborly 5-polytopes with 10 vertices by establishing coordinates for 98 “doubted polytopes” in the classification of Altshuler [1]. We show that for alln ≧k + 5 ≧8 there exist simplicialk-spheres withn vertices which are non-polytopal due to the simple fact that they fail to be matroid spheres. On the other hand, we show that the 3-sphereM ₉₆₃ ⁹ with 9 vertices in [2] is the smallest non-polytopal matroid sphere, and non-polytopal matroidk-spheres withn vertices exist for alln ≧k + 6 ≧ 9.     

Nonrealizability proofs in computational geometry

This paper deals with a class of computational problems in real algebraic geometry. We introduce the concept of final polynomials as a systematic approach to prove nonrealizability for oriented matroids and combinatorial geometries.Hilbert's Nullstellensatz and its real analogue imply that an abstract geometric object is either realizable or it admits a final polynomial. This duality has first been applied by Bokowski in the study of convex polytopes [7] and [11], but in these papers the resulting final polynomials were given without their derivations.It is the objective of the present paper to fill that gap and to describe an algorithm for constructing final polynomials for a large class of nonrealizable chirotopes. We resolve a problem posed in [10] by proving that not every realizable simplicial chirotope admits a solvability sequence. This result shows that there is no easy combinatorial method for proving nonrealizability and thus justifies our final polynomial approach.     

Su un modello di geometria non euclidea

In this paper, by using the method of [4], a new model of non-euclidean geometry that is non-comparable with the Loba?evskij geometry is given.     

Matroids with few non-common bases

In [On Mills's conjecture on matroids with many common bases, Discrete Math. 240 (2001) 271-276], Lemos proved a conjecture of Mills [On matroids with many common bases, Discrete Math. 203 (1999) 195-205]: for two (k+1)-connected matroids whose symmetric difference between their collections of bases has size at most k, there is a matroid that is obtained from one of these matroids by relaxing n₁ circuit-hyperplanes and from the other by relaxing n₂ circuit-hyperplanes, where n₁ and n₂ are non-negative integers such that n₁+n₂≤k. In [Matroids with many common bases, Discrete Math. 270 (2003) 193-205], Lemos proved a similar result, where the hypothesis of the matroids being k-connected is replaced by the weaker hypothesis of being vertically k-connected. In this paper, we extend these results.     

Two constructions of oriented matroids with disconnected extension space

The extension space ℰ(ℳ) of an oriented matroid ℳ is the poset of all one-element extensions of ℳ, considered as a simplicial complex. We present two different constructions leading to rank 4 oriented matroids with disconnected extension space. We prove especially that if an elementf is not contained in any mutation of a rank 4 oriented matroid ℳ, then ℰ(ℳ\f) contains an isolated point. A uniform nonrealizable arrangement of pseudoplanes with this property is presented. The examples described contrast results of Sturmfels and Ziegler [12] who proved that for rank 3 oriented matroids the extension space has the homotopy type of the 2-sphere.     

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.     

A note on the fundamental group of the Salvetti complex determined by an oriented matroid

LetM_C(A) be the complexification of the complement of the hyperplanes of an arrangementAinR^d. In [13], Salvetti constructed a regular finite CW complexX M_C(A) homotopic to this space. The definition of this complex is essentially based on the structure of the oriented matroid determined byA, and can be extended similarly to other oriented matroids. In this note, we prove two theorems related to decompositions of the fundamental group of this generalised Salvetti complex.     

A combinatorial abstraction of linear programming

In the context of oriented matroids we establish and elaborate upon an abstraction of linear programming duality foreseen by Rockafellar in his work on elementary vectors. We describe a pivoting operation for oriented matroids and a finite pivoting method, which elucidate the combinatorial nature of Dantzig's simplex method. The pivoting method specializes, when the oriented matroids arise from real vector spaces, to the simplex method with a new pivot selection rule. A very simple pivot selection rule for which finiteness has been established in the linear programming context, but not in the broader setting of oriented matroids, is also described.     

Generation of Oriented Matroids—A Graph Theoretical Approach

We discuss methods for the generation of oriented matroids and of isomorphism classes of oriented matroids. Our methods are based on single element extensions and graph theoretical representations of oriented matroids, and all these methods work in general rank and for non-uniform and uniform oriented matroids as well. We consider two types of graphs, cocircuit graphs and tope graphs, and discuss the single element extensions in terms of localizations which can be viewed as partitions of the vertex sets of the graphs. Whereas localizations of the cocircuit graph are well characterized, there is no graph theoretical characterization known for localizations of the tope graph. In this paper we prove a connectedness property for tope graph localizations and use this for the design of algorithms for the generation of single element extensions by use of tope graphs. Furthermore, we discuss similar algorithms which use the cocircuit graph. The characterization of localizations of cocircuit graphs finally leads to a backtracking algorithm which is a simple and efficient method for the generation of single element extensions. We compare this method with a recent algorithm of Bokowski and Guedes de Oliveira for uniform oriented matroids. Received November 1, 2000, and in revised form May 11, 2001. Online publication November 7, 2001.     

On some algorithmic aspects of hypergraphic matroids

Hypergraphic matroids were studied first by Lorea [23] and later by Frank et al. [11]. They can be seen as generalizations of graphic matroids. Here we show that several algorithms developed for the graphic case can be extended to hypergraphic matroids. We treat the following: the separation problem for the associated polytope, testing independence, separation of partition inequalities, computing the rank of a set, computing the strength, computing the arboricity and network reinforcement.     

Topological representations of matroid maps

The Topological Representation Theorem for (oriented) matroids states that every (oriented) matroid arises from the intersection lattice of an arrangement of codimension one homotopy spheres on a homotopy sphere. In this paper, we use a construction of Engström to show that structure-preserving maps between matroids induce topological mappings between their representations; a result previously known only in the oriented case. Specifically, we show that weak maps induce continuous maps and that this process is a functor from the category of matroids with weak maps to the homotopy category of topological spaces. We also give a new and conceptual proof of a result regarding the Whitney numbers of the first kind of a matroid.     

Oriented matroids

In this paper, the basic properties of oriented matroids are examined. A topological representation theorem for oriented matroids is proven, utilizing the notion of an “arrangement of pseudo-hemispheres”. The duality theorem of linear programming is extended to oriented matroids.