Wiki
Wiki

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

Updated


Source. Theorem 2d, printed p. 152 (published PDF).

Statement. With pairwise disjoint independent J1,…,JkJ_1,\ldots,J_k and E′=E∖⋃iJiE'=E\setminus\bigcup_iJ_i as above, pairwise disjoint bases BiB_i of MM satisfying Ji⊆BiJ_i\subseteq B_i exist if and only if

∣A∣≥∑i=1k(r(E)−r((E′∖A)∪Ji))(A⊆E′).(1)|A|\ge\sum_{i=1}^k \bigl(r(E)-r((E'\setminus A)\cup J_i)\bigr) \qquad(A\subseteq E'). \tag{1}

Proof. If such bases exist, Bi∖AB_i\setminus A is an independent subset of (E′∖A)∪Ji(E'\setminus A)\cup J_i, since it cannot contain any other seed. Hence

∣Bi∩A∣≥r(E)−r((E′∖A)∪Ji).|B_i\cap A|\ge r(E)-r((E'\setminus A)\cup J_i).

Summing inside AA proves necessity.

For sufficiency, first apply (1) to A=∅A=\varnothing. Each summand r(E)−r(E′∪Ji)r(E)-r(E'\cup J_i) is nonnegative by rank monotonicity, so their sum can be at most zero only if

r(E′∪Ji)=r(E)(1≤i≤k).(2)r(E'\cup J_i)=r(E)\qquad(1\le i\le k). \tag{2}

Thus the rank obstruction must be checked before constructing a packing of full bases.

As in Theorem 1d, contract JiJ_i and restrict to E′E'. The resulting matroid MiM_i has

ri(A)=r(A∪Ji)−r(Ji),ri(E′)=r(E)−r(Ji),r_i(A)=r(A\cup J_i)-r(J_i),\qquad r_i(E')=r(E)-r(J_i),

where the second equality uses (2). Substituting these expressions in Theorem 2c on E′E' gives exactly (1). It yields disjoint bases KiK_i of MiM_i. Each Bi=Ki∪JiB_i=K_i\cup J_i is independent in MM and has r(E)−r(Ji)+r(Ji)=r(E)r(E)-r(J_i)+r(J_i)=r(E) elements, so is a base. The unions are pairwise disjoint because the KiK_i lie in E′E' and the seeds were disjoint. This proves sufficiency, including E′=∅E'=\varnothing and rank zero. □\square