Back to Search
Start Over
A new approach to the results of K\'ovari, S\'os, and Tur\'an concerning rectangle-free subsets of the grid
- Source :
- Integers, 2012, Vol. 12, #A62
- Publication Year :
- 2012
-
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| \geq 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\"ovari, S\'os, and Tur\'an 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$.<br />Comment: 9 pages
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Journal :
- Integers, 2012, Vol. 12, #A62
- Publication Type :
- Report
- Accession number :
- edsarx.1206.1107
- Document Type :
- Working Paper