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?
  • $\begingroup$ 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. $\endgroup$ – Tony Huynh May 3 at 8:29
  • $\begingroup$ Just fixed the statement. $\endgroup$ – 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.

  • $\begingroup$ 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). $\endgroup$ – H A Helfgott May 3 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.