Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Source. Theorem 1b, printed p. 150 (published PDF).
Statement. Let be finite, , and be integers. Independent sets of exact sizes cover if and only if
where .
Proof. If the cover exists, each is independent, with size at most both and . Counting their union proves (1). The displayed equality is the conjugate-counting identity in the maximum-union formula.
Conversely, truncate at to obtain matroid of rank , by Lemma 1. Condition (1) is exactly Theorem 1c for these matroids, so it yields a partition into independent sets with . Extend each within to size , which is possible because . The extensions cover ; disjointness is not required.