MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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.