# Maximal disjoint collections and matrix rank

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.)

1. 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?
• For (1), should the bound be $|\mathcal C| / (k^3-k^2+k)$? Nothing seems to prevent $\mathcal C$ of just consisting of one set of size $k$ for example. – Tony Huynh May 3 at 8:29
• Just fixed the statement. – H A Helfgott May 3 at 9:00

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, 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.

• Thanks Fedor! Please pass me a reference where you have it (or, if not, give me a keyword, so that I can look for the references myself). – H A Helfgott May 3 at 9:27