Mutation Polynomials and Oriented Matroids

Several polynomials are of use in various enumeration problems concerning objects in oriented matroids. Chief among these is the Radon catalog. We continue to study these, as well as the total polynomials of uniform oriented matroids, by considering the effect on them of mutations of the uniform oriented matroid. The notion of a ``mutation polynomial' is introduced to facilitate the study. The affine spans of the Radon catalogs and the total polynomials in the appropriate rational vector spaces of polynomials are determined, and bases for the Z -modules generated by the mutation polynomials are found. The Radon polynomials associated with alternating oriented matroids are described; it is conjectured that a certain extremal property, like that held by cyclic polytopes among simplicial polytopes, is possessed by them. Received November 20, 1998, and in revised form August 21, 1999. Online publication May 19, 2000.     

Visibility Graphs and Oriented Matroids

Abstract. We describe a set of necessary conditions for a given graph to be the visibility graph of a simple polygon. For every graph satisfying these conditions we show that a uniform rank 3 oriented matroid can be constructed in polynomial time, which if affinely coordinatizable yields a simple polygon whose visibility graph is isomorphic to the given graph.     

Visibility Graphs and Oriented Matroids

   Abstract. We describe a set of necessary conditions for a given graph to be the visibility graph of a simple polygon. For every graph satisfying these conditions we show that a uniform rank 3 oriented matroid can be constructed in polynomial time, which if affinely coordinatizable yields a simple polygon whose visibility graph is isomorphic to the given graph.     

Oriented Matroids and Associated Valuations

It is possible to associate a valuation on the orthant lattice with each oriented matroid. In the case of uniform oriented matroids, it is not difficult to provide a characterization of the corresponding valuations. This is done here, thereby establishing a new characterization of the uniform oriented matroids themselves. Additionally, the connection between the valuations and the total polynomials associated with uniform oriented matroids is noted.     

On the Generation of Oriented Matroids

We provide a multiple purpose algorithm for generating oriented matroids. An application disproves a conjecture of Grünbaum that every closed triangulated orientable 2-manifold can be embedded geometrically in R ³ , i.e., with flat triangles and without self-intersections. We can show in particular that there exists an infinite class of orientable triangulated closed 2-manifolds for each genus g \geq 6 that cannot be embedded geometrically in Euclidean 3-space. Our algorithm is interesting in its own right as a tool for many investigations in which oriented matroids play a key role. Received January 7, 1999, and in final form July 16, 1999.     

The Topological Representation of Oriented Matroids

We present a new proof of the Topological Representation Theorem for oriented matroids in the general rank case. Our proof is based on an earlier rank 3 version. It uses hyperline sequences and the generalized Schonflies theorem. As an application, we show that one can read off oriented matroids from arrangements of embedded spheres of codimension one, even if wild spheres are involved.     

A Commutative Algebra for Oriented Matroids

Let V be a vector space of dimension d over a field K and let A be a central arrangement of hyperplanes in V. To answer a question posed by K. Aomoto, P. Orlik and H. Terao construct a commutative K -algebra U(A) in terms of the equations for the hyperplanes of A. In the course of their work the following question naturally occurred: \circ Is U(A) determined by the intersection lattice L(A) of the hyperplanes of A? We give a negative answer to this question. The theory of oriented matroids gives rise to a combinatorial analogue of the algebra of Orlik—Terao, which is the main tool of our proofs. Received November 7, 2000, and in revised form May 18, 2001. Online publication November 2, 2001.     

Many Neighborly Polytopes and Oriented Matroids

In this paper we present a new technique to construct neighborly polytopes, and use it to prove a lower bound of ${\big (( r+d ) ^{( \frac{r}{2}+\frac{d}{2} )^{2}}\big )}\big /{\big ({r}^{{(\frac{r}{2})}^{2}} {d}^{{(\frac{d}{2})}^{2}}{\mathrm{e}^{3\frac{r}{2}\frac{d}{2}}}\big )}$ for the number of combinatorial types of vertex-labeled neighborly polytopes in even dimension d with $r+d+1$ vertices. This improves current bounds on the number of combinatorial types of polytopes. The previous best lower bounds for the number of neighborly polytopes were found by Shemer in 1982 using a technique called the Sewing Construction. We provide a new simple proof that sewing works, and generalize it to oriented matroids in two ways: to Extended Sewing and to Gale Sewing. Our lower bound is obtained by estimating the number of polytopes that can be constructed via Gale Sewing. Combining both new techniques, we are also able to construct many non-realizable neighborly oriented matroids.     

Complete Enumeration of Small Realizable Oriented Matroids

Enumeration of all combinatorial types of point configurations and polytopes is a fundamental problem in combinatorial geometry. Although many studies have been done, most of them are for 2-dimensional and non-degenerate cases. Finschi and Fukuda (Discrete Comput Geom 27:117–136, 2002) published the first database of oriented matroids including degenerate (i.e., non-uniform) ones and of higher ranks. In this paper, we investigate algorithmic ways to classify them in terms of realizability, although the underlying decision problem of realizability checking is NP-hard. As an application, we determine all possible combinatorial types (including degenerate ones) of 3-dimensional configurations of 8 points, 2-dimensional configurations of 9 points, and 5-dimensional configurations of 9 points. We also determine all possible combinatorial types of 5-polytopes with nine vertices.     

Intersection and Linking Numbers in Oriented Matroids

We introduce for oriented matroids a generalization of the concepts of intersection and linking numbers in Euclidean space, with most of their main properties (see Wu). As an application, we reprove a result of Brehm in a slightly extended form.     

Cycles in Circuit Graphs of Matroids

Let G be the circuit graph of any connected matroid. We prove that G is edge-pancyclic if it has at least three vertices. This work is supported by the National Natural Science Foundation(60673047) and the Doctoral Program Foundation of Education Ministry (20040422004) of China.     

Spatial Graphs and Oriented Matroids: the Trefoil

Let m=m(K) be the smallest positive integer such that every linear spatial representation of the complete graph with n vertices, n ≥ m , contains either the knot K or its mirror . In this paper we show that m(Trefoil)=7 . The proof uses the theory of oriented matroids. Received July 8, 1997, and in revised form January 16, 1998.     

New Examples of Oriented Matroids with Disconnected Realization Spaces

We construct oriented matroids of rank 3 on 13 points whose realization spaces are disconnected. They are defined on smaller point-sets than the known examples with this property. Moreover, we construct one on 13 points whose realization space is a connected but non-irreducible semialgebraic variety.     

极小圈模对与二元域拟阵的特征

研究极小圈模对与二元域拟阵的特征.首先给出拟阵M的极小圈模对,模对的并的秩与相应的超平面的交的秩三者的等价关系.在两个极小圈不等的条件下,证明了满足极小圈消去公理的极小圈是唯一的并且极小圈模对的对称差包含在其中,结合极小圈的对称差的表示,证明了极小圈与基的差的绝对值大于等于2.后面两个证明都把原来的必要条件推广为充要条件.最后,用M上不相同的极小圈,极小圈模对,极小圈的对称差表示,M上不相等的超平面,超平面的并不等于E及满足的秩等式极简单地刻划了二元域拟阵M的特征.     

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.