Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.