Wiki
Wiki

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 E,QE,Q, k≥1k\ge1 and integers nt≥0n_t\ge0, there are pairwise disjoint partial transversals of exact sizes n1,…,nkn_1,\ldots,n_k if and only if, for every A⊆EA\subseteq E,

∣A∣≥∑j>σ(E∖A)nj∗=∑t(nt−min⁡(nt,σ(E∖A))).(1)|A|\ge\sum_{j>\sigma(E\setminus A)}n_j^* =\sum_t\bigl(n_t-\min(n_t,\sigma(E\setminus A))\bigr). \tag{1}

Only finitely many terms in the sum over jj are nonzero. The rank ρ(E∖A)\rho(E\setminus A) may replace σ(E∖A)\sigma(E\setminus A).

Proof. Let N=∑tntN=\sum_t n_t. Any disjoint packing under the upper limits ntn_t has union size at most NN. It has union size NN exactly when each size limit is attained.

By the maximum-union formula, such a packing exists exactly when, for every B⊆EB\subseteq E,

∣E∖B∣+∑tmin⁡(nt,σ(B))≥N.|E\setminus B|+\sum_t\min(n_t,\sigma(B))\ge N.

Set B=E∖AB=E\setminus A and rearrange. This is the second expression in (1). The equality with the sum over jj follows by counting, for each tt, the integers σ(E∖A)<j≤nt\sigma(E\setminus A)<j\le n_t. The rank version follows from the rank form of the same maximum formula. □\square

No separate feasibility condition is missing: the inequalities themselves force it. In the rank version the empty-set test gives nt≤ρ(E)n_t\le\rho(E) for every tt, and the A=EA=E test gives ∑tnt≤∣E∣\sum_tn_t\le|E|. Both remain valid when some or all ntn_t are zero.