Under what conditions is there a common transversal?

177 Views Asked by At

Let $S = \{S_1,\dots,S_n\}$ and $T = \{T_1,\dots,T_n\}$ be two collections of finite subsets of $\{1,2,\dots\}$.

A transversal for $S$ is a list of elements $s_1,\dots,s_n$, one coming from each set in $S$. A common transversal is a single transversal for both $S$ and $T$.

Under what conditions does a common transversal exist? Why?