Wiki
Wiki

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

Updated


Source. Theorems 1 and 2, printed p. 148 (published PDF), specialized from the complete different-matroid arguments on pp. 150–152.

Statement. Let M=(E,F)M=(E,\mathcal F) be finite and k≥1k\ge1.

  1. EE is a union of kk independent sets, equivalently an indexed partition into kk independent sets with empty parts allowed, if and only if ∣A∣≤kr(A)|A|\le k r(A) for every A⊆EA\subseteq E.
  2. There are kk pairwise disjoint bases if and only if
∣E∖A∣≥k(r(E)−r(A))(A⊆E).(1)|E\setminus A|\ge k\bigl(r(E)-r(A)\bigr) \qquad(A\subseteq E). \tag{1}

Equivalently, EE has an indexed partition into kk spanning sets, with the same empty-part convention.

Proof. Apply Theorem 1c with every Mi=MM_i=M to obtain part 1 for partitions. An independent cover can be made disjoint by assigning each element to one of its containing members; heredity preserves independence. A partition is already a cover.

For part 2, Theorem 2c with all matroids equal gives ∣B∣≥k(r(E)−r(E∖B))|B|\ge k(r(E)-r(E\setminus B)) for every BB. Setting B=E∖AB=E\setminus A gives (1).

Disjoint bases extend to a partition into spanning sets by assigning all unused elements to, for example, the first part. Conversely, choosing a base within each part of a spanning partition gives disjoint bases. All choices are finite. □\square

The source describes part 2 using at least kk spanning parts and also discusses the maximum number of disjoint bases. For positive rank, combining spanning parts reduces an at-least-kk partition to kk parts. In rank zero the exact fixed-kk indexed formulation above is preferable: empty bases exist for every kk, so there is no finite maximum packing number under this convention. If a partition is defined to require nonempty parts, its rank-zero formulation needs the additional cardinality restriction and is not used here.