Wiki
Wiki

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

Updated


Source. Theorem 13 and its proof, printed p. 1329 (published PDF).

Printed statement. Let A=(A1,…,An)\mathcal A=(A_1,\ldots,A_n) and B=(B1,…,Bm)\mathcal B=(B_1,\ldots,B_m) be finite indexed families, let pi≥0p_i\ge0 be integers, and let k≥0k\ge0 be an integer. The source states that there is one subset X⊆SX\subseteq S which is both an AA pp-transversal and a BB kk-transversal if and only if

k∣B(K)∣≥∣K∣(15)k|B(K)|\ge |K| \tag{15}

and

∣A(J)∩B(K)∣≥p(J)+∣K∣−m(16)|A(J)\cap B(K)|\ge p(J)+|K|-m \tag{16}

for every J⊆[n]J\subseteq[n] and K⊆[m]K\subseteq[m].

This exact-common-support conclusion is false.

Counterexample. Take

S={a,b},A=({a}),p1=1,S=\{a,b\},\qquad \mathcal A=(\{a\}),\qquad p_1=1,

and

B=({a},{b}),k=1.\mathcal B=(\{a\},\{b\}),\qquad k=1.

Condition (15) is Hall's condition for the two singleton sets and holds for all K⊆[2]K\subseteq[2]. For (16), when J=∅J=\varnothing the right side is ∣K∣−2≤0|K|-2\le0. When J={1}J=\{1\}, the required lower bound is ∣K∣−1|K|-1: it is at most zero for ∣K∣≤1|K|\le1, and for K=[2]K=[2] the intersection has size one. Thus (16) also holds in every case.

The only AA pp-transversal is {a}\{a\}. The only BB 11-transversal is {a,b}\{a,b\}. No subset is both.

The proof's failure occurs after Theorem 5 produces a BB kk-transversal XX of rank

N=∑i=1npiN=\sum_{i=1}^n p_i

in the pp-transversal matroid. Rank NN means that XX contains a base of that matroid; it does not mean that XX itself is a base. In the example, {a,b}\{a,b\} has rank one and contains the base {a}\{a\}. □\square

The printed proof also refers to “(1)” where it needs (15). Correcting that label does not repair the substantive error. The actual containment criterion is proved in the compilation-supplied corrected theorem.