共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
本文讨论了准模糊图拟阵基的交换定理,在此基础上给出了基有序的准模糊图拟阵的一些性质. 相似文献
3.
It has recently been shown that infinite matroids can be axiomatized in a way that is very similar to finite matroids and permits duality. This was previously thought impossible, since finitary infinite matroids must have non-finitary duals.In this paper we illustrate the new theory by exhibiting its implications for the cycle and bond matroids of infinite graphs. We also describe their algebraic cycle matroids, those whose circuits are the finite cycles and double rays, and determine their duals. Finally, we give a sufficient condition for a matroid to be representable in a sense adapted to infinite matroids. Which graphic matroids are representable in this sense remains an open question. 相似文献
4.
Alexandre V. Borovik Israel Gelfand Neil White 《Journal of Algebraic Combinatorics》1998,8(3):235-252
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. 相似文献
5.
Rigoberto Flórez 《Discrete Mathematics》2009,309(8):2365-2372
We study a generalization of the concept of harmonic conjugation from projective geometry and full algebraic matroids to a larger class of matroids called harmonic matroids. We use harmonic conjugation to construct a projective plane of prime order in harmonic matroids without using the axioms of projective geometry. As a particular case we have a combinatorial construction of a projective plane of prime order in full algebraic matroids. 相似文献
6.
Ilda P.F. da Silva 《Discrete Mathematics》2008,308(16):3574-3585
We define and study a new class of matroids: cubic matroids. Cubic matroids include, as a particular case, all affine cubes over an arbitrary field. There is only one known orientable cubic matroid: the real affine cube. The main results establish as an invariant of orientable cubic matroids the structure of the subset of acyclic orientations with LV-face lattice isomorphic to the face lattice of the real cube or, equivalently, with the same signed circuits of length 4 as the real cube. 相似文献
7.
We construct a new family of minimal non-orientable matroids of rank three. Some of these matroids embed in Desarguesian projective planes. This answers a question of Ziegler: for every prime power q, find a minimal non-orientable submatroid of the projective plane over the q-element field. 相似文献
8.
Eunice Gogo Mphako 《Czechoslovak Mathematical Journal》2006,56(1):19-25
We give an example of a class of binary matroids with a cocircuit partition and we give some characteristics of a set of cocircuits
of such binary matroids which forms a partition of the ground set. 相似文献
9.
10.
Günter M. Ziegler 《Geometriae Dedicata》1991,38(3):365-371
We construct an infinite family of minor-minimal rank three matroids that are not orientable. 相似文献
11.
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). 相似文献
12.
Matroid bundles, introduced by MacPherson, are combinatorial analogues of real vector bundles. This paper sets up the foundations
of matroid bundles. It defines a natural transformation from isomorphism classes of real vector bundles to isomorphism classes
of matroid bundles. It then gives a transformation from matroid bundles to spherical quasifibrations, by showing that the
geometric realization of a matroid bundle is a spherical quasifibration. The poset of oriented matroids of a fixed rank classifies
matroid bundles, and the above transformations give a splitting from topology to combinatorics back to topology. A consequence
is that the mod 2 cohomology of the poset of rank k oriented matroids (this poset classifies matroid bundles) contains the free polynomial ring on the first k Stiefel-Whitney classes. 相似文献
13.
Building on the recent axiomatisation of infinite matroids with duality, we present a theory of representability for infinite matroids. This notion of representability allows for infinite sums, and is preserved under duality. 相似文献
14.
Sanjay Rajpal 《Discrete Mathematics》1998,190(1-3):191-200
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. 相似文献
15.
Will Agnew-Svoboda Alana Huszar Erin McNicholas Jeff Schreiner-McGraw Colin Starr Corrine Yap 《Discrete Mathematics》2019,342(8):2254-2269
Analogous to the concept of uniquely pancyclic graphs, we define a uniquely pancyclic (UPC) matroid of rank to be a (simple) rank- matroid containing exactly one circuit of each length for . 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 . 相似文献
16.
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
3
, 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. 相似文献
17.
《Discrete Mathematics》2022,345(7):112796
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. 相似文献
18.
We consider the problem of classifying all finite basis-transitive matroids and reduce it to the classification of the finite basis-transitive and point-primitive simple matroids (or geometric lattices, or dimensional linear spaces). Our main result shows how a basis- and point-transitive simple matroid is decomposed into a so-called supersum. In particular each block of imprimitivity bears the structure of two closely related simple matroids, and the set of blocks of imprimitivity bears the structure of a point- and basis-transitive matroid. 相似文献
19.
All orientations of binary and ternary matroids are representable [R.G. Bland, M. Las Vergnas, Orientability of matroids, J. Combinatorial Theory Ser. B 24 (1) (1978) 94–123; J. Lee, M. Scobee, A characterization of the orientations of ternary matroids, J. Combin. Theory Ser. B 77 (2) (1999) 263–291]. In this paper we show that this is not the case for matroids that are representable over GF(pk) where k2. Specifically, we show that there are orientations of the rank-k free spike that are not representable for all k4. The proof uses threshold functions to obtain an upper bound on the number of representable orientations of the free spikes. 相似文献
20.
Felipe Rincón 《Journal of Combinatorial Theory, Series A》2012,119(1):14-32
The spinor variety is cut out by the quadratic Wick relations among the principal Pfaffians of an n×n skew-symmetric matrix. Its points correspond to n-dimensional isotropic subspaces of a 2n-dimensional vector space. In this paper we tropicalize this picture, and we develop a combinatorial theory of tropical Wick vectors and tropical linear spaces that are tropically isotropic. We characterize tropical Wick vectors in terms of subdivisions of Δ-matroid polytopes, and we examine to what extent the Wick relations form a tropical basis. Our theory generalizes several results for tropical linear spaces and valuated matroids to the class of Coxeter matroids of type D. 相似文献