Wiki
Wiki

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

Updated


Source. Theorem 8, printed p. 1327 (published PDF).

Statement. Let A=(Ai)i∈I\mathcal A=(A_i)_{i\in I} be a finite indexed family and let k,t≥0k,t\ge0 be integers. There is a kk-transversal of cardinality at least tt if and only if

k∣A(J)∣≥∣J∣(11)k|A(J)|\ge |J| \tag{11}

and

∣A(J)∣≥∣J∣+t−∣I∣(12)|A(J)|\ge |J|+t-|I| \tag{12}

for every J⊆IJ\subseteq I.

Proof. In the free matroid on SS, every set is independent and r(X)=∣X∣r(X)=|X|. Substituting this rank function into Theorem 5 turns its second inequality into (12), while its first inequality is (11). Its equivalence therefore proves the statement. □\square

The k=0k=0 and I=∅I=\varnothing cases are exactly those dispatched in Theorem 5; no positivity assumption is added here.