Combinatorics: Systems of distinct representatives

Question

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

2. 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!

Answer 1

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]$.

Answer 2

$$\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.