The active bijection in graphs, hyperplane arrangements, and oriented matroids, 1: The fully optimal basis of a bounded region

The present paper is the first in a series of four dealing with a mapping, introduced by the present authors, from orientations to spanning trees in graphs, from regions to simplices in real hyperplane arrangements, from reorientations to bases in oriented matroids (in order of increasing generality). This mapping is actually defined for ordered oriented matroids. We call it the active orientation-to-basis mapping, in reference to an extensive use of activities, a notion depending on a linear ordering, first introduced by W.T. Tutte for spanning trees in graphs. The active mapping, which preserves activities, can be considered as a bijective generalization of a polynomial identity relating two expressions–one in terms of activities of reorientations, and the other in terms of activities of bases–of the Tutte polynomial of a graph, a hyperplane arrangement or an oriented matroid. Specializations include bijective versions of well-known enumerative results related to the counting of acyclic orientations in graphs or of regions in hyperplane arrangements. Other interesting features of the active mapping are links established between linear programming and the Tutte polynomial.We consider here the bounded case of the active mapping, where bounded corresponds to bipolar orientations in the case of graphs, and refers to bounded regions in the case of real hyperplane arrangements, or of oriented matroids. In terms of activities, this is the uniactive internal case. We introduce fully optimal bases, simply defined in terms of signs, strengthening optimal bases of linear programming. An optimal basis is associated with one flat with a maximality property, whereas a fully optimal basis is equivalent to a complete flag of flats, each with a maximality property. The main results of the paper are that a bounded region has a unique fully optimal basis, and that, up to negating all signs, fully optimal bases provide a bijection between bounded regions and uniactive internal bases. In the bounded case, up to negating all signs, the active mapping is a bijection.     

A Linear Programming Construction of Fully Optimal Bases in Graphs and Hyperplane Arrangements

The fully optimal basis of a bounded acyclic oriented matroid on a linearly ordered set has been defined and studied by the present authors in a series of papers, dealing with graphs, hyperplane arrangements, and oriented matroids (in order of increasing generality). This notion provides a bijection between bipolar orientations and uniactive internal spanning trees in a graph resp. bounded regions and uniactive internal bases in a hyperplane arrangement or an oriented matroid (in the sense of Tutte activities). This bijection is the basic case of a general activity preserving bijection between reorientations and subsets of an oriented matroid, called the active bijection, providing bijective versions of various classical enumerative results.Fully optimal bases can be considered as a strenghtening of optimal bases from linear programming, with a simple combinatorial definition. Our first construction used this purely combinatorial characterization, providing directly an algorithm to compute in fact the reverse bijection. A new definition uses a direct construction in terms of a linear programming. The fully optimal basis optimizes a sequence of nested faces with respect to a sequence of objective functions (whereas an optimal basis in the usual sense optimizes one vertex with respect to one objective function). This note presents this construction in terms of graphs and linear algebra.     

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.     

On the Bounded Complex of an Affine Oriented Matroid

We prove that the bounded complex of an affine oriented matroid is pure and collapsible. We also generalize Zaslavsky's central decomposition theorem for hyperplane arrangements to affine oriented matroids.     

The entropic discriminant

The entropic discriminant is a non-negative polynomial associated to a matrix. It arises in contexts ranging from statistics and linear programming to singularity theory and algebraic geometry. It describes the complex branch locus of the polar map of a real hyperplane arrangement, and it vanishes when the equations defining the analytic center of a linear program have a complex double root. We study the geometry of the entropic discriminant, and we express its degree in terms of the characteristic polynomial of the underlying matroid. Singularities of reciprocal linear spaces play a key role. In the corank-one case, the entropic discriminant admits a sum of squares representation derived from the discriminant of a characteristic polynomial of a symmetric matrix.     

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.     

Face numbers of Engström representations of matroids

A classic problem in the theory of matroids is to find a subspace arrangement, such as a hyperplane or pseudosphere arrangement, whose intersection poset is isomorphic to a prescribed geometric lattice. Engström gave an explicit construction for an infinite family of such arrangements, indexed by the set of finite regular CW complexes. In this paper, we compute the face numbers of these topological representations in terms of the face numbers of the indexing complexes and give upper bounds on the total number of faces in these objects. Moreover, for a fixed rank, we show that the total number of faces in the Engström representation corresponding to a codimension one homotopy sphere arrangement is bounded above by a polynomial in the number of elements of the matroid, whose degree is one less than the matroid’s rank.     

Asymptotic cohomological functions of toric divisors

We study functions on the class group of a toric variety measuring the rates of growth of the cohomology groups of multiples of divisors. We show that these functions are piecewise polynomial with respect to finite polyhedral chamber decompositions. As applications, we express the self-intersection number of a T-Cartier divisor as a linear combination of the volumes of the bounded regions in the corresponding hyperplane arrangement and prove an asymptotic converse to Serre vanishing.     

On the Gorensteinness of broken circuit complexes and Orlik–Terao ideals

It is proved that the broken circuit complex of an ordered matroid is Gorenstein if and only if it is a complete intersection. Several characterizations for a matroid that admits such an order are then given, with particular interest in the h-vector of broken circuit complexes of the matroid. As an application, we prove that the Orlik–Terao algebra of a hyperplane arrangement is Gorenstein if and only if it is a complete intersection. Interestingly, our result shows that the complete intersection property (and hence the Gorensteinness as well) of the Orlik–Terao algebra can be determined from the last two nonzero entries of its h-vector.     

Hypergeometric Polynomials and Integer Programming

We examine connections between A-hypergeometric differential equations and the theory of integer programming. In the first part, we develop a hypergeometric sensitivity analysis for small variations of constraint constants with creation operators and b-functions. In the second part, we study the indicial polynomial (b-function) along the hyperplane xi=0 via a correspondence between the optimal value of an integer programming problem and the roots of the indicial polynomial. Gröbner bases are used to prove theorems and give counter examples.     

Broken circuit complexes and hyperplane arrangements

We study Stanley–Reisner ideals of broken circuit complexes and characterize those ones admitting linear resolutions or being complete intersections. These results will then be used to characterize hyperplane arrangements whose Orlik–Terao ideal has the same properties. As an application, we improve a result of Wilf on upper bounds for the coefficients of the chromatic polynomial of a maximal planar graph. We also show that for a matroid with a complete intersection broken circuit complex, the supersolvability of the matroid is equivalent to the Koszulness of its Orlik–Solomon algebra.     

Euler's relation,möbius functions and matroid identities

We give a short combinatorial proof of the Euler relation for convex polytopes in the context of oriented matroids. Using counting arguments we derive from the Euler relation several identities holding in the lattice of flats of an oriented matroid. These identities are proven for any matroid by Möbius inversion.     

Hyperplane arrangements with a lattice of regions

A hyperplane arrangement is a finite set of hyperplanes through the origin in a finite-dimensional real vector space. Such an arrangement divides the vector space into a finite set of regions. Every such region determines a partial order on the set of all regions in which these are ordered according to their combinatorial distance from the fixed base region.We show that the base region is simplicial whenever the poset of regions is a lattice and that conversely this condition is sufficient for the lattice property for three-dimensional arrangements, but not in higher dimensions. For simplicial arrangements, the poset of regions is always a lattice.In the case of supersolvable arrangements (arrangements for which the lattice of intersections of hyperplanes is supersolvable), the poset of regions is a lattice if the base region is suitably chosen. We describe the geometric structure of such arrangements and derive an expression for the rank-generating function similar to a known one for Coxeter arrangements. For arrangements with a lattice of regions we give a geometric interpretation of the lattice property in terms of a closure operator defined on the set of hyperplanes.The results generalize to oriented matroids. We show that the adjacency graph (and poset of regions) of an arrangement determines the associated oriented matroid and hence in particular the lattice of intersections.The work of Anders Björner was supported in part by a grant from the NSF. Paul Edelman's work was supported in part by NSF Grants DMS-8612446 and DMS-8700995. The work of Günter Ziegler was done while he held a Norman Levinson Graduate Fellowship at MIT.     

Flag enumerations of matroid base polytopes

In this paper, we study flag structures of matroid base polytopes. We describe faces of matroid base polytopes in terms of matroid data, and give conditions for hyperplane splits of matroid base polytopes. Also, we show how the cd-index of a polytope can be expressed when a polytope is split by a hyperplane, and apply these to the cd-index of a matroid base polytope of a rank 2 matroid.     

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.     

Euclideaness and final polynomials in oriented matroid theory

This paper deals with a geometric construction of algebraic non-realizability proofs for certain oriented matroids. As main result we obtain an algorithm which generates a (bi-quadratic) final polynomial [3], [5] for any non-euclidean oriented matroid. Here we apply the results of Edmonds, Fukuda and Mandel [6], [7] concerning non-degenerate cycling of linear programs in non-euclidean oriented matroids.     

On the generalized Ball bases

The Ball basis was introduced for cubic polynomials by Ball, and two different generalizations for higher degree m polynomials have been called the Said–Ball and the Wang–Ball basis, respectively. In this paper, we analyze some shape preserving and stability properties of these bases. We prove that the Wang–Ball basis is strictly monotonicity preserving for all m. However, it is not geometrically convexity preserving and is not totally positive for m>3, in contrast with the Said–Ball basis. We prove that the Said–Ball basis is better conditioned than the Wang–Ball basis and we include a stable conversion between both generalized Ball bases. The Wang–Ball basis has an evaluation algorithm with linear complexity. We perform an error analysis of the evaluation algorithms of both bases and compare them with other algorithms for polynomial evaluation.     

A new constrained edit distance between quotiented ordered trees

In this paper we propose a dynamic programming algorithm to compare two quotiented ordered trees using a constrained edit distance. An ordered tree is a tree in which the left-to-right order among siblings is significant. A quotiented ordered tree is an ordered tree T with an equivalence relation on vertices and such that, when the equivalence classes are collapsed to super-nodes, the graph so obtained is an ordered tree as well. Based on an algorithm proposed by Zhang and Shasha [K. Zhang, D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing 18 (6) (1989) 1245–1262] and introducing new notations, we describe a tree edit distance between quotiented ordered trees preserving equivalence relations on vertices during computation which works in polynomial time. Its application to RNA secondary structures comparison is finally presented.     

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.