Matroids

Problems in this category

• Aharoni-Berger conjecture
• Binary matroid representation of cyclic families
• Tidbits/Bonn, matroids, and Farkas’ Lemma
• Bounded degree matroid basis
• Cyclic orderings of matroids
• Destroying rigidity
• Edge-covering number of 2-polymatroids
• Equitability of matroids
• Expressing vectors using bases of a matroid
• List colouring of two matroids
• Maximum weight k-element subsets of perfect matchings
• Partition median problem
• Rainbow matchings in bipartite graphs
• Rota's conjecture on disjoint bases
• Scrambled Rota conjecture
• Serial symmetric exchanges
• Small representations of gammoids
• Strong colouring of matroid-graph pairs
• Upper bound on common independent set cover

Introduction

We present some open questions about the global properties of bases and circuits of general (not necessarily representable) matroids. There are other areas of matroid theory not addressed here where exciting open questions arise: some of the most interesting current research is on representable matroids and excluded minors, see the survey of Geelen, Gerards and Whittle . A groundbreaking new result is their proof of Rota's conjecture on excluded minors for representability.

Girth and co-girth

Computing the girth (minimum length cycle) of a graph is easy using BFS, and computing the co-girth (minimum size cut) can also be done in polynomial time, e.g. by flows or the maximum adjacency ordering algorithm of Nagamochi and Ibaraki . However, finding the girth of a matroid can be much more difficult: it is NP-hard for transversal matroids (attributed to Stockmeyer in ) and for binary matroids . Cho, Chen and Ding present some general algorithmic results.

It would be important to find larger classes of matroids where the girth or co-girth can be computed in polynomial time. One candidate could be the class of count matroids, where girth is NP-hard , but co-girth is open. One solved special case is the k-circuit matroid of a hypergraph, see . A polynomial algorithm for finding the co-girth of the rigidity matroid would solve the problem of Destroying rigidity.

Global structure of bases

A very exciting conjecture about matroids is Rota's basis conjecture, see its page at the Open Problem Garden. A related question is the Scrambled Rota conjecture of Aharoni and Kotlar:

Let [math]M=(S,r)[/math] be a loopless matroid of rank k whose ground set can be partitioned into k bases. Is it true that no matter how we partition S into sets of size k, the partition will have k-1 disjoint transversals that are bases?

There are several other elegant conjectures which show that the global structure of bases in a matroid is not really well understood. A matroid may have only one basis, but if it can be partitioned into two bases then it must have many, because there is a sequence of exchages leading from one to the other. The conjecture on Equitability of matroids says that in this case any subset can be cut (almost) exactly in half by a basis whose complement is also a basis:

Is it true that if the ground set S of a matroid M can be partitioned into 2 bases, then for any set [math]X \subseteq S[/math] there is a basis B such that [math]S \setminus B[/math] is also a basis and [math]\lfloor|X|/2 \rfloor \leq |B\cap X| \leq \lceil|X|/2 \rceil[/math]?

The above sequence of exchanges shows that there is a linear order of the elements where any interval of length r is a basis. This does not imply equitability, but if there would be a cyclic order with this property then equitability would follow. The conjecture on Cyclic orderings of matroids states that such a cyclic order always exists:

Let M be a matroid on ground set S, and suppose that S can be partitioned into k bases. Is it true that there is a cyclic ordering of the elements of S such that any [math]|S|/k[/math] consecutive elements in this ordering form a basis?