Wiki
Wiki

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

Updated


Source. Theorem 1b, printed p. 150 (published PDF).

Statement. Let M=(E,F)M=(E,\mathcal F) be finite, k≥1k\ge1, and 0≤nt≤r(E)0\le n_t\le r(E) be integers. Independent sets ItI_t of exact sizes ntn_t cover EE if and only if

∣A∣≤∑t=1kmin⁡(nt,r(A))=∑j=1r(A)nj∗(A⊆E),(1)|A|\le\sum_{t=1}^k\min(n_t,r(A)) =\sum_{j=1}^{r(A)}n_j^* \qquad(A\subseteq E), \tag{1}

where nj∗=∣{t:nt≥j}∣n_j^*=|\{t:n_t\ge j\}|.

Proof. If the cover exists, each A∩ItA\cap I_t is independent, with size at most both ntn_t and r(A)r(A). Counting their union proves (1). The displayed equality is the conjugate-counting identity in the maximum-union formula.

Conversely, truncate MM at ntn_t to obtain matroid MtM_t of rank min⁡(nt,r(A))\min(n_t,r(A)), by Lemma 1. Condition (1) is exactly Theorem 1c for these matroids, so it yields a partition into independent sets JtJ_t with ∣Jt∣≤nt|J_t|\le n_t. Extend each JtJ_t within MM to size ntn_t, which is possible because nt≤r(E)n_t\le r(E). The extensions cover EE; disjointness is not required. □\square