Partitioning a matroid into independent sets

From himtp
Jump to: navigation, search

(suggested by Kristóf Bérczi, Csaba Király and Tamás Király)

Problem Statement

Let M=(S,\mathcal{I}) be a matroid and k,l\in\mathbb{Z}_+ be positive integers such that l\leq k. Give a characterization of the existence of a partition S_1\cup\dots\cup S_k of S such that S_{i_1}\cup\dots\cup S_{i_l} is an independent set for any subset \{i_1,\dots,i_l\}\subseteq\{1,\dots,k\} of indeces.

What is known?

When k is arbitrary and l=1, the problem can be solved easily by using the matroid partition algorithm.

If l=k-1, then it is not difficult to see that there exists a proper partition if and only if the matroid obtained by taking k-1 parallel copies of each element of M can be partitioned into k independent sets. Hence the first open case is when k=4 and l=2.

For the graphic matroid of a graph G=(V,E), the problem asks for a coloring of the edges by k colors in which each cycle receives at least l different colors. That is, when l=2 then we are looking for a coloring of the edges by k colors such that there is no two-colored cycle in G. There are several results on so-called acyclic colorings of graphs, but in that case a proper coloring of the edges is needed not containing two-colored cycles.

Please add comments here