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