I'm working my way through the Oxford notes in Probabilistic Combinatorics and came across this question in one of the question sheets; I'd like to stress that this is not my homework: I'm simply working through the notes for my own pleasure.

For $n, r ∈ \mathbb{N}$, $1 < r < n$, let $z(r, n)$ be the largest possible number of $0$ entries in an $n × n$ matrix which has no $r × r$ submatrix whose entries are all $0$. (Here a submatrix is obtained by selecting any $r$ rows and any $r$ columns; the rows/columns need not be consecutive.)

Consider a random matrix in which each entry is $0$ with probability $p$ and $1$ with probability $1−p$, independently.

Deduce that $z(r, n) > pn^{2}-p^{r^{2}}n^{2r}.$

My solution:

Let $[n]_{2}$ denote the set of all $n \times n$ matrices, with only $0-1$ entries. For each $\sigma \in [n]_{2}$ let the random variable $X(\sigma)$ denote the number of $0$ entries in $\sigma$ and the random variable $Y(\sigma)$ denote the number of $r \times r$ submatrices filled with entirely with $0$'s. It follows that $\mathbb{E}(X)=pn^{{2}}$ and $\mathbb{E}(Y)=\binom{n}{r}^{2}p^{r^{2}}<n^{2r}p^{r^{2}}$.

Further more consider the random variable $X-Y$ for which $\mathbb{E}(X-Y)>pn^{2}-n^{2r}p^{r^{2}}$. It follows that there exists a $\sigma \in [n]_{2}$ such that $X(\sigma)-Y(\sigma)>pn^{2}-n^{2r}p^{r^{2}}$. Given such a $\sigma$ construct $\sigma' \in [n]_{2}$ as follows. For each of the all $0$, $r \times r$ sub matrices of $\sigma$ remove at random a single $0$ from each to ensure $\sigma'$ has no $r \times r$ such sub-matrices. We have removed at most $\binom{n}{r}^{2}<n^{2r}$ such zero's and so we can conclude that $\sigma'$ has at least $pn^{2}-p^{r^{2}}n^{2r}$ zeros thus we can conclude that $z(n,r)>pn^{2}-p^{r^{2}}n^{2r}$.

I'd appreciate any comments on the validity of the proof.


This solution is correct, but with a mistake right at the end.

To construct $\sigma'$, you do not remove a $0$ from every submatrix of $\sigma$. Rather, you only remove a $0$ from every one of the $Y(\sigma)$ all-$0$ $r \times r$ submatrices. That is, you remove at most $Y$ zeros, not at most $n^{2r}$. (The latter bound is still true, just not helpful.) Then, $\sigma'$ has exactly $X - Y$ zero entries, and you can apply the expectation of $X - Y$ as you did.

If instead you removed a zero from every $r \times r$ submatrix, you would have to say something like $$Y(\sigma') \geq Y(\sigma) - n^{2r} \geq p n^2 - p^{r^2} n^{2r} - n^{2r},$$ which is hard (impossible?) to bound usefully.

Writing this up might look like this:

Given $\sigma \in [n]_2$, to make $\sigma$ contain no all-$0$ $r \times r$ submatrix, we must flip at most $Y(\sigma)$ zeros in $\sigma$. Since $\sigma$ has $X(\sigma)$ zeros, we can make a "$0$-submatrix-free" $\sigma'$ with at least $X(\sigma) - Y(\sigma)$ zeros. The expectation of $X - Y$ is $$E[X - Y] = p n^2 - p^{r^2} {n \choose r}^2 > p n^2 - p^{r^2} n^{2r}.$$ Therefore $z(r, n) > pn^2 - p^{r^2} n^{2r}.$

As an aside, the maximum of the lower bound given occurs at $$p = \frac{1}{(k^2 n^{2k - 2})^{\frac{1}{k^2 - 1}}} = \frac{1}{k^{\frac{2}{k^2 - 1}} n^{\frac{2}{k + 1}}},$$ so the best bound we can get is something like

\begin{equation*} z(k, n) > \left( \frac{n^k}{k^{\frac{1}{k - 1}}} \right)^{\frac{2}{k + 1}} - \left( \frac{n}{k^{\frac{k}{k - 1}}} \right)^{\frac{2k}{k + 1}}, \end{equation*}

modulo algebraic mistakes. For fixed $k$, this tells us that $z(k, n) = O(n^{2k / (k + 1)})$.

(Note: I've switched $r$ for $k$ in this section.)


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.