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?

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

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .