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$ – realdonaldtrump Jun 27 '18 at 9:38
  • 1
    $\begingroup$ Where you write "random", you mean "arbitrary". There's no random element in the question. $\endgroup$ – joriki Jun 27 '18 at 9:57
  • $\begingroup$ @joriki I meant it's a random partition with no special property :-? but sure arbitrary is right $\endgroup$ – Alaleh Ahmadian Jun 27 '18 at 9:59
  • 1
    $\begingroup$ That's a colloquial use of "random". In mathematics, "random" refers to probability and statistics, not to arbitrariness. $\endgroup$ – 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.


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.