Wiki
Wiki

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

Updated


Compilation-supplied correction. The inequalities are (15)–(16) in Theorem 13, printed p. 1329 (published PDF). The exact-common-support conclusion there is false.

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 and k≥0k\ge0 be integers. There are sets Y⊆X⊆SY\subseteq X\subseteq S such that YY is an AA pp-transversal and XX is a BB kk-transversal if and only if

k∣B(K)∣≥∣K∣(K⊆[m]),(1)k|B(K)|\ge |K| \qquad(K\subseteq[m]), \tag{1}

and

∣A(J)∩B(K)∣≥p(J)+∣K∣−m(J⊆[n], K⊆[m]).(2)|A(J)\cap B(K)|\ge p(J)+|K|-m \qquad(J\subseteq[n],\ K\subseteq[m]). \tag{2}

Proof. Put N=p([n])N=p([n]). Suppose first that Y⊆XY\subseteq X as in the statement. The set YY is a base of the rank-NN transversal matroid Tp(A)T_p(\mathcal A), so rp(X)=Nr_p(X)=N. Apply the necessary direction of Theorem 5 to the BB kk-transversal XX in that matroid, with t=Nt=N. Its first condition is (1), and its second is

rp(B(K))≥∣K∣+N−m.(3)r_p(B(K))\ge |K|+N-m. \tag{3}

By the rank formula, (3) is equivalent to (2) for every JJ.

Conversely, assume (1) and (2). Taking K=[m]K=[m] in (2) gives

∣A(J)∣≥∣A(J)∩B([m])∣≥p(J).|A(J)|\ge |A(J)\cap B([m])|\ge p(J).

Thus an AA pp-transversal exists by Theorem 7, and Tp(A)T_p(\mathcal A) has rank NN with the AA pp-transversals as its bases. The rank formula turns (2) into (3). Theorem 5, applied with t=Nt=N, now gives a BB kk-transversal XX with rp(X)≥Nr_p(X)\ge N. Since the whole matroid has rank NN, the restriction to XX contains a base Y⊆XY\subseteq X. That base is an AA pp-transversal, as required.

The endpoint m=0m=0 is included. Then (1) is vacuous, while (2) at K=∅K=\varnothing forces p(J)=0p(J)=0 for every JJ and hence N=0N=0; take X=Y=∅X=Y=\varnothing. The case k=0k=0 with m>0m>0 is excluded on both sides by (1). □\square

The correction retains the result actually proved by the full-rank argument. It is not labeled as the printed theorem or as a published erratum.