Maximal disjoint collections and matrix rank

Question

1. First, a combinatorial question fit for an undergrad course. Say I have a collection $\mathcal{C}$ of non-empty subsets of $S=\{1,\dotsc,n\}$ such that every element of $\mathcal{C}$ has at most $k$ elements and every element of $S$ is contained in no fewer than $1$ and no more than $k$ elements of $\mathcal{C}$. Then it is easy to see that there has to be a disjoint subcollection of $\mathcal{C}$ consisting of at least $n/(k^3-k^2+k)$ sets. Is this lower bound optimal?

(To me, the question feels like a discrete analogue of the Vitali covering lemma.)

2. Let $A$ be an $n$-by-$n$ matrix whose entries are $0$s, $1$s and $-1$s. Assume that the number of non-zero entries in any row or column is greater than $0$ and no greater than $k$. By 1., the rank of $A$ is at least $n/(k^3-k^2+k)$. Can one give a better lower bound?

Answer 1

In 2) you may get $n/k$ as follows:

consider the random linear ordering $\Pi$ on the set of columns. In each row $\alpha$, mark the non-zero element which is the $\Pi$-maximal, if it belongs to the column $s$, say that $s$ is the leader of the row $\alpha$: $s=L(\alpha)$. For $s=1,\ldots,n$ denote $\xi(s)=\mathbb{1}_{\exists \alpha: s=L(\alpha)}$. It is easy to see that the rank of our matrix is not less than $\sum_s \xi(s)$ (for fixed $\Pi$). Take the expectation, we get the lower bound $\sum_s \mathbb{E} \xi(s)$. It remains to observe each $s$, $\mathbb{E} \xi(s)$ is not less than $1/k$. Indeed, take any element in the column $s$. It makes $s$ the leader of its row with probability at least $1/k$.

Of course this estimate is sharp at least when $k|n$, as the block matrix shows.

I think this stuff is less or more known, Cosmin Pohoata told me some references which I have already forgotten.