4
$\begingroup$

What I want to prove is:

Let $U=(A_1\ldots,A_n)$ be a family of sets and let $P\subseteq A_1\cup \cdots \cup A_n$. Then $U$ has a transversal which includes the set $P$ if and only if (i) $U$ has a transversal (ii)$|P\setminus (\cup_{i\in I}A_i)|\le n-|I|$ for any $I\subseteq \{1,\ldots,n\}$.

A transversal of $U$ is a set $X$ with $|X|=n$ which can have its elements arranged in a certain order, $X=\{a_1,\ldots,a_n\}$ say,so that $a_1\in A_1,\ldots,a_n\in A_n$; in other words then $n$ distinct elements of $X$ 'represent' the $ sets.

I think \Rightarrow$ direction is quite easy to prove but the converse, I don't know how to start the proof.

Does anyone has any idea to prove this statement?

  • 3
    This is an extension of the classical Hall marriage theorem. It should be in Leonid Mirsky's *Transversal theory: an account of some aspects of combinatorial mathematics* (a *whole* book on the subject!)2012-01-23

0 Answers 0