Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Source. Theorem 2a, printed p. 150 (published PDF).
Statement. With finite , and integers , there are pairwise disjoint partial transversals of exact sizes if and only if, for every ,
Only finitely many terms in the sum over are nonzero. The rank may replace .
Proof. Let . Any disjoint packing under the upper limits has union size at most . It has union size exactly when each size limit is attained.
By the maximum-union formula, such a packing exists exactly when, for every ,
Set and rearrange. This is the second expression in (1). The equality with the sum over follows by counting, for each , the integers . The rank version follows from the rank form of the same maximum formula.
No separate feasibility condition is missing: the inequalities themselves force it. In the rank version the empty-set test gives for every , and the test gives . Both remain valid when some or all are zero.