Tropical hyperplane arrangements and oriented matroids

We study the combinatorial properties of a tropical hyperplane arrangement. We define tropical oriented matroids, and prove that they share many of the properties of ordinary oriented matroids. We show that a tropical oriented matroid determines a subdivision of a product of two simplices, and conjecture that this correspondence is a bijection.     

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.     

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”.     

Convexity in oriented matroids

We generalize to oriented matroids classical notions of Convexity Theory: faces of convex polytopes, convex hull, etc., and prove some basic properties. We relate the number of acyclic orientations of an orientable matroid to an evaluation of its Tutte polynomial.     

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.     

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 .     

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.     

Adjoints of oriented matroids

An adjoint of a geometric latticeG is a geometric lattice of the same rank into which there is an embeddinge mapping the copoints ofG onto the points of . In this paper we introduce oriented adjoints and prove that they can be embedded into the extension lattice of oriented matroids. Supported by Sonderforschungbereich 21 (DFG)     

A theorem on arrangements of lines in the plane

LetA be an arrangement ofn lines in the plane. IfR ₁, …,R _r arer distinct regions ofA, andR _i is ap _i-gon (i=1, …,r) then we show that . Further we show that for allr this bound is the best possible ifn is sufficiently large. Financial support for this research was provided by the Carnegie Trust for the Universities of Scotland.     

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.     

On the coordinatization of oriented matroids

Several important and hard realizability problems of combinatorial geometry can be reduced to the realizability problem of oriented matroids. In this paper we describe a method to find a coordinatization for a large class of realizable cases. This algorithm has been used successfully to decide several geometric realizability problems. It is shown that all realizations found by our algorithm fulfill the isotopy property.     

A finite crisscross method for oriented matroids

Our paper presents a new finite crisscross method for oriented matroids. Starting from a neither primal nor dual feasible tableau, we reach primal and dual optimal oriented circuits in a finite number of steps if they exist. If there is no optimal tableau then we show that there is no primal feasible circuit or there is no dual feasible cocircuit. So we give a new constructive proof for the general duality theorem (Bland J. Combin. Theory Ser. B 23 (1977), 33–57; Folkman and Lawrence J. Combin. Theory Ser. B 25 (1978), 199–236). Our pivot rule is a generalization of the “anticycling rule” suggested in Bland (op cit; Math. Oper. Res. 2 (1977), 103–107). Finite pivoting rules are given by Edmonds, Fukuda and Todd (Ph.D. dissertation, Univ. of Waterloo, 1982), SIAM Algebraic Discrete Math. 5, No. 4 (1984), 467–485). A general relaxed recursive algorithm was discovered independently by Jensen (Ph.D. thesis, School of OR and IE, Cornell, 1985) which is principally crisscross type. Jensen's is very general and flexible; in fact it can be considered as a family of algorithms. Among the conceivable algorithms in his general family our independently constructed crisscross method is characterized by its extreme simplicity.     

On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids

We introduce the active partition of the ground set of an oriented matroid perspective (or morphism, or quotient, or strong map) on a linearly ordered ground set. The reorientations obtained by arbitrarily reorienting parts of the active partition share the same active partition. This yields an equivalence relation for the set of reorientations of an oriented matroid perspective, whose classes are enumerated by coefficients of the Tutte polynomial, and a remarkable partition of the set of reorientations into Boolean lattices, from which we get a short direct proof of a 4-variable expansion formula for the Tutte polynomial in terms of orientation activities. This formula was given in the last unpublished preprint by Michel Las Vergnas; the above equivalence relation and notion of active partition generalize a former construction in oriented matroids by Michel Las Vergnas and the author; and the possibility of such a proof technique in perspectives was announced in the aforementioned preprint. We also briefly highlight how the 5-variable expansion of the Tutte polynomial in terms of subset activities in matroid perspectives comes in a similar way from the known partition of the power set of the ground set into Boolean lattices related to subset activities (and we complete the proof with a property which was missing in the literature). In particular, the paper applies to matroids and oriented matroids on a linearly ordered ground set, and applies to graph and directed graph homomorphisms on a linearly ordered edge-set.     

Extension spaces of oriented matroids

We study the space of all extensions of a real hyperplane arrangement by a new pseudohyperplane, and, more generally, of an oriented matroid by a new element. The question whether this space has the homotopy type of a sphere is a special case of the “Generalized Baues Problem” of Billera, Kapranov, and Sturmfels, via the Bohne-Dress theorem on zonotopal tilings. We prove that the extension space is spherical for the class of strongly euclidean oriented matroids. This class includes the alternating matroids and all oriented matroids of rank at most 3 or of corank at most 2. In general it is not known whether the extension space is connected for all realizable oriented matroids (hyperplane arrangements). We show that the subspace of realizable extensions is always connected but not necessarily spherical. Nonrealizable oriented matroids of rank 4 with disconnected extension spaces were recently constructed by Mnëv and Richter-Gebert.     

Arithmetic matroids,the Tutte polynomial and toric arrangements

We introduce the notion of an arithmetic matroid whose main example is a list of elements of a finitely generated abelian group. In particular, we study the representability of its dual, providing an extension of the Gale duality to this setting. Guided by the geometry of generalized toric arrangements, we provide a combinatorial interpretation of the associated arithmetic Tutte polynomial, which can be seen as a generalization of Crapo’s formula for the classical Tutte polynomial.     

Inseparability graphs of oriented matroids

We determine the inseparability graphs of uniform oriented matroids and of graphic oriented matroids. For anyr, n such that 4rn–3, examples of rankr uniform oriented matroids onn elements with a given inseparability graph are obtained by simple constructions of polytopes having prescribed separation properties.     

Linear and quadratic programming in oriented matroids

We prove constructively duality theorems of linear and quadratic programming in the combinatorial setting of oriented matroids. One version of our algorithm for linear programing has the interesting feature of maintaining feasibility. The development of the quadratic programming duality result suggests the study of properties of square matrices such as symmetry and positive semi-definiteness in the context of oriented matroids.     

A theorem on average Liapunov functions

A theorem on average Liapunov functions for dynamical systems is generalized. As an illustration the result is used to establish a rather strong coexistence criterion for an ecological system.