A note on nongraphic matroids

Tutte found an excluded minor characterization of graphic matroids with five excluded minors. A variation on Tutte's result is presented here. Let {e, f, g} be a circuit of a 3-connected nongraphic matroid M. Then M has a minor using e, f, g isomorphic to either the 4-point line, the Fano matroid, or the bond matroid of K_3,3.     

A note on some algorithms for matroids

We use results on the optimal basis of a matroid to modify two algorithms, one which finds the circuits of a matroid from the bases, and one which finds the bases from the cocircuits.     

A note on binary fundamental transversal matroids

A fundamental transversal matroid (f.t.m.) is a transversal matroid which arises from the family of cocircuits with respect to a cobase. A characterization of binary f.t.m.'s is given in the form of excluded minor type. It is also shown that a binary f.t.m. is a special sort of series-parallel graphs.     

A note on submodular set cover on matroids

We consider a problem related to the submodular set cover on polymatroids, when the ground set is the family of independent sets of a matroid. The achievement here is getting a strongly polynomial running time with respect to the ground set of the matroid even though the family of independent sets has exponential size. We also address the optimization problem of the maximization of submodular set functions on the independent sets of a matroid.     

A note on clone sets in representable matroids

We investigate the size of clone sets in representable matroids.     

A composition for matroids

The composition of a quotient matroid Q over a collection of component matroids f₁, …, f_n indexed on the cells of Q, is described. This composition, called quotient composition, may be viewed as an application of clutter composition to matroids, or as a generalization of matroid direct sum composition to the next higher connectivity. It may also be viewed as equivalent to compositions described by Minty in 1966, and Brylawski in 1971.Quotient composition is characterized, and the circuits and rank function of a composed matroid are given. Various other properties are described, along with a category for quotient composition.     

A decomposition theory for matroids. II. Minimal violation matroids

Two decomposition theorems of Part I are utilized to characterize minimal violation matroids of matroid properties that possess certain composition and extension properties. Graphicness, planarity, and regularity have all or almost all of the desired composition and extension properties, and rather simple arguments produce the well-known minimal violation matroids.     

Security games on matroids

Two players, the Defender and the Attacker play the following game. A matroid \(M=(S,\mathcal {I})\), a weight function \(d:S\rightarrow \mathbb {R}^+\) and a cost function \(c:S\rightarrow \mathbb {R}\) are given. The Defender chooses a base B of the matroid M and the Attacker chooses an element \(s\in S\) of the ground set. In all cases, the Attacker pays the Defender the cost of attack c(s). Besides that, if \(s\in B\) then the Defender pays the Attacker the amount d(s); if, on the other hand, \(s\notin B\) then there is no further payoff. Special cases of this two-player, zero-sum game were considered and solved in various security-related applications. In this paper we show that it is also possible to compute Nash-equilibrium mixed strategies for both players in strongly polynomial time in the above general matroid setting. We also consider a further generalization where common bases of two matroids are chosen by the Defender and apply this to define and efficiently compute a new reliability metric on digraphs.     

A geometric characterization of Coxeter matroids

Coxeter matroids, introduced by Gelfand and Serganova, are combinatorial structures associated with any finite Coxeter group and its parabolic subgroup they include ordinary matroids as a specia case. A basic result in the subject is a geometric characterization of Coxeter matroids first stated by Gelfand and Serganova. This paper presents a self-contained, simple proof of a more general version of this geometric characterization.     

A new characterization of graphic matroids

We give a necessary and sufficient condition for a binary matroid to be graphic. The condition is very natural, but, unlike other similar results, it gives a trivial algorithm for testing graphicness.     

A maximum-rank minimum-term-rank theorem for matroids

M. Iri has proved that the maximum rank for a pivotal system of matrices (i.e., combivalence class) equals the minimum term rank. Here this and some of Iri's related results are generalized to matroids. These generalizations are presented using a representation of matroids with (0,1)-matrices. Then, with the aid of matroid basis graphs, these generalizations are restated graph-theoretically. Finally, related results about certain uniform basis graphs are derived.     

A MacWilliams type identity for matroids

In this paper, we consider the coboundary polynomial for a matroid as a generalization of the weight enumerator of a linear code. By describing properties of this polynomial and of a more general polynomial, we investigate the matroid analogue of the MacWilliams identity. From coding-theoretical approaches, upper bounds are given on the size of circuits and cocircuits of a matroid, which generalizes bounds on minimum Hamming weights of linear codes due to I. Duursma.     

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 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 problem of P. Seymour on nonbinary matroids

The following statement fork=1, 2, 3 has been proved by Tutte [4], Bixby [1] and Seymour [3] respectively: IfM is ak-connected non-binary matroid andX a set ofk-1 elements ofM, thenX is contained in someU ₄ ² minor ofM. Seymour [3] asks whether this statement remains true fork=4; the purpose of this note is to show that it does not and to suggest some possible alternatives. Supported in part by the National Science Foundation     

Biased graphs whose matroids are special binary matroids

Abiased graph is a graph together with a class of polygons such that no theta subgraph contains exactly two members of the class. To a biased graph are naturally associated three edge matroids:G(), L(), L ₀ (). We determine all biased graphs for which any of these matroids is isomorphic to the Fano plane, the polygon matroid ofK ₄,K ₅ orK _3,3, any of their duals, Bixby's regular matroidR ₁₀, or the polygon matroid ofK _m form > 5. In each case the bias is derived from edge signs. We conclude by finding the biased graphs for whichL ₀ () is not a graphic [or, regular matroid but every proper contraction is.Research supported by National Science Foundation grant DMS-8407102 and SGPNR grant 85Z0701Visiting Research Fellow, 1984–1985     

Note on binary simplicial matroids

Using an earlier characterization of simplicial hypergraphs we obtain a characterization of binary simplicial matroids in terms of the existence of a special base.     

Unipancyclic matroids

Analogous to the concept of uniquely pancyclic graphs, we define a uniquely pancyclic (UPC) matroid of rank $r$ to be a (simple) rank-$r$ matroid containing exactly one circuit of each length $?$ for $3\le ?\le r+1$. 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 $2$.     

A constrained independent set problem for matroids

In this note, we study a constrained independent set problem for matroids. The problem can be regarded as an ordered version of the matroid parity problem. By a reduction of this problem to matroid intersection, we prove a min-max formula. We show how earlier results of Hefner and Kleinschmidt on the so-called MS-matchings fit in our framework.