Strongly inequivalent representations and Tutte polynomials of matroids

We develop constructive techniques to show that non-isomorphic 3-connected matroids that are representable over a fixed finite field and that have the same Tutte polynomial abound. In particular, for most prime powers q, we construct infinite families of sets of 3-connected matroids for which the matroids in a given set are non-isomorphic, are representable over GF(q), and have the same Tutte polynomial. Furthermore, the cardinalities of the sets of matroids in a given family grow exponentially as a function of rank, and there are many such families.In Memory of Gian-Carlo Rota     

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.     

A unique factorization theorem for matroids

We study the combinatorial, algebraic and geometric properties of the free product operation on matroids. After giving cryptomorphic definitions of free product in terms of independent sets, bases, circuits, closure, flats and rank function, we show that free product, which is a noncommutative operation, is associative and respects matroid duality. The free product of matroids M and N is maximal with respect to the weak order among matroids having M as a submatroid, with complementary contraction equal to N. Any minor of the free product of M and N is a free product of a repeated truncation of the corresponding minor of M with a repeated Higgs lift of the corresponding minor of N. We characterize, in terms of their cyclic flats, matroids that are irreducible with respect to free product, and prove that the factorization of a matroid into a free product of irreducibles is unique up to isomorphism. We use these results to determine, for K a field of characteristic zero, the structure of the minor coalgebra of a family of matroids that is closed under formation of minors and free products: namely, is cofree, cogenerated by the set of irreducible matroids belonging to .     

Oriented matroid systems

The domination invariant has played an important part in reliability theory. While most of the work in this field has been restricted to various types of network system models, many of the results can be generalized to much wider families of systems associated with matroids. Previous papers have explored the relation between undirected network systems and matroids. In this paper the main focus is on directed network systems and their relation to oriented matroids. An oriented matroid is a special type of matroid where the circuits are signed sets. Using these signed sets one can e.g., obtain a set theoretic representation of the direction of the edges of a directed network system. Classical results for directed network systems include the fact that the signed domination is either +1 or −1 if the network is acyclic, and zero otherwise. It turns out that these results can be generalized to systems derived from oriented matroids. Several classes of systems for which the generalized results hold will be discussed. These include oriented versions of k-out-of-n systems and a certain class of systems associated with matrices.     

Circuit Admissible Triangulations of Oriented Matroids

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.     

On the Circuit-cocircuit Intersection Conjecture

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).     

Matroidal approaches to rough sets via closure operators

This paper studies rough sets from the operator-oriented view by matroidal approaches. We firstly investigate some kinds of closure operators and conclude that the Pawlak upper approximation operator is just a topological and matroidal closure operator. Then we characterize the Pawlak upper approximation operator in terms of the closure operator in Pawlak matroids, which are first defined in this paper, and are generalized to fundamental matroids when partitions are generalized to coverings. A new covering-based rough set model is then proposed based on fundamental matroids and properties of this model are studied. Lastly, we refer to the abstract approximation space, whose original definition is modified to get a one-to-one correspondence between closure systems (operators) and concrete models of abstract approximation spaces. We finally examine the relations of four kinds of abstract approximation spaces, which correspond exactly to the relations of closure systems.     

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.     

Matroid Enumeration for Incidence Geometry

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 ℝ³ and that of Motzkin on ≤12 lines in ℝ², 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.     

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.     

Excluding a bipartite circle graph from line graphs

We prove that, for a fixed bipartite circle graph H, all line graphs with sufficiently large rank‐width (or clique‐width) must have a pivot‐minor isomorphic to H. To prove this, we introduce graphic delta‐matroids. Graphic delta‐matroids are minors of delta‐matroids of line graphs and they generalize graphic and cographic matroids. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 183–203, 2009     

On fixing elements in matroid minors

LetF be a collection of 3-connected matroids which is (3, 1)-rounded, that is, whenever a 3-connected matroidM has a minor in F ande is an element ofM, thenM has a minor in F whose ground set contains.e. The aim of this note is to prove that, for all sufficiently largen, the collection ofn-element 3-connected matroids having some minor inF is also (3, 1)-rounded.This research was partially supported by the National Science Foundation under Grant No. DMS-8500494.     

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.     

基于覆盖上近似算子的拟阵结构及其关系

Covering-based rough sets,as a technique of granular computing,can be a useful tool for dealing with inexact,uncertain or vague knowledge in information systems.Matroids generalize linear independence in vector spaces,graph theory and provide well established platforms for greedy algorithm design.In this paper,we construct three types of matroidal structures of covering-based rough sets.Moreover,through these three types of matroids,we study the relationships among these matroids induced by six types of covering-based upper approximation operators.First,we construct three families of sets by indiscernible neighborhoods,neighborhoods and close friends,respectively.Moreover,we prove that they satisfy independent set axioms of matroids.In this way,three types of matroidal structures of covering-based rough sets are constructed.Secondly,we study some characteristics of the three types of matroid,such as dependent sets,circuits,rank function and closure.Finally,by comparing independent sets,we study relationships among these matroids induced by six types of covering-based upper approximation operators.     

Realization of abstract convex geometries by point configurations

The Edelman–Jamison problem is to characterize those abstract convex geometries that are representable by a set of points in the plane. We show that some natural modification of the Edelman–Jamison problem is equivalent to the well known NP-hard order type problem. The relation to the realizability of oriented matroids is clarified.     

Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems

Min-max problems on matroids are NP-hard for a wide variety of matroids. However, greedy type algorithms have data independent worst case performance guarantees, andn-enumerative algorithms yield-optimal solutions ifn is sufficiently close to the rank of the underlying matroid. Data dependent performance guarantees can be obtained for max-min problems over matroids.This research was partially supported by NSERC Grant A5543.     

Injection geometries

In this paper a new concept, injection geometries, is considered. This provides a common generalization of matroids and permutation geometries. Different systems of axioms and various examples are given. Theorem 5.1 provides an extremal set theoretic characterization of injection designs.     

Symplectic Matroids

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.     

拟阵上模糊合作对策的Banzhaf函数

首先通过对清晰拟阵定义的拓展,给出了模糊拟阵的概念。通过定义具有多线性扩展形式的模糊合作对策在静态结构和动态结构拟阵上B anzhaf函数的公理体系,分别探讨了此类模糊合作对策在这两种拟阵上关于B anzhaf函数的存在性和唯一性。同时,通过定义具有Choquet积分形式模糊合作对策在静态结构和动态结构拟阵上B anzhaf函数的公理体系,分别探讨了此类模糊合作对策在这两种拟阵上关于B anzhaf函数的存在性和唯一性。