This is a problem in my graph theory class and I'm unsure about how to solve it..
Let $X$ be the set $\{1,2,\dots,mn\}$. Suppose we partition $X$ into $m$ sets $P_1,\dots,P_m$, each of size $n$.
Suppose we choose another partition $Q_1,\dots,Q_m$, each of size $n$.
Show that the sets $P_i$ can be renumbered so that $P_i \cap Q_i$ is non-empty for every $i$.
Thanks in advance!
Edit: I'm attempting to use Hall's Marriage theorem to solve this but I'm struggling with formulating the solution in a way that would get me to my answer.
Hall's Marriage Theorem is the right way to go. To put it in terms of graphs, consider a bipartite graph, where The $P_k$ form one of the bipartition sets, and the $Q_k$ form the other. Make $P_i$ adjacent to $Q_j$ if and only if $P_i\cap Q_j\neq \emptyset.$ Then you want to show that there is a complete matching, so if you can show that Hall's condition holds, you are done.
That is, you must show that if $P_{i_1},\dots,P_{i_k}$ are given, for some $1\leq k\leq m,$ then there exist $Q_{i_1},\dots,Q_{i_k}$ that each have at least one element in common with at least one of the $P_{i_j}.$
This is quite easy when you think about it.