# Proof there's a partition of set where for each $i$, $A_i \cap B_i \neq \emptyset$

We have the set of $S=\{1, 2, ..., nm\}$ and we partition it into n subsets of size m in two random ways, which gives us

1. $A_1, A_2, ..., A_n$ where $A_1\cup A_2 \cup ... \cup A_n = S$ and $A_i\cap A_j = \emptyset$ if $i\neq j$.

2. $B_1, B_2, ..., B_n$ where $B_1\cup B_2 \cup ... \cup B_n = S$ and $B_i\cap B_j = \emptyset$ if $i\neq j$.

I want to prove that with changing the indices there's a pairing of $A_i$ and $B_i$s where for each $i$ $A_i \cap B_i \neq \emptyset$

I think Hall's theorem seems to be a good way to go but I don't know how to model the problem into a graph to find a feasible pairing of subsets. Any help?

• Start by doing it for small values of $m$ and $n$. This will give you ideas for the general case. – realdonaldtrump Jun 27 '18 at 9:38
• Where you write "random", you mean "arbitrary". There's no random element in the question. – joriki Jun 27 '18 at 9:57
• @joriki I meant it's a random partition with no special property :-? but sure arbitrary is right – Alaleh Ahmadian Jun 27 '18 at 9:59
• That's a colloquial use of "random". In mathematics, "random" refers to probability and statistics, not to arbitrariness. – joriki Jun 27 '18 at 10:47

Hint: Let $G(V,E)$ be a simple bipartite graph with bipartition $V=V_A\sqcup V_B$, where $V_A=\big\{A_1,A_2,\ldots,A_n\big\}$ and $V_B=\big\{B_1,B_2,\ldots,B_n\big\}$, and where two vertices $A_i$ and $B_j$ are joined by an edge if and only if $A_i\cap B_j \neq \emptyset$. Show that $G$ satisfies the marriage condition of Hall's Marriage Theorem.