# Combinatorics: Systems of distinct representatives

I have two related(but separate) questions that are both heading toward something I am trying to prove(I think anyway).

1. Let's assume that $$A_1,A_2,...,A_n$$ is a collection of subsets of $$S$$ such that $$|A_i|=m$$ for all $$i$$ and every element in the set $$S$$ belongs to exactly $$m$$ of the sets $$A_1,A_2,...,A_n$$. Prove that the sets $$A_1,A_2,...,A_n$$ have a system of distinct representatives.

Obviously I am supposed to prove that the criterion in Hall's theorem holds. And I see that $$k\leq k\cdot m = \sum_{i=1}^{k}|A_i|$$, but I cant really make the needed connection between the union $$|\bigcup_{i=1}^{k}A_i|$$ and $$k$$.

1. Let's assume now that $$|S|=m\cdot n$$ and that $$S=A_1\cup A_2\cup...\cup A_m=B_1\cup B_2\cup...\cup B_m$$, where $$|A_i|=|B_i|=n$$ for all $$i$$. Prove that it is possible to re-index the sets $$A_i$$ such that $$A_i\cap B_i=\emptyset$$ for all $$i$$.

I don't really know where to start with this one and I am not entirely sure if it is even true but I think it is. Any help would be appreciated!

$$\sum_{i=1}^{k}|A_{i}|=mk$$ Note that every element in $$\bigcup_{i=1}^{k}A_{i}$$ appears at most $$m$$ times in the left hand side of the above equation, i.e. it is contained in at most $$m$$ of the sets $$A_{1},\cdots,A_{k}$$, which guarantees that $$\sum_{i=1}^{k}|A_{i}|\leq m\left|\bigcup_{i=1}^{k}A_{i}\right|.$$ Combine this inequality with the equation, and we get the desired $$\left|\bigcup_{i=1}^{k}A_{i}\right|\geq k.$$ A good view of the question is think of the elements and the sets as vertices of a bipartite graph, in which an element-representing vertex is connected by an edge to a set-representing vertex iff the element is contained in the set. The result we've just got translates to the fact that a $$m$$-regular bipartite graph always has a complete matching.

For your second question, it isn’t always possible to re-index the sets in the desired manner. To see this, let $$m=n$$ and $$S=[n]\times[n]$$. If we let $$A_k=\{k\}\times[n]$$ and $$B_k=[n]\times\{k\}$$ for each $$k\in[n]$$, we find that $$\langle k,\ell\rangle\in A_k\cap B_\ell$$ for each $$\langle k,\ell\rangle\in[n]\times[n]$$: each $$A_k$$ has non-empty intersection with each $$B_\ell$$.

In fact there is a counterexample whenever $$n\ge m$$. Let $$S=[m]\times[n]$$, and for $$k\in[m]$$ let $$A_k=\{k\}\times[n]$$. For $$\ell\in[m]$$ let

$$B_\ell=\big([m]\times\{\ell\}\big)\cup\left(\{\ell\}\times\big([n]\setminus[m]\big)\right)\,;$$

clearly $$\langle k,\ell\rangle\in A_k\cap B_\ell$$ for each $$\langle k,\ell\rangle\in[m]\times[m]$$.

• I can't quite wrap my head around your argumentation, but I found the same question here:math.stackexchange.com/questions/2833429/… Someone there seems to think that this statement is true. What do you think? Commented Nov 1, 2020 at 18:39
• @SlaveofChrist: It’s the opposite of your problem: in that one we want to show that we can always re-index them so that $A_i\cap B_i\color{red}{\ne}\varnothing$. Commented Nov 1, 2020 at 18:52
• Oops sorry about that, my bad. Commented Nov 1, 2020 at 18:55