4 added 80 characters in body

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 least minimum possible value of $n - c$, where $n$ stands for a number of verticescan be in our graph, and $c$ - for a number of connected components?

Any related results are interesting too.

3 added 200 characters in body

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 least number of vertices can be in our graph?

Any related results are interesting too.

2 added 86 characters in body

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.

Any related results are interesting too.

1