Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform matroid $U_{|A|,\max_{C \in B} |C|}$. But what if we restrict ourselves to, say, binary or even graphic matroids.

Can we characterize $B$'s that have a 'covering' binary (graphic) matroid with rank $r$? Does the problem of finding such a minimum $r$ lies in $\mathbf{P}$ or $\mathbf{coNP}$? Maybe there is a kind of min-max formula.

The case of graphic matroids can be reformulated as follows: suppose we have $m$ 'invisible' edges. We know that some subsets are acyclic. What is the minimum possible value of $n - c$, where $n$ stands for a number of vertices, and $c$ - for a number of connected components?

Any related results are interesting too.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.