Deficit Hall theorem

Task number: 3993

Prove the following generalization of the Hall theorem:

Let a set system \( (X, {\cal S}) \) and a positive integer \( k \) be such that the union of any subsystem \( {\cal T } \subseteq {\cal S} \) contains at least \(|{\cal T}|-k \) elements of the underlying set \( X \). Then, after excluding at most \( k \) sets from \( \cal S \), the resulting set system has a system of distint representatives.

  • Solution

    We convert the given problem onto the Hall theorem as follows: Augment the set \( X \) by \( k \) new elements, which we add to each set from \( \mathcal S \).

    The modified system satisfies the Hall condition, so it has a system of different representatives. After discarding at most \(k\) sets, which are represented by additionally added elements, we get a system of representatives for the reduced set system, as required.

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email