Wiki
Wiki

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 U⊆SU\subseteq S and let N=p(I)N=p(I). There is a pp-transversal XX of A\mathcal A with U⊆XU\subseteq X if and only if, for every J⊆IJ\subseteq I,

∣A(J)∣≥p(J),(1)|A(J)|\ge p(J), \tag{1}

and

∣A(J)∩U∣≥p(J)+∣U∣−N.(2)|A(J)\cap U|\ge p(J)+|U|-N. \tag{2}

Proof. Suppose X=⨆i∈IXiX=\bigsqcup_{i\in I}X_i is a pp-transversal containing UU. The union of the JJ-parts is a p(J)p(J)-element subset of A(J)A(J), proving (1). At most N−p(J)N-p(J) elements of XX, and hence at most that many elements of UU, lie in parts indexed outside JJ. Therefore

∣U∖A(J)∣≤N−p(J),|U\setminus A(J)|\le N-p(J),

which rearranges to (2).

Conversely, assume (1) and (2). Condition (1) and Theorem 7 show that the replicated family Ap\mathcal A^p has a full transversal.

On SS, take the matroid in which the elements of UU are free and all elements of S∖US\setminus U are loops. Its rank is

rU(Y)=∣Y∩U∣.r_U(Y)=|Y\cap U|.

For a subfamily K⊆IpK\subseteq I^p of copied indices, let JJ be its support in II. Then ∣K∣≤p(J)|K|\le p(J) and its union is A(J)A(J). Condition (2) gives

rU(A(J))=∣A(J)∩U∣≥∣U∣+p(J)−N≥∣U∣+∣K∣−N.r_U(A(J)) =|A(J)\cap U| \ge |U|+p(J)-N \ge |U|+|K|-N.

By Perfect's criterion, Ap\mathcal A^p has a partial-transversal range PP with rU(P)≥∣U∣r_U(P)\ge|U|. Since rU(P)≤∣U∣r_U(P)\le|U|, this says U⊆PU\subseteq P. The copied family also has a full transversal, so augmentation extends PP to a full-transversal range XX. Then U⊆XU\subseteq X, and the replicated-family correspondence makes XX a pp-transversal of A\mathcal A.

At J=∅J=\varnothing, (2) forces ∣U∣≤N|U|\le N. When U=∅U=\varnothing, (2) is automatic and the statement reduces to the ordinary pp-Hall criterion. □\square

The use of Perfect's criterion keeps the exact finite Rado input described in external inputs.