# Partitioning a matroid into independent sets

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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