0
$\begingroup$

I think I have seen theorems like this before, but since the question is very simple I was unable to really search for an answer on here; didn't find it, at least.

I have $n+1$ not necessarily distinct sets $Q_k \subset \lbrace 1, 2, \dots n \rbrace$. Further, we assume each $Q_k$ contains at least two elements, and that $Q_1 \cup Q_2 \cup \cdots \cup Q_{n+1} = \lbrace 1, 2, \dots, n \rbrace$. If we let $\mathcal{Q}$ be the collection of the $Q_k$'s, Is it true that there is an injection $f: \lbrace 1, 2, \dots, n \rbrace \rightarrow \mathcal{Q}$ such that $j \in f(j)$ for all $j$?

That is to say, if $\mathcal{Q} = \lbrace Q_k \rbrace$ is a covering of $\lbrace 1, 2, \dots, n \rbrace$ by $n+1$ subsets each containing at least two elements, can we pair off the points $1, 2, \dots, n$ with some $n$ of $Q_k$'s so that each integer is paired off with a subset containing it?

Thanks a lot! Either a reference or proof is fine!

$\endgroup$
2
$\begingroup$

This looks like a case for Hall's theorem. You have a bipartite graph with one part indexed by $\{1,2,\ldots,n\}$ and the other by the $ Q_i$ and we join $j$ and $Q_i$ when $j\in Q_i$. By Hall's theorem there is a matching of the type you need iff for each $A\subseteq\{1,\ldots,n\}$, there are at least $|A|$ $Q_i$ with $Q_i\cap A\ne\emptyset$.

I don't think this condition is automatically satisfied in your set-up.

$\endgroup$
2

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.