0
$\begingroup$

You probably know Hall's theorem:

The family $\mathcal{S} = ( S_1, S_2, \dots, S_m)$ has an SDR(system of distinct representatives) if and only if for each $k = 1, 2, \dots, n$ and each choice of $k$ distinct indices $i_1, i_2, \dots, i_k$ from $\{1, 2, \dots, n\}$, $$\vert S_{i_1} \cup S_{i_2} \cup \dots \cup S_{i_k} \vert \ge k;$$ in short, every $k$ sets of the family collectively contain at least $k$ elements.

Now we reformulate the problem.
Suppose $x_1 \in S_1, \dots, x_m \in S_m$, where $x_1, \dots, x_m$ are not necessarily distinct. Then we say $x_1, \dots, x_m$ is a system of representatives (a.k.a. SR) of $S_1, \dots, S_m$. Show that $S_1, \dots, S_m$ has an SR s.t. each element occurs at most $r$ times if and only if for each $k = 1, 2, \dots, n$ and each choice of $k$ distinct indices $i_1, i_2, \dots, i_k$ from $\{1, 2, \dots, n\}$, $$r\vert S_{i_1} \cup S_{i_2} \cup \dots \cup S_{i_k} \vert \ge k.$$ I know how to prove Hall's theorem. And the "only if" part of the new problem is pretty trivial. However, I'm having difficulty applying the method used to prove Hall's theorem to this new problem.

$\endgroup$
0
$\begingroup$

Define $R={1, 2, \dots, r}.$ Let $A_i = S_i \times R$, $i=1,2,\dots,m$ ,where "$\times$ " stands for Cartesian product.
Then for each $k=1,2,\dots,n$ and each choice of $k$ distinct indices $\{i_1, i_2, \dots, i_k\}$, we have $$\vert A_{i_1} \cup A_{i_2} \cup \dots \cup A_{i_k}\vert = \vert (S_{i_1} \cup S_{i_2} \cup \dots \cup S_{i_k}) \times R \vert \ge \frac{k}{r}r = k.$$ Hence $\{A_{1} , A_{2} , \dots ,A_{m}\}$ has an SDR $\{(x_1,n_1),(x_2,n_2),\dots,(x_m,n_m)\}$. Assume $x_1=x_2=\dots=x_{r+1}.$ However, this cannot happen since there must exist $j,k \in \{1,2,\dots,r+1\}$ s.t. $n_j=n_k.$ This means $(x_j,n_j)=(x_k,n_k)$, which contradicts with the fact that $\{(x_1,n_1),(x_2,n_2),\dots,(x_m,n_m)\}$ is an SDR.
Therefore we can conclude that $\{x_1,x_2,\dots,x_m\}$ forms a SR of $\{S_1,S_2,\dots,S_m\}$ s.t. each element occurs at most $r$ times.

$\endgroup$

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.