# Random $0-1$ matrices

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