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.     

A combinatorial abstraction of linear programming

In the context of oriented matroids we establish and elaborate upon an abstraction of linear programming duality foreseen by Rockafellar in his work on elementary vectors. We describe a pivoting operation for oriented matroids and a finite pivoting method, which elucidate the combinatorial nature of Dantzig's simplex method. The pivoting method specializes, when the oriented matroids arise from real vector spaces, to the simplex method with a new pivot selection rule. A very simple pivot selection rule for which finiteness has been established in the linear programming context, but not in the broader setting of oriented matroids, is also described.     

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.     

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.     

A unified interpretation of several combinatorial dualities

Several combinatorial structures exhibit a duality relation that yields interesting theorems, and, sometimes, useful explanations or interpretations of results that do not concern duality explicitly. We present a common characterization of the duality relations associated with matroids, clutters (Sperner families), oriented matroids, and weakly oriented matroids. The same conditions characterize the orthogonality relation on certain families of vector spaces. This leads to a notion of abstract duality.     

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.     

Thin sums matroids and duality

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.     

Recharacterizing Eulerian: Intimations of new duality

Eulerian graphs are shown to be characterized by being connected with each edge in an odd number of circuits, as compared with the traditional characterization having each cutset contain an even number of edges. This result is proved in the general context of binary matroids, and the intriguing sort of duality present is analyzed using syntactical duality principles.     

Linear and quadratic programming in oriented matroids

We prove constructively duality theorems of linear and quadratic programming in the combinatorial setting of oriented matroids. One version of our algorithm for linear programing has the interesting feature of maintaining feasibility. The development of the quadratic programming duality result suggests the study of properties of square matrices such as symmetry and positive semi-definiteness in the context of oriented matroids.     

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 .     

Combinatorial characterizations of K-matrices

e present a number of combinatorial characterizations of K-matrices. This extends a theorem of Fiedler and Pták on linear-algebraic characterizations of K-matrices to the setting of oriented matroids. Our proof is elementary and simplifies the original proof substantially by exploiting the duality of oriented matroids. As an application, we show that any simple principal pivot method applied to the linear complementarity problems with K-matrices converges very quickly, by a purely combinatorial argument.     

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.     

Latroids and their representation by codes over modules

It has been known for some time that there is a connection between linear codes over fields and matroids represented over fields. In fact a generator matrix for a linear code over a field is also a representation of a matroid over that field. There are intimately related operations of deletion, contraction, minors and duality on both the code and the matroid. The weight enumerator of the code is an evaluation of the Tutte polynomial of the matroid, and a standard identity relating the Tutte polynomials of dual matroids gives rise to a MacWilliams identity relating the weight enumerators of dual codes. More recently, codes over rings and modules have been considered, and MacWilliams type identities have been found in certain cases.

In this paper we consider codes over rings and modules with code duality based on a Morita duality of categories of modules. To these we associate latroids, defined here. We generalize notions of deletion, contraction, minors and duality, on both codes and latroids, and examine all natural relations among these.

We define generating functions associated with codes and latroids, and prove identities relating them, generalizing above-mentioned generating functions and identities.

     

Gammoids and transversal matroids

The two main results of this paper identify the “strict gammoids” of Mason [7] with duals of transvesal matroids, and gammoids in general with contractions of transversal matroids. Both theorems derive from a fundamental construction which we also use, inter alia, to establish a duality between the graph theorems of Menger and König.     

Some matroids related to sum-rank metric codes

We introduce the notion of sum-matroids and show its association with sum-rank metric codes. As a consequence, some results for sum-rank metric codes by Martínez-Peñas are generalized for sum-matroids. The sum-matroids generalize the notions of matroids and q-matroids. We define the generalized weights for sum-matroids and prove a Wei-type duality theorem which generalizes the analogous cases for matroids and q-matroids.     

On Brylawski’s Generalized Duality

We introduce a notion of duality??due to Brylawski??that generalizes matroid duality to arbitrary rank functions. This allows us to define a generalization of the matroid Tutte polynomial. This polynomial satisfies a deletion-contraction recursion, where deletion and contraction are defined in this more general setting. We explore this notion of duality for greedoids, antimatroids and demi-matroids, proving that matroids correspond precisely to objects that are simultaneously greedoids and ??dual?? greedoids.     

Skew partial fields,multilinear representations of matroids,and a matrix tree theorem

We extend the notion of representation of a matroid to algebraic structures that we call skew partial fields. Our definition of such representations extends Tutte?s definition, using chain groups. We show how such representations behave under duality and minors, we extend Tutte?s representability criterion to this new class, and we study the generator matrices of the chain groups. An example shows that the class of matroids representable over a skew partial field properly contains the class of matroids representable over a skew field. Next, we show that every multilinear representation of a matroid can be seen as a representation over a skew partial field. Finally we study a class of matroids called quaternionic unimodular. We prove a generalization of the matrix tree theorem for this class.     

Abstract Separation Systems

Abstract separation systems provide a simple general framework in which both tree-shape and high cohesion of many combinatorial structures can be expressed, and their duality proved. Applications range from tangle-type duality and tree structure theorems in graphs, matroids or CW-complexes to, potentially, image segmentation and cluster analysis. This paper is intended as a concise common reference for the basic definitions and facts about abstract separation systems in these and any future papers using this framework.     

Axioms for infinite matroids

We give axiomatic foundations for infinite matroids with duality, in terms of independent sets, bases, circuits, closure and rank. Continuing work of Higgs and Oxley, this completes the solution to a problem of Rado of 1966.     

Splitting Off Operation for Binary Matroids and its Applications

In this paper, we generalize the splitting off operation on graphs to binary matroids and investigate the relations between the matroids resulting from this operation and the original binary matroids in terms of representation matrices, bases, rank functions and connectivity. We also provide some interesting applications of this operation.