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.
