Wiki
Wiki

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

Updated


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

Statement. Let U⊆SU\subseteq S and let k≥0k\ge0 be an integer. The family A=(Ai)i∈I\mathcal A=(A_i)_{i\in I} has a kk-transversal XX with U⊆XU\subseteq X if and only if, for every J⊆IJ\subseteq I,

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

and

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

Proof. Give SS the matroid whose elements in UU are free and whose elements outside UU are loops. Its rank function is

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

Since rU(Y)≤∣U∣r_U(Y)\le|U|, the inequality rU(Y)≥∣U∣r_U(Y)\ge|U| is equivalent to U⊆YU\subseteq Y. Apply Theorem 5 with t=∣U∣t=|U|. Its first condition is (1), and its second condition is exactly (2). The equivalence in Theorem 5 proves both directions. □\square

This argument includes U=∅U=\varnothing. It also includes k=0k=0: if I≠∅I\ne\varnothing, (1) fails, while for I=∅I=\varnothing condition (2) forces U=∅U=\varnothing, the only possible support.