Corners Theorem
In arithmetic combinatorics, the corners theorem states that for every \varepsilon>0, for large enough N, any set of at least \varepsilon N^2 points in the N\times N grid \^2 contains a corner, i.e., a triple of points of the form \ with h\ne 0. It was first proved by Miklós Ajtai and Endre Szemerédi in 1974 using Szemerédi's theorem.. In 2003, József Solymosi gave a short proof using the triangle removal lemma. Statement Define a corner to be a subset of \mathbb^2 of the form \, where x,y,h\in \mathbb and h\ne 0. For every \varepsilon>0, there exists a positive integer N(\varepsilon) such that for any N\ge N(\varepsilon), any subset A\subseteq\^2 with size at least \varepsilon N^2 contains a corner. The condition h\ne 0 can be relaxed to h>0 by showing that if A is dense, then it has some dense subset that is centrally symmetric. Proof overview What follows is a sketch of Solymosi's argument. Suppose A\subset\^2 is corner-free. Construct an auxiliary tripartite graph G with ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   [Amazon]