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 and let be an integer. The family has a -transversal with if and only if, for every ,
and
Proof. Give the matroid whose elements in are free and whose elements outside are loops. Its rank function is
Since , the inequality is equivalent to . Apply Theorem 5 with . Its first condition is (1), and its second condition is exactly (2). The equivalence in Theorem 5 proves both directions.
This argument includes . It also includes : if , (1) fails, while for condition (2) forces , the only possible support.
Linked from (1)
Graph