共查询到20条相似文献,搜索用时 31 毫秒
1.
J. -P. Roudneff 《Combinatorica》1989,9(1):75-84
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. 相似文献
2.
Jim Lawrence 《Discrete and Computational Geometry》2005,33(3):445-462
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. 相似文献
3.
Jürgen Bokowski Jürgen Richter Bernd Sturmfels 《Discrete and Computational Geometry》1990,5(1):333-350
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. 相似文献
4.
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. 相似文献
5.
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. 相似文献
6.
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. 相似文献
7.
8.
Vanessa Chatelain 《European Journal of Combinatorics》2012,33(2):215-219
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. 相似文献
9.
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. 相似文献
10.
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. 相似文献
11.
Arnau Padrol 《Discrete and Computational Geometry》2013,50(4):865-902
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. 相似文献
12.
Jesús A. De Loera David C. Haws Matthias Köppe 《Discrete and Computational Geometry》2009,42(4):703-704
We investigate properties of Ehrhart polynomials for matroid polytopes, independence matroid polytopes, and polymatroids. In the first half of the paper we prove that, for fixed rank, Ehrhart polynomials of matroid polytopes and polymatroids are computable in polynomial time. The proof relies on the geometry of these polytopes as well as a new refined analysis of the evaluation of Todd polynomials. In the second half we discuss two conjectures about the h *-vector and the coefficients of Ehrhart polynomials of matroid polytopes; we provide theoretical and computational evidence for their validity. 相似文献
13.
H. Günzel 《Discrete and Computational Geometry》1996,15(2):121-145
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 ℝ
n
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”. 相似文献
14.
J. Rambau 《Discrete and Computational Geometry》2002,27(1):155-161
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. 相似文献
15.
Michel Las Vergnas 《Journal of Combinatorial Theory, Series B》1980,29(2):231-243
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. 相似文献
16.
Yoshitake Matsumoto Sonoko Moriyama Hiroshi Imai David Bremner 《Discrete and Computational Geometry》2012,47(1):17-43
Matroids are combinatorial abstractions for point configurations and hyperplane arrangements, which are fundamental objects
in discrete geometry. Matroids merely encode incidence information of geometric configurations such as collinearity or coplanarity,
but they are still enough to describe many problems in discrete geometry, which are called incidence problems. We investigate
two kinds of incidence problem, the points–lines–planes conjecture and the so-called Sylvester–Gallai type problems derived
from the Sylvester–Gallai theorem, by developing a new algorithm for the enumeration of non-isomorphic matroids. We confirm
the conjectures of Welsh–Seymour on ≤11 points in ℝ3 and that of Motzkin on ≤12 lines in ℝ2, extending previous results. With respect to matroids, this algorithm succeeds to enumerate a complete list of the isomorph-free
rank 4 matroids on 10 elements. When geometric configurations corresponding to specific matroids are of interest in some incidence
problems, they should be analyzed on oriented matroids. Using an encoding of oriented matroid axioms as a boolean satisfiability
(SAT) problem, we also enumerate oriented matroids from the matroids of rank 3 on n≤12 elements and rank 4 on n≤9 elements. We further list several new minimal non-orientable matroids. 相似文献
17.
Michael J. Todd 《Discrete Mathematics》1976,16(1):61-70
In an earlier paper we defined a class of matroids whose circuit are combinatorial generalizations of simple polytopes; these matroids are the binary analogue of the simplical geometrics of Crapo and Rota. Here we find necessary and sufficient conditions for a matroid to be isomorphic to such a binary simplical matroid. 相似文献
18.
Meena Jagadeesan 《代数通讯》2013,41(11):4945-4972
The Möbius polynomial is an invariant of ranked posets, closely related to the Möbius function. In this paper, we study the Möbius polynomial of face posets of convex polytopes. We present formulas for computing the Möbius polynomial of the face poset of a pyramid or a prism over an existing polytope, or of the gluing of two or more polytopes in terms of the Möbius polynomials of the original polytopes. We also present general formulas for calculating Möbius polynomials of face posets of simplicial polytopes and of Eulerian posets in terms of their f-vectors and some additional constraints. 相似文献
19.
The goal of this article is to obtain bounds on the coefficients of modular and integral flow and tension polynomials of graphs.
To this end we use the fact that these polynomials can be realized as Ehrhart polynomials of inside-out polytopes. Inside-out
polytopes come with an associated relative polytopal complex and, for a wide class of inside-out polytopes, we show that this
complex has a convex ear decomposition. This leads to the desired bounds on the coefficients of these polynomials. 相似文献
20.
We study a family of polynomials whose values express degrees of Schubert varieties in the generalized complex flag manifold
G/B. The polynomials are given by weighted sums over saturated chains in the Bruhat order. We derive several explicit formulas
for these polynomials, and investigate their relations with Schubert polynomials, harmonic polynomials, Demazure characters,
and generalized Littlewood-Richardson coefficients. In the second half of the paper, we study the classical flag manifold
and discuss related combinatorial objects: flagged Schur polynomials, 312-avoiding permutations, generalized Gelfand-Tsetlin
polytopes, the inverse Schubert-Kostka matrix, parking functions, and binary trees.
A.P. was supported in part by National Science Foundation grant DMS-0201494 and by Alfred P. Sloan Foundation research fellowship.
R.S. was supported in part by National Science Foundation grant DMS-9988459. 相似文献