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.     

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.     

New Results on Global Rank Axioms of Poset Matroids

An excellent introduction to the topic of poset matroids is due to M. Barnabei, G. Nicoletti and L. Pezzoli. On the basis of their work, we have obtained the global rank axioms for poset matroids.In this paper, we study the special integral function f and obtain a new class of poset matroids from the old ones, and then we generalize this result according to the properties of f. Almost all of these results can be regarded as the application of global rank axioms for poset matroids. The main results in our paper have, indeed, investigated the restriction of the basis of the poset matroid, and we give them the corresponding geometric interpretation.     

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.     

Checking oriented matroid isomorphism by means of canonical labeling

In this paper a method for establishing the structural equivalence of sets of planar geometric features composed by points and lines is presented. It is based on oriented matroid theory, a setting in which the combinatorial structural properties of these geometric features, such as incidence, order, partitioning, separation, and convexity, can be represented and analyzed in a coordinate-free manner. Projective transformations in computer vision keep in general the convexity property which implies an invariant oriented matroid representation of the planar geometric features under this class of transformations. As long as points and lines are in general position, the oriented matroid representation is also insensitive to small changes in the geometric image features. However the oriented matroid representation depends on the labeling of its elements. Checking the structural equivalence of the above mentioned geometric features represented by means of oriented matroids implies establishing whether two oriented matroid representations are equivalent up to relabeling of their elements. This is the oriented matroid isomorphism problem which is solved in this paper by means of a canonical labeling of the elements.     

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.     

A matroid-friendly basis for the quasisymmetric functions

A new Z-basis for the space of quasisymmetric functions (QSym, for short) is presented. It is shown to have nonnegative structure constants, and several interesting properties relative to the quasisymmetric functions associated to matroids by the Hopf algebra morphism F of Billera, Jia, and Reiner [L.J. Billera, N. Jia, V. Reiner, A quasisymmetric function for matroids, arXiv:math.CO/0606646]. In particular, for loopless matroids, this basis reflects the grading by matroid rank, as well as by the size of the ground set. It is shown that the morphism F distinguishes isomorphism classes of rank two matroids, and that decomposability of the quasisymmetric function of a rank two matroid mirrors the decomposability of its base polytope. An affirmative answer to the Hilbert basis question raised in [L.J. Billera, N. Jia, V. Reiner, A quasisymmetric function for matroids, arXiv:math.CO/0606646] is given.     

On Recognizing Frame and Lifted‐Graphic Matroids

We prove that there is no polynomial with the property that a matroid M can be determined to be either a lifted‐graphic or frame matroid using at most rank evaluations. This resolves two conjectures of Geelen, Gerards, and Whittle (Quasi‐graphic matroids, to appear in J. Graph Theory).     

On the Circuit-cocircuit Intersection Conjecture

Oxley has conjectured that for k≥4, if a matroid M has a k-element set that is the intersection of a circuit and a cocircuit, then M has a (k−2)-element set that is the intersection of a circuit and a cocircuit. In this paper we prove a stronger version of this conjecture for regular matroids. We also show that the stronger result does not hold for binary matroids. The second author was partially supported by CNPq (grant no 302195/02-5) and the ProNEx/CNPq (grant no 664107/97-4).     

The Lattice of Cyclic Flats of a Matroid

A flat of a matroid is cyclic if it is a union of circuits. The cyclic flats of a matroid form a lattice under inclusion. We study these lattices and explore matroids from the perspective of cyclic flats. In particular, we show that every lattice is isomorphic to the lattice of cyclic flats of a matroid. We give a necessary and sufficient condition for a lattice of sets and a function to be the lattice of cyclic flats of a matroid and the restriction of the corresponding rank function to . We apply this perspective to give an alternative view of the free product of matroids and we show how to compute the Tutte polynomial of the free product in terms of the Tutte polynomials of the constituent matroids. We define cyclic width and show that this concept gives rise to minor-closed, dual-closed classes of matroids, two of which contain only transversal matroids. Received May 29, 2005     

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

ContributionsOn binary k-paving matroids and Reed-Muller codes

A matroid M of rank r k is k-paving if all of its circuits have cardinality exceeding r − k. In this paper, we develop some basic results concerning k-paving matroids and their connections with codes. Also, we determine all binary 2-paving matroids.     

任意基数集上的拟阵之单扩张

对于由Betten和Wenzel于2003年提出的任意基数集上的拟阵其相应的秩公理给予了证明,并将此结果用于研究任意基数集上的拟阵的单扩张问题.     

On Maximum-sized k-Regular Matroids

 Let k be an integer exceeding one. The class of k-regular matroids is a generalization of the classes of regular and near-regular matroids. A simple rank-r regular matroid has the maximum number of points if and only if it is isomorphic to M(K _r+1), the cycle matroid of the complete graph on r+1 vertices. A simple rank-r near-regular matroid has the maximum number of points if and only if it is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding a point to a 3-point line of M(K _r+2) and then contracting this point. This paper determines the maximum number of points that a simple rank-r k-regular matroid can have and determines all such matroids having this number. With one exception, there is exactly one such matroid. This matroid is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding k independent points to a flat of M(K _r+k+1) isomorphic to M(K _k+2) and then contracting each of these points. Revised: July 27, 1998     

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.     

On the regularity of orientable matroids

We present two characterizations of regular matroids among orientable matroids and use them to give a measure of “how far” an orientable matroid is from being regular.     

Symplectic Matroids

A symplectic matroid is a collection B of k-element subsets of J = {1, 2, ..., n, 1*, 2*, ...; n*}, each of which contains not both of i and i* for every i n, and which has the additional property that for any linear ordering of J such that i j implies j* i* and i j* implies j i* for all i, j n, B has a member which dominates element-wise every other member of B. Symplectic matroids are a special case of Coxeter matroids, namely the case where the Coxeter group is the hyperoctahedral group, the group of symmetries of the n-cube. In this paper we develop the basic properties of symplectic matroids in a largely self-contained and elementary fashion. Many of these results are analogous to results for ordinary matroids (which are Coxeter matroids for the symmetric group), yet most are not generalizable to arbitrary Coxeter matroids. For example, representable symplectic matroids arise from totally isotropic subspaces of a symplectic space very similarly to the way in which representable ordinary matroids arise from a subspace of a vector space. We also examine Lagrangian matroids, which are the special case of symplectic matroids where k = n, and which are equivalent to Bouchet's symmetric matroids or 2-matroids.     

Oriented matroid systems

The domination invariant has played an important part in reliability theory. While most of the work in this field has been restricted to various types of network system models, many of the results can be generalized to much wider families of systems associated with matroids. Previous papers have explored the relation between undirected network systems and matroids. In this paper the main focus is on directed network systems and their relation to oriented matroids. An oriented matroid is a special type of matroid where the circuits are signed sets. Using these signed sets one can e.g., obtain a set theoretic representation of the direction of the edges of a directed network system. Classical results for directed network systems include the fact that the signed domination is either +1 or −1 if the network is acyclic, and zero otherwise. It turns out that these results can be generalized to systems derived from oriented matroids. Several classes of systems for which the generalized results hold will be discussed. These include oriented versions of k-out-of-n systems and a certain class of systems associated with matrices.