Infinite matroids in graphs

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.     

Quasi‐graphic matroids*

Frame matroids and lifted‐graphic matroids are two interesting generalizations of graphic matroids. Here, we introduce a new generalization, quasi‐graphic matroids, that unifies these two existing classes. Unlike frame matroids and lifted‐graphic matroids, it is easy to certify that a 3‐connected matroid is quasi‐graphic. The main result is that every 3‐connected representable quasi‐graphic matroid is either a lifted‐graphic matroid or a frame matroid.     

Oriented matroids

In this paper, the basic properties of oriented matroids are examined. A topological representation theorem for oriented matroids is proven, utilizing the notion of an “arrangement of pseudo-hemispheres”. The duality theorem of linear programming is extended to oriented matroids.     

A characterization of orthogonal duality in matroid theory

An operation on matroids is a function defined from the collection of all matroids on finite sets to itself which preserves isomorphism of matroids and sends a matroid on a set S to a matroid on the same set S. We show that orthogonal duality is the only non-trivial operation on matroids which interchanges contraction and deletion.     

On the matroids in which all hyperplanes are binary

In this paper, it is shown that, for a minor-closed class of matroids, the class of matroids in which every hyperplane is in is itself minor-closed and has, as its excluded minors, the matroids U_1.1 N such that N is an excluded minor for . This result is applied to the class of matroids of the title, and several alternative characterizations of the last class are given.     

Unions of oriented matroids

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.     

A general model for matroids and the greedy algorithm

We present a general model for set systems to be independence families with respect to set families which determine classes of proper weight functions on a ground set. Within this model, matroids arise from a natural subclass and can be characterized by the optimality of the greedy algorithm. This model includes and extends many of the models for generalized matroid-type greedy algorithms proposed in the literature and, in particular, integral polymatroids. We discuss the relationship between these general matroids and classical matroids and provide a Dilworth embedding that allows us to represent matroids with underlying partial order structures within classical matroids. Whether a similar representation is possible for matroids on convex geometries is an open question. S. Fujishige’s research was supported by a Grant-in-Aid for Scientific Research of the Ministry of Education, Culture, Sports, Science and Technology of Japan.     

Signed graphs

A signed graph is a graph with a sign attached to each arc. This article introduces the matroids of signed graphs, which generalize both the polygon matroids and the even-circle (or unoriented cycle) matroids of ordinary graphs. The concepts of balance, switching, restriction and contraction, double covering graphs, and linear representation of signed graphs are treated in terms of the matroid, and a matrix-tree theorem for signed graphs is proved. The examples treated include the all-positive and all-negative graphs (whose matroids are the polygon and even-circle matroids), sign-symmetric graphs (related to the classical root systems), and signed complete graphs (equivalent to two-graphs).Replacing the sign group by an arbitrary group leads to voltage graphs. Most of our results on signed graphs extend to all voltage graphs.     

The signed-graphic representations of wheels and whirls

We characterize all of the ways to represent the wheel matroids and whirl matroids using frame matroids of signed graphs. The characterization of wheels is in terms of topological duality in the projective plane and the characterization of whirls is in terms of topological duality in the annulus.     

Cubes and orientability

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.     

Infinite Matroidal Version of Hall's Matching Theorem

Hall's theorem for bipartite graphs gives a necessary and sufficientcondition for the existence of a matching in a given bipartitegraph. Aharoni and Ziv have generalized the notion of matchabilityto a pair of possibly infinite matroids on the same set andgiven a condition that is sufficient for the matchability ofa given pair (M, W) of finitary matroids, where the matroidM is SCF (a sum of countably many matroids of finite rank).The condition of Aharoni and Ziv is not necessary for matchability.The paper gives a condition that is necessary for the existenceof a matching for any pair of matroids (not necessarily finitary)and is sufficient for any pair (M, W) of finitary matroids,where the matroid M is SCF.     

Regular matroids with every circuit basis fundamental

Hartvigsen and Zemel have obtained a characterization of those graphs which have every circuit basis fundamental. We consider the corresponding problem for binary matroids. We show that, in general, the class of binary matroids for which every circuit basis is fundamental is not closed under the taking of minors. However, this class is closed under the taking of series-minors. We also describe some general properties of this class of matroids. We end by extending Hartvigsen and Zemel's result to the class of regular matroids, thus obtaining a set of excluded minors which are graphic for this class. © 1996 John Wiley & Sons, Inc.     

Oriented matroids from smooth manifolds

Results of Folkman and Lawrence and Mandel on representations of oriented matroids by topological spheres are used to prove a method of constructing oriented matroids from intersections of smooth topological hyperplanes. A class of such constructions is given corresponding to non real-representable matroids of rank ϱ on 2ϱ + 1 elements, ϱ ≥ 4.     

拟阵上合作对策的Banzhaf函数

本文结合文[1,2]中关于拟阵上静态结构和动态结构合作对策Shapley函数的描述,探讨了两类拟阵上的Banzhaf函数.通过给出相应的公理体系,论述了两类拟阵上Banzhaf函数的存在性和唯一性,拓展了拟阵上分配指标的研究范围.同时讨论了两类合作对策上Banzhaf函数的有关性质.最后通过算例来说明局中人在此类合作对策中的Banzhaf指标.     

Orientable arithmetic matroids

The theory of matroids has been generalized to oriented matroids and, recently, to arithmetic matroids. We want to give a definition of “oriented arithmetic matroid” and prove some properties like the “uniqueness of orientation”.     

A decomposition theory for matroids. I. General results

A new matroid decomposition with several attractive properties leads to a new theorem of alternatives for matroids. A strengthened version of this theorem for binary matroids says roughly that to any binary matroid at least one of the following statements must apply: (1) the matroid is decomposable, (2) several elements can be removed (in any order) without destroying 3-connectivity, (3) the matroid belongs to one of 2 well-specified classes or has 10 elements or less. The latter theorem is easily specialized to graphic matroids. These theorems seem particularly useful for the determination of minimal violation matroids, a subject discussed in part II.     

Kuratowski's and Wagner's theorems for matroids

In an earlier paper we proved the following theorem, which provides a strengthening of Tutte's well-known characterization of regular (totally unimodular) matroids: A binary matroid is regular if it does not have the Fano matroid or its dual as a series-minor (parallel-minor). In this paper we prove two theorems (Theorems 5.1 and 6.1) which provide the same kind of strengthening for Tutte's characterization of the graphic matroids (i.e., bond-matroids). One interesting aspect of these theorems is the introduction of the matroids of “type R”. It turns out that these matroids are, in at least two different senses, the smallest regular matroids which are neither graphic nor cographic (Theorems 6.2 and 6.3).     

Orientability of matroids

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.     

What is a complex matroid?

Following an “ansatz” of Björner and Ziegler [BZ], we give an axiomatic development of finite sign vector systems that we callcomplex matroids. This includes, as special cases, the sign vector systems that encode complex arrangements according to [BZ], and the complexified oriented matroids, whose complements were considered by Gel'fand and Rybnikov [GeR]. Our framework makes it possible to study complex hyperplane arrangements as entirely combinatorial objects. By comparing complex matroids with 2-matroids, which model the more general 2-arrangements introduced by Goresky and MacPherson [GoM], the essential combinatorial meaning of a “complex structure” can be isolated. Our development features a topological representation theorem for 2-matroids and complex matroids, and the computation of the cohomology of the complement of a 2-arrangement, including its multiplicative structure in the complex case. Duality is established in the cases of complexified oriented matroids, and for realizable complex matroids. Complexified oriented matroids are shown to be matroids with coefficients in the sense of Dress and Wenzel [D1], [DW1], but this fails in general.