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$
    – Alaleh
    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.


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.