Wiki
Wiki

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

Updated


Source. Equation (14) and its defect-Hall explanation in the proof of Theorem 12, printed pp. 1328–1329 (published PDF).

Statement. Let Tp(A)T_p(\mathcal A) be the transversal matroid of the replicated family Ap\mathcal A^p, whether or not a full pp-transversal exists. For every X⊆SX\subseteq S,

rp(X)=min⁡J⊆I(∣X∩A(J)∣+N−p(J)),(1)r_p(X) =\min_{J\subseteq I} \bigl(|X\cap A(J)|+N-p(J)\bigr), \tag{1}

where N=p(I)N=p(I). Equivalently, for every integer tt,

rp(X)≥t⟺∣X∩A(J)∣≥p(J)+t−N(J⊆I).(2)r_p(X)\ge t \quad\Longleftrightarrow\quad |X\cap A(J)|\ge p(J)+t-N \quad(J\subseteq I). \tag{2}

If A\mathcal A has a pp-transversal, then rp(S)=Nr_p(S)=N and the bases of Tp(A)T_p(\mathcal A) are exactly the pp-transversals.

Proof. The rank formula (1) is Welsh's equation (14), which the source obtains from the defect version of Hall's theorem applied to the replicated family (pp. 1328–1329). The equivalence (2) restates (1) threshold by threshold.

The final base assertion is the corrected Theorem 3. □\square