The following combinatorial problem came up that seems easy but has turned out to be very intricate.

Assume that you are given $2n$ sets, say $S_1, \ldots, S_{2n}$ such that

  • each $S_i$ has exactly $n$ elements,
  • each element is in at most $n$ sets, $\forall x \colon | \{ S_i | x \in S_i \}| \leq n$,
  • for each $S_i$, there is an $S_j$ such that they are disjoint, $S_i \cap S_j = \emptyset$.

The final goal is to prove that it is possible to pick in each $S_i$ a different element $x_i \in S_i$ (i.e. $i \neq j \Rightarrow x_i \neq x_j$).

Assume we could prove that there is always a pair of elements $x,y$ such that none of the $S_i$ contains both $x$ and $y$. Then the statement above follows easily by induction.

But how to prove this? Is it actually true?


Okay, the original problem can be solved using the marriage theorem. Using the marriage theorem, it is sufficient to prove that each collection of $S_i$ of size $k$ contains at least $k$ many different elements.

For $k \leq n$, there is nothing to do since already one single $S_i$ contains $n$ elements. For an arbitrary $k$, note that a collection of $k$ many $S_i$ contains $n \cdot k$ elements (counted with multiplicity). As each element occurs in at most $n$ many $S_i$, this means we have at least $\frac{n \cdot k}{n} = k$ many different elements.

The problem whether it is possible to pick a pair of elements such that none of the $S_i$ contains both remains unanswered.


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.