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

preprint2012arXivOpen access

Abstract

For positive integers mm and nn, define f(m,n)f(m,n) to be the smallest integer such that any subset AA of the m×nm \times n integer grid with ∣A∣≥f(m,n)|A| \geq f(m,n) contains a rectangle; that is, there are x∈[m]x\in [m] and y∈[n]y \in [n] and d1,d2∈Z+d_{1},d_{2} \in \mathbb{Z}^{+} such that all four points (x,y)(x,y), (x+d1,y)(x+d_{1},y), (x,y+d2)(x,y+d_{2}), and (x+d1,y+d2)(x+d_{1},y+d_{2}) are contained in AA. 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 pp is a prime number, f(p2,p2+p)=p2(p+1)+1f(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)f(k,k) which holds for all kk.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.