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