Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source. Theorem 9 and the preceding rank sentence, printed p. 1327 (published PDF).

Printed statement. Welsh states that A\mathcal A has a pp-transversal containing U⊆SU\subseteq S if and only if

∣A(J)∩U∣≥p(J)(J⊆I).(1)|A(J)\cap U|\ge p(J) \qquad(J\subseteq I). \tag{1}

This statement is false. Condition (1) is instead the Hall criterion for a pp-transversal contained in UU. The prose immediately before the theorem uses the matroid with the single base UU, of rank r(X)=∣X∩U∣r(X)=|X\cap U|, which does express the “contains UU” problem. Thus neither changing only the prose nor changing only the displayed inequality gives an unambiguous transcription repair.

Counterexamples. First, (1) is not necessary for a pp-transversal containing UU. Take

I={1},p1=2,S=A1={u,v},U={u}.I=\{1\},\quad p_1=2,\quad S=A_1=\{u,v\},\quad U=\{u\}.

The unique pp-transversal {u,v}\{u,v\} contains UU, but at J={1}J=\{1\} the printed inequality reads 1≥21\ge2.

Nor is the printed inequality sufficient for the printed conclusion. Take

I={1},p1=1,S=A1=U={a,b}.I=\{1\},\quad p_1=1,\quad S=A_1=U=\{a,b\}.

Condition (1) holds for both subsets of II, but every pp-transversal has one element and therefore cannot contain the two-element set UU. □\square

The valid contained-in criterion is proved in the corrected contained theorem. The valid contains-UU criterion needs ordinary pp-Hall conditions and an additional defect inequality, and is proved in the corrected contains theorem. Both are compilation-supplied results, not claims about a published erratum.