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

 
discard

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

Browse other questions tagged or ask your own question.