An intersection theorem for supermatroids

We generalize the matroid intersection theorem to distributive supermatroids, a structure that extends the matroid to the partially ordered ground set. Distributive supermatroids are special cases of both supermatroids and greedoids, and they generalize polymatroids. This is the first good characterization proved for the intersection problem of an independence system where the ground set is partially ordered. The characterization given has a more complex structure than the matroid (or polymatroid) intersection theorem.     

Coxeter matroid polytopes

If Δ is a polytope in real affine space, each edge of Δ determines a reflection in the perpendicular bisector of the edge. The exchange groupW (Δ) is the group generated by these reflections, and Δ is a (Coxeter) matroid polytope if this group is finite. This simple concept of matroid polytope turns out to be an equivalent way to define Coxeter matroids. The Gelfand-Serganova Theorem and the structure of the exchange group both give us information about the matroid polytope. We then specialize this information to the case of ordinary matroids; the matroid polytope by our definition in this case turns out to be a facet of the classical matroid polytope familiar to matroid theorists. This work was supported in part by NSA grant MDA904-95-1-1056.     

Two algorithms for matroids

A matroid may be characterized by the collection of its bases or by the collection of its circuits. Along with any matroid is a uniquely determined dual matroid. Given the bases of a matroid, it is possible to show that base complements are precisely the bases of the dual. So it is easy to construct bases of the dual given the bases of the original matroid.This paper provides two results. The first enables construction of all circuits of the dual matroid from circuits of the original matroid. The second constructs all bases of a matroid from its circuits.     

An Adjacency Criterion for Coxeter Matroids

A Coxeter matroid is a generalization of matroid, ordinary matroid being the case corresponding to the family of Coxeter groups A _n , which are isomorphic to the symmetric groups. A basic result in the subject is a geometric characterization of Coxeter matroid in terms of the matroid polytope, a result first stated by Gelfand and Serganova. This paper concerns properties of the matroid polytope. In particular, a criterion is given for adjacency of vertices in the matroid polytope.     

On the (co)girth of a connected matroid

This article studies the girth and cogirth problems for a connected matroid. The problem of finding the cogirth of a graphic matroid has been intensively studied, but studies on the equivalent problem for a vector matroid or a general matroid have been rarely reported. Based on the duality and connectivity of a matroid, we prove properties associated with the girth and cogirth of a matroid whose contraction or restriction is disconnected. Then, we devise algorithms that find the cogirth of a matroid M from the matroids associated with the direct sum components of the restriction of M. As a result, the problem of finding the (co)girth of a matroid can be decomposed into a set of smaller sub-problems, which helps alleviate the computation. Finally, we implement and demonstrate the application of our algorithms to vector matroids.     

Setup optimization problems with matroid structure

A class of ordered sets is investigated for which the setup minimization problem gives rise to matroid independence systems. This class includes in particular all N-free ordered sets and all M-free ordered sets of height at most one. The matroid structure can be recognized efficiently; whence the matroid greedy algorithm may be used to solve the weighted minimization problem.Supported by Sonderforschungsbereich 303 (DFG), Institut für Ökonometrie und Operations Research, Univesität Bonn, W. Germany.     

Dimensions, matroids, and dense pairs of first-order structures

A structure M is pregeometric if the algebraic closure is a pregeometry in all structures elementarily equivalent to M. We define a generalisation: structures with an existential matroid. The main examples are superstable groups of Lascar U-rank a power of ω and d-minimal expansion of fields. Ultraproducts of pregeometric structures expanding an integral domain, while not pregeometric in general, do have a unique existential matroid.Generalising previous results by van den Dries, we define dense elementary pairs of structures expanding an integral domain and with an existential matroid, and we show that the corresponding theories have natural completions, whose models also have a unique existential matroid. We also extend the above result to dense tuples of structures.     

Truncation Formulas for Invariant Polynomials of Matroids and Geometric Lattices

This paper considers the truncation of matroids and geometric lattices. It is shown that the truncated matroid of a representable matroid is again representable. Truncation formulas are given for the coboundary and M?bius polynomial of a geometric lattice and the spectrum polynomial of a matroid, generalizing the truncation formula of the rank generating polynomial of a matroid by Britz.     

The lattice of convex sets of an oriented matroid

Using the theory of the anti-exchange closure the structure of the lattice of convex sets of an acyclic oriented matroid is described. A new expression for the characteristic polynomial of the underlying matroid is proven using this analysis.     

Some Features of Gaussian Elimination with Rook Pivoting

Rook pivoting is a relatively new pivoting strategy used in Gaussian elimination (GE). It can be as computationally cheap as partial pivoting and as stable as complete pivoting. This paper shows some new attractive features of rook pivoting. We first derive error bounds for the LU factors computed by GE and show rook pivoting usually gives a highly accurate U factor. Then we show accuracy of the computed solution of a linear system by rook pivoting is essentially independent of row scaling of the coefficient matrix. Thus if the matrix is ill-conditioned due to bad row scaling a highly accurate solution can usually be obtained. Finally for a typical inversion method involving the LU factorization we show rook pivoting usually makes both left and right residuals for the computed inverse of a matrix small.     

拟阵与概念格的关系

本文以构造的方式建立起拟阵与概念格的联系,得到在同构意义下每个拟阵是一个概念格,但反之不然的结论;该结论使得利用概念格的性质研究拟阵成为现实,特别为将建造概念格的算法尤其是已计算机化的算法应用于求取拟阵奠定了基础,也为拟阵论成为研究概念格性质的辅助工具打下基础．     

Mod 2 cohomology of combinatorial Grassmannians

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.     

Parallel arc-allocation algorithms for optimizing generalized networks

Two parallel shared-memory algorithms are presented for the optimization of generalized networks. These algorithms are based on the allocation of arc-related operations in the (generalized) network simplex method. One method takes advantage of the multi-tree structure of basic solutions and performs pivot operations in parallel, utilizing locking to ensure correctness. The other algorithm utilizes only one processor for sequential pivoting, but parallelizes the pricing operation and overlaps this task with pivoting in a speculative manner (i.e. since pivoting and pricing involve data dependencies, a candidate for flow change generated by the pricing processors is not guaranteed to be acceptable, but in practice generally has this property). The relative performance of these two methods (on the Sequent Symmetry S81 multiprocessor) is compared and contrasted with that of a fast sequential algorithm on a set of large-scale test problems of up to 1,000,000 arcs.This research was supported in part by NSF grant CCR-8709952 and AFOSR grant AFOSR-86-0194.     

任意基数集上的拟阵的圈及连通性

通过研究任意基数集上的拟阵圈的性质,继而得出当此拟阵连通时,它可由含任一给定元素的圈集唯一确定的结论.     

准模糊图拟阵基图的最大权基与字典序最大的基

模糊拟阵的基图是模糊拟阵的基本概念.在准模糊图拟阵的基础上,给出了准模糊图拟阵基图的最大权基与字典序最大的基的性质,这将有利于模糊拟阵从基础研究逐渐转向应用研究.     

Topological cycle matroids of infinite graphs

We prove that the topological cycles of an arbitrary infinite graph together with its topological ends form a matroid. This matroid is, in general, neither finitary nor cofinitary.     

Basis-Transitive Matroids

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.     

拟阵的可去圈

本首先用拟阵语言将图论的新概念定义成了拟阵的新概念，然后用拟阵语言将Goddyn和Heuevl所得的图论上的新结果平移成了拟阵的新结果，最后用拟阵的方法对它们给出了新的证明。     

Oriented matroid structures from realized root systems

Journal of Algebraic Combinatorics - This paper investigates the question of uniqueness of the reduced oriented matroid structure arising from root systems of a Coxeter system in real vector...