Matroids

From Egres Open
(Redirected from Category:Matroids)
Jump to: navigation, search

Problems in this category



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 [1]. 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 [2]. However, finding the girth of a matroid can be much more difficult: it is NP-hard for transversal matroids (attributed to Stockmeyer in [3]) and for binary matroids [4]. Cho, Chen and Ding [5] 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 [6], but co-girth is open. One solved special case is the k-circuit matroid of a hypergraph, see [7]. 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?

References

  1. J. Geelen, B. Gerards, G. Whittle, Structure in Minor-Closed Classes of Matroids, manuscript.
  2. H. Nagamochi, T. Ibaraki, Computing edge-connectivity in multiple and capacitated graphs, DOI link.
  3. S.T. McCormick, A Combinatorial Approach to Some Sparse Matrix Problems, Ph.D. Thesis, Stanford University, Stanford CA (1983).
  4. A. Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory 43, 1757-1766. DOI link.
  5. J.J. Cho, Y. Chen, Y. Ding, On the (co)girth of a connected matroid, DOI link.
  6. A. Lomonosov, Graph and combinatorial algorithms for geometric constraint solving, Ph.D. Thesis, 2004. PDF link.
  7. T. Király, Computing the minimum cut in hypergraphic matroids, EGRES Quick Proof.