Maximal disjoint collections and matrix rank

Question

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

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
– Tony Huynh, Commented May 3, 2019 at 8:29

Fedor Petrov · Accepted Answer · 2019-07-12 06:04:07Z

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.

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
– H A Helfgott, Commented May 3, 2019 at 9:27
Here's an easier proof. Start with $S = \emptyset$. At each step, if there is a row $j$ such that the $j$th entry of every column in $S$ is $0$, include in $S$ a column whose $j$th entry is non-zero. Stop if there is no such row. Since every column has at most $k$ non-zero entries, $S$ must have at least $n/k$ elements in the end. — H A Helfgott
– H A Helfgott, Commented May 31, 2020 at 19:48

Stack Exchange Network

Maximal disjoint collections and matrix rank

1 Answer 1

You must log in to answer this question.

Maximal disjoint collections and matrix rank

1 Answer 1

You must log in to answer this question.

Related