Wiki
Wiki

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

Updated


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

Statement. Let M=(E,F)M=(E,\mathcal F) be finite and let 0≤nt≤r(E)0\le n_t\le r(E), 1≤t≤k1\le t\le k, be integers, with k≥1k\ge1. There are pairwise disjoint independent sets ItI_t with ∣It∣=nt|I_t|=n_t if and only if

∣A∣≥∑t(nt−min⁡(nt,r(E∖A)))=∑j=r(E∖A)+1r(E)nj∗(A⊆E).(1)\begin{aligned} |A| &\ge\sum_t\bigl(n_t-\min(n_t,r(E\setminus A))\bigr)\\ &=\sum_{j=r(E\setminus A)+1}^{r(E)}n_j^* \qquad(A\subseteq E). \tag{1} \end{aligned}

Proof. The truncation MtM_t at ntn_t has rank ntn_t on EE, and rank min⁡(nt,r(B))\min(n_t,r(B)) on a subset BB. Its bases are exactly the independent sets of MM of size ntn_t. Theorem 2c for the family (Mt)(M_t) therefore gives precisely the first inequality in (1). For the equality, count for each tt the integers r(E∖A)<j≤ntr(E\setminus A)<j\le n_t; the upper bound nt≤r(E)n_t\le r(E) permits the common upper limit r(E)r(E). This proves both directions, including nt=0n_t=0. □\square