Let $E$ be a finite set. Let $d,m,n\in\mathbb N$. Let $\mathcal A:=\{A_1,\dots,A_m\}$ and $\mathcal B:=\{B_1,\dots,B_n\}$ be two families of subsets of $E$. A partial transversal of $\mathcal A$ is the image of an injective function from a subset of $\{1,\dots,m\}$ to $E$ such that for all $i$ in the domain of $f$, $f(i)\in A_i$. A common partial transversal of $\mathcal A$ and $\mathcal B$ is a subset that is a partial transversal of $\mathcal A$ and $\mathcal B$.

The family of partial transversals of $\mathcal A$ is (the family of independent sets of) a matroid on $E$. (See, for example, Theorem 6.5.2 of Mirsky's book, Transversal Theory.)

If one wants to determine the cardinality of the set of maximum size that is a union of $d$ common partial transversals, is there a way of doing so by considering intersections of independent sets arising from possibly different matroid structures on possibly different sets?

The inspiration behind this is that if one has a matroid on a set and one wants to find the subset of maximum size that is a union of $d$ independent sets, one can translate this into the problem of finding the subset of maximum size that is independent in two different matroid structures on a different ground set. (See, for example, the end of $\S6$ of Chapter 8 of Lawler's book, Combinatorial Optimization: Networks and Matroids.)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.