A new approach to the results of Kövari, Sós, and Turán concerning rectangle-free subsets of the grid

Abstract

For positive integers $m$ and $n$, define $f(m,n)$ to be the smallest integer such that any subset $A$ of the $m\times n$ integer grid with $|A|\ge f(m,n)$ contains a rectangle; that is, there are $x\in [m]$ and $y\in [n]$ and $d_1,d_2\in {\mathbb{Z}}^{+}$ such that all four points $(x,y)$, $(x+d_1,y)$, $(x,y+d_2)$, and $(x+d_1,y+d_2)$ are contained in $A$. In \cite{kovarisosturan}, Kövari, Sós, and Turán showed that $\dlim_{k \to \infty}\dfrac{f(k,k)}{k^{3/2}} = 1$. They also showed that whenever $p$ is a prime number, $f(p^2,p^2+p)=p^2(p+1)+1$. We recover their asymptotic result and strengthen the second, providing cleaner proofs which exploit a connection to projective planes, first noticed by Mendelsohn in \cite{mendelsohn87}. We also provide an explicit lower bound for $f(k,k)$ which holds for all $k$.

9 pages