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.     

Random sampling and greedy sparsification for matroid optimization problems

Random sampling is a powerful tool for gathering information about a group by considering only a small part of it. We discuss some broadly applicable paradigms for using random sampling in combinatorial optimization, and demonstrate the effectiveness of these paradigms for two optimization problems on matroids: finding an optimum matroid basis and packing disjoint matroid bases. Application of these ideas to the graphic matroid led to fast algorithms for minimum spanning trees and minimum cuts. An optimum matroid basis is typically found by agreedy algorithm that grows an independent set into an optimum basis one element at a time. This continuous change in the independent set can make it hard to perform the independence tests needed by the greedy algorithm. We simplify matters by using sampling to reduce the problem of finding an optimum matroid basis to the problem of verifying that a givenfixed basis is optimum, showing that the two problems can be solved in roughly the same time. Another application of sampling is to packing matroid bases, also known as matroid partitioning. Sampling reduces the number of bases that must be packed. We combine sampling with a greedy packing strategy that reduces the size of the matroid. Together, these techniques give accelerated packing algorithms. We give particular attention to the problem of packing spanning trees in graphs, which has applications in network reliability analysis. Our results can be seen as generalizing certain results from random graph theory. The techniques have also been effective for other packing problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Some of this work done at Stanford University, supported by National Science Foundation and Hertz Foundation Graduate Fellowships, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation and Xerox Corporation. Also supported by NSF award 962-4239.     

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.     

Ideal secret sharing schemes whose minimal qualified subsets have at most three participants

One of the main open problems in secret sharing is the characterization of the access structures of ideal secret sharing schemes. Brickell and Davenport proved that every one of these ideal access structures is related in a certain way to a unique matroid. Specifically, they are matroid ports. In addition to the search of general results, this difficult open problem has been studied in previous works for several families of access structures. In this paper we do the same for access structures with rank 3, that is, structures whose minimal qualified subsets have at most three participants. We completely characterize and classify the rank-3 access structures that are matroid ports. We prove that all access structures with rank three that are ports of matroids greater than 3 are ideal. After the results in this paper, the only open problem in the characterization of the ideal access structures with rank three is to characterize the rank-3 matroids that can be represented by an ideal secret sharing scheme. A previous version of this paper appeared in Fifth Conference on Security and Cryptography for Networks, SCN 2006, Lecture Notes in Computer Science 4116 (2006) 201–215.     

A matroid-friendly basis for the quasisymmetric functions

A new Z-basis for the space of quasisymmetric functions (QSym, for short) is presented. It is shown to have nonnegative structure constants, and several interesting properties relative to the quasisymmetric functions associated to matroids by the Hopf algebra morphism F of Billera, Jia, and Reiner [L.J. Billera, N. Jia, V. Reiner, A quasisymmetric function for matroids, arXiv:math.CO/0606646]. In particular, for loopless matroids, this basis reflects the grading by matroid rank, as well as by the size of the ground set. It is shown that the morphism F distinguishes isomorphism classes of rank two matroids, and that decomposability of the quasisymmetric function of a rank two matroid mirrors the decomposability of its base polytope. An affirmative answer to the Hilbert basis question raised in [L.J. Billera, N. Jia, V. Reiner, A quasisymmetric function for matroids, arXiv:math.CO/0606646] is given.     

Equivalence-free exhaustive generation of matroid representations

In this paper we present an algorithm for the problem of exhaustive equivalence-free generation of 3-connected matroids which are represented by a matrix over some finite (partial) field, and which contain a given minor. The nature of this problem is exponential, and it appears to be much harder than, say, isomorph-free generation of graphs. Still, our algorithm is very suitable for practical use, and it has been successfully implemented in our matroid computing package MACEK [http://www.mcs.vuw.ac.nz/research/macek, 2001-05].     

On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids

We introduce the active partition of the ground set of an oriented matroid perspective (or morphism, or quotient, or strong map) on a linearly ordered ground set. The reorientations obtained by arbitrarily reorienting parts of the active partition share the same active partition. This yields an equivalence relation for the set of reorientations of an oriented matroid perspective, whose classes are enumerated by coefficients of the Tutte polynomial, and a remarkable partition of the set of reorientations into Boolean lattices, from which we get a short direct proof of a 4-variable expansion formula for the Tutte polynomial in terms of orientation activities. This formula was given in the last unpublished preprint by Michel Las Vergnas; the above equivalence relation and notion of active partition generalize a former construction in oriented matroids by Michel Las Vergnas and the author; and the possibility of such a proof technique in perspectives was announced in the aforementioned preprint. We also briefly highlight how the 5-variable expansion of the Tutte polynomial in terms of subset activities in matroid perspectives comes in a similar way from the known partition of the power set of the ground set into Boolean lattices related to subset activities (and we complete the proof with a property which was missing in the literature). In particular, the paper applies to matroids and oriented matroids on a linearly ordered ground set, and applies to graph and directed graph homomorphisms on a linearly ordered edge-set.     

A matroid operation that commutes with duality

In this note, we propose an operation for matroids that commutes with duality having deletions and contractions as extremal cases. Crapo and Schmitt's free product of matroids is one of its consequences. A special case of this operation can be used as an inductive tool because it reduces the number of elements of a matroid by two and it is invariant by duality.     

Primitive elements in the matroid-minor Hopf algebra

We introduce the matroid-minor coalgebra C, which has labeled matroids as distinguished basis and coproduct given by splitting a matroid into a submatroid and complementary contraction in all possible ways. We introduce two new bases for C; the first of these is related to the distinguished basis by Möbius inversion over the rank-preserving weak order on matroids, the second by Möbius inversion over the suborder excluding matroids that are irreducible with respect to the free product operation. We show that the subset of each of these bases corresponding to the set of irreducible matroids is a basis for the subspace of primitive elements of C. Projecting C onto the matroid-minor Hopf algebra H, we obtain bases for the subspace of primitive elements of H.     

On the intersection of infinite matroids

We show that the infinite matroid intersection conjecture of Nash-Williams implies the infinite Menger theorem proved by Aharoni and Berger in 2009.We prove that this conjecture is true whenever one matroid is nearly finitary and the second is the dual of a nearly finitary matroid, where the nearly finitary matroids form a superclass of the finitary matroids.In particular, this proves the infinite matroid intersection conjecture for finite-cycle matroids of 2-connected, locally finite graphs with only a finite number of vertex-disjoint rays.     

The 3-connected matroids with circumference 6

We construct all 3-connected matroids with circumference equal to 6 having rank at least 8. A matroid belongs to this family if and only if it is a generalized parallel connection of a set of planes along a common line (which may have some virtual points).     

Matroid matching in pseudomodular lattices

The matroid matching problem (also known as matroid parity problem) has been intensively studied by several authors. Starting from very special problems, in particular the matching problem and the matroid intersection problem, good characterizations have been obtained for more and more general classes of matroids. The two most recent ones are the class of representable matroids and, later on, the class of algebraic matroids (cf. [4] and [2]). We present a further step of generalization, showing that a good characterization can also be obtained for the class of socalled pseudomodular matroids, introduced by Björner and Lovász (cf. [1]). A small counterexample is included to show that pseudomodularity still does not cover all matroids that behave well with respect to matroid matching.Supported by the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).     

Greedy algorithm and symmetric matroids

Symmetric matroids are set systems which are obtained, in some sense, by a weakening of the structure of a matroid. These set systems are characterized by a greedy algorithm and they are suitable for dealing with autodual properties of matroids. Applications are given to the eulerian tours of 4-regular graphs and the theory ofg-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 .     

Matroids with a unique non-common circuit containing a fixed element

In this paper, we define a matroid operation that generalizes the circuit-hyperplane relaxation. This operation is used to characterize when a pair of connected matroids over the same ground set have exactly one non-common circuit containing a fixed element.     

Matroid representation of clique complexes

In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted clique problem” since a greedy algorithm is a k-approximation algorithm for this problem. For any k>0, we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be n-1. Other related investigations are also given.     

Four matroidal structures of covering and their relationships with rough sets

Covering is a common form of data representation, and covering-based rough sets serve as an efficient technique to process this type of data. However, many important problems such as covering reduction in covering-based rough sets are NP-hard so that most algorithms to solve them are greedy. Matroids provide well-established platforms for greedy algorithm foundation and implementation. Therefore, it is necessary to integrate covering-based rough set with matroid. In this paper, we propose four matroidal structures of coverings and establish their relationships with rough sets. First, four different viewpoints are presented to construct these four matroidal structures of coverings, including 1-rank matroids, bigraphs, upper approximation numbers and transversals. The respective advantages of these four matroidal structures to rough sets are explored. Second, the connections among these four matroidal structures are studied. It is interesting to find that they coincide with each other. Third, a converse view is provided to induce a covering by a matroid. We study the relationship between this induction and the one from a covering to a matroid. Finally, some important concepts of covering-based rough sets, such as approximation operators, are equivalently formulated by these matroidal structures. These interesting results demonstrate the potential to combine covering-based rough sets with matroids.     

Systems of Polynomials for Detecting Orientable Matroids

We study systems of polynomial equations that correspond to a matroid M. Each of these systems has a zero solution if and only if M is orientable. Since determining if a matroid is orientable is NP-complete with respect to the size of the input data, determining if these systems have solutions is also NP-complete. However, we show that one of the associated polynomial systems corresponding to M is linear if M is a binary matroid and thus it may be determined if binary matroids are orientable in polynomial time given the circuits and cocircuits of said matroid as the input. In the case when M is not binary, we consider the associated system of non-linear polynomials. In this case Hilbertʼs Nullstellensatz gives us that M is non-orientable if and only if a certain certificate to the given polynomials system exists. We wish to place bounds on the degree of these certificates in future research.     

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

Matroids and Graphs with Few Non-Essential Elements

An essential element of a 3-connected matroid M is one for which neither the deletion nor the contraction is 3-connected. Tutte's Wheels and Whirls Theorem proves that the only 3-connected matroids in which every element is essential are the wheels and whirls. In an earlier paper, the authors showed that a 3-connected matroid with at least one non-essential element has at least two such elements. This paper completely determines all 3-connected matroids with exactly two non-essential elements. Furthermore, it is proved that every 3-connected matroid M for which no single-element contraction is 3-connected can be constructed from a similar such matroid whose rank equals the rank in M of the set of elements e for which the deletion M\e is 3-connected.