Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Compilation-supplied correction. Welsh's prose in Theorem 9, printed p. 1327 (published PDF), asks this question, but its displayed criterion is false at that scope.
Statement. Let and let . There is a -transversal of with if and only if, for every ,
and
Proof. Suppose is a -transversal containing . The union of the -parts is a -element subset of , proving (1). At most elements of , and hence at most that many elements of , lie in parts indexed outside . Therefore
which rearranges to (2).
Conversely, assume (1) and (2). Condition (1) and Theorem 7 show that the replicated family has a full transversal.
On , take the matroid in which the elements of are free and all elements of are loops. Its rank is
For a subfamily of copied indices, let be its support in . Then and its union is . Condition (2) gives
By Perfect's criterion, has a partial-transversal range with . Since , this says . The copied family also has a full transversal, so augmentation extends to a full-transversal range . Then , and the replicated-family correspondence makes a -transversal of .
At , (2) forces . When , (2) is automatic and the statement reduces to the ordinary -Hall criterion.
The use of Perfect's criterion keeps the exact finite Rado input described in external inputs.