Prove that $\text{ex}\left(n, \begin{pmatrix} 1 & 1\\ 1 & 1\end{pmatrix}\right) = \Theta(n^{3/2})$.

Question

I was reading the thesis http://www.renyi.hu/~keszegh/papers/szakdolgozat.pdf, and they cite Theorem 2.6 without proof (because apparently it is a well-known fact from extremal graph theory).

The extremal function $\text{ex}(n, P)$ is defined in the paper as the maximum possible number of 1's in an $n\times n$ binary matrix that avoids a pattern $P$.

Prove that $\text{ex}\left(n, \begin{pmatrix} 1 & 1\\ 1 & 1\end{pmatrix}\right) = \Theta(n^{3/2})$.

Can someone post a proof here or redirect me to one? Thanks!

Answer 1

You might try:

Corollary 2.4 in "On 0-1 matrices and small excluded submatrices" (.ps)

---

What occurs in the above is a citation to Theorem 1.1 in "Davenport-Schinzel theory of matrices" (.pdf), which is the actual proof.