Theorem 7: existence of a p-transversal

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

Updated Oct 5

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

Statement. A finite indexed family $\mathcal A=(A_i)_{i\in I}$ has a $p$ -transversal if and only if

|A(J)|\ge p(J) \qquad(J\subseteq I). \tag{1}

Proof. Apply Theorem 4 to the free matroid on $S$ , whose rank is $r(X)=|X|$ . Its independent $p$ -transversals are simply all $p$ -transversals, and the rank condition in that theorem becomes (1). $\square$

Equivalently, (1) is Hall's condition for the replicated family $\mathcal A^p$ . Coordinates with $p_i=0$ cause no copies. If $I$ is empty, the condition is $0\ge0$ and the empty set is the unique transversal.

Linked from (5)

Transversal theory and matroids Theorem 12: common p- and q-transversal support Corrected Theorem 13: a k-transversal containing a p-transversal Corrected Theorem 9A: a p-transversal contained in U Corrected Theorem 9B: a p-transversal containing U

Graph