Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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!) –  Mariano Suárez-Alvarez Jan 23 '12 at 4:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.