most recent 30 from http://mathoverflow.net 2013-06-19T04:43:55Z http://mathoverflow.net/feeds/question/26294 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26294/matroids-with-prescribed-independent-sets ilyaraz 2010-05-28T18:12:47Z 2010-05-28T19:54:57Z

<p>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.</p> <p>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.</p> <p>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?</p> <p>Any related results are interesting too.</p>