The Lovasz-Stein theorem Given a family $\mathcal{F}$ of subsets of some finite set $X$, its cover number of $\mathcal{F}$, $\text{Cov}(\mathcal{F})$, is the minimum number of members of $\mathcal{F}$ whose union covers all points of $X$.

Theorem 2.16. If each member of $\mathcal{F}$ has at most $a$ elements, and each point $x\in X$ belongs to at least $v$ of the sets
in $\mathcal{F}$, then $$\text{Cov}(\mathcal{F})\leq
 \dfrac{|\mathcal{F}|}{v}(1+\ln a).$$

Proof. Let $|X|=N, |\mathcal{F}|=M$ and consider the $N\times M$ $0$-$1$ matrix $A=(a_{x,i})$, where $a_{x,i}=1$ iff $x\in X$ belongs to the $i$-th member of $\mathcal{F}$. By our assumption, each row of $A$ has at least $v$ ones and each column at most $a$ ones. By double couting, we have that $Nv\leq Ma$, or equivalently, $$\frac{M}{v}\geq \frac{N}{a} \quad \quad (*).$$ Our goal is to show that $A$ must contain an $N\times K $ submatrix $C$ with no all-$0$ rows and such that $$K\leq (M/v)(1+\ln a).$$
We describe a constructive procedure for producing the desired submatrix $C$. Let $A_a=A$ and define $A'_a$ to be any maximal set of columns from $A_a$ whose supports are pairwise disjoint and whose columns each have $a$ ones. Let $K_a=|A'_a|$. Discard from $A_a$ the columns of $A'_a$ and any row with a one in $A'_a$. We are left with a $k_a\times (M-K_a)$ matrix $A_{a-1}$, where $k_a=N-aK_a$. Clearly, the columns of $A_{a-1}$ have at most $a-1$ ones (indeed, otherwise such a column could be added to the previously discarded set, contradicting its maximality). We continue by doing to $A_{a-1}$ what we did to $A_a$. That is we define $A'_{a-1}$ to be any maximal set of columns from $A_{a-1}$, whose supports are pairwise disjoint and whose columns each have $a-1$ ones. Let $K_{a-1}=|A'_{a-1}|$, then discard from $A_{a-1}$ the columns of $A'_{a-1}$ and any row with a one in $A'_{a-1}$ getting a $k_{a-1}\times (M-K_a-K_{a-1})$ matrix $A_{a-2}$, where $k_{a-1}=N-aK_a-(a-1)K_{a-1}$.
The process will terminate after at most $a$ steps. The union of the columns of the discarded sets form the desired submatrix $C$ with $K=\sum \limits_{i=1}^a K_i$. The first step of the algorithm gives $k_a=N-aK_a$, which we rewrite, setting $k_{a+1}=N$, as $$K_a=\frac{k_{a+1}-k_a}{a}.$$ Analogously, $$K_i=\frac{k_{i+1}-k_i}{i} \  \text{for} \ i=1,\dots,a.$$ Now we derive an upper bound for $k_i$ by counting the number of ones in $A_{i-1}$ in two ways: every row of $A_{i-1}$ contains at least $v$ ones, and every column at most $i-1$ ones, thus $$vk_i\leq (i-1)(M-K_a-\dots-K_{i+1})\leq (i-1)M,$$ or equivalently $$k_i\leq \frac{(i-1)M}{v}.$$
So, $$K=\sum\limits_{i=1}^a K_i=\sum\limits_{i=1}^a \frac{k_{i+1}-k_i}{i}=$$ $$=\frac{k_{a+1}}{a}+\frac{k_{a}}{a(a-1)}+\frac{k_{a-1}}{(a-1)(a-2)}+\dots+\frac{k_{2}}{2\cdot 1}-k_1\leq $$ $$\leq \frac{N}{a}+\frac{M}{v}(\frac{1}{a}+\dots+\frac{1}{2})\leq \frac{N}{a}+\frac{M}{v}\ln a.$$ The last inequality here follows because $1+\frac{1}{2}+\dots+\frac{1}{n}$ is the $n$-th harmonic number which is known to lie between $\ln n$ and $\ln n+1$. Together with $(*)$, this yields $K\leq (M/v)(1+\ln a)$, as desired.
This proof is copied from the book of Stasys Jukna "Extremal combinatorics" and I would like to clarify some moments of this proof.
My questions:

*

*I am a bit confused with the procedure and how it works. In the first step we need to find any maximal set of columns which have pairwise disjoint supports and each of them have $a$ ones. What if there no columns with $a$ ones?


*Intuitively I can understand why this process terminates after at most $a$ steps but can anyone explain it in a rigorous way, please?


*How we take the union of the columns of the discarded sets if those columns have different size?


*If we take $C$ to be the union of the columns of the discarded sets. why any row of $C$ has $1$ among its entries?
I would be very thankful if someone can explain those questions!
Thank you so much for your attention!
 A: *

*If there are no columns with $a$ ones, then the empty set is a maximal set of columns with $a$ ones. This seems trivial, but it lets our proof keep going just as well as any other case: notably, after removing the empty set of columns in this case, all columns of $A_{a-1}$ have at most $a-1$ ones.

*We prove (formally, by induction on $i$) that after the $i^{\text{th}}$ step, we get a matrix $A_{a-i}$ in which all columns have at most $a-i$ ones. So after $a$ steps, the matrix $A_0$ we are left with has no ones in it, which indicates that there are no uncovered elements.

*"The union of the columns of the discarded sets" is a bit imprecise. To get the $N \times K$ submatrix we want, we should take all the columns of $A$ corresponding to any columns we discarded. However, be careful: in the analysis to follow, we are not counting the number of ones in this submatrix! We are counting the number of ones in $A_a', A_{a-1}', \dots$, which may be different, because we delete some rows in the process.

*In the $i^{\text{th}}$ step of the algorithm, one of two things can happen to the $x^{\text{th}}$ row. Either $A_{a-i}'$ has a one in the $x^{\text{th}}$ row; in that case, the row gets deleted, but also $C$ will have a one in the $x^{\text{th}}$ row, because $C$ gets columns from $A_{a-i}'$. Or $A_{a-i}'$ has all zeroes in the $x^{\text{th}}$ row; in that case, the row does not get deleted, and also does not lose any of its ones. We know that at the end of the algorithm, the matrix $A_0$ has no ones anywhere; therefore at some point, the $x^{\text{th}}$ row must have gotten deleted - and that's when $C$ got a one in the $x^{\text{th}}$ row.

