3
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.