Corners theorem

Corners theorem

In mathematics, the corners theorem is an important result, proved by Miklós Ajtai and Endre Szemerédi, of a statement in arithmetic combinatorics. It states that for every ε > 0 there exists N such that given at least εN2 points in the N × N grid {1, ..., N} × {1, ..., N}, there exists a corner, i.e., three points in the form (x, y), (x + h, y), and (x, y + h). Later Solymosi gave a simpler proof, based on the triangle removal lemma. The corners theorem implies Roth's theorem.

References

  • M. Ajtai, E. Szemerédi: Sets of lattice points that form no squares, Studia Sci. Math. Hungar., 9(1974), 9–11.
  • J. Solymosi: Note on a generalization of Roth's theorem, Algorithms Combin., 25, 2003,Springer, Berlin, 825–827,

External link


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Krein–Milman theorem — In mathematics, more precisely in functional analysis, the Krein–Milman theorem is a statement about convex sets. A particular case of this theorem, which can be easily visualized, states that given a convex polygon, one only needs the corners of …   Wikipedia

  • Perron–Frobenius theorem — In linear algebra, the Perron–Frobenius theorem, proved by Oskar Perron (1907) and Georg Frobenius (1912), asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding… …   Wikipedia

  • Gauss–Bonnet theorem — The Gauss–Bonnet theorem or Gauss–Bonnet formula in differential geometry is an important statement about surfaces which connects their geometry (in the sense of curvature) to their topology (in the sense of the Euler characteristic). It is named …   Wikipedia

  • Japanese theorem for concyclic polygons — In geometry, the Japanese theorem states that no matter how we triangulate a concyclic polygon, the sum of inradii of triangles is constant. Conversely, if the sum of inradii independent from the triangulation, then the polygon is cyclic. The… …   Wikipedia

  • Japanese theorem for concyclic quadrilaterals — The Japanese theorem states that the centers of the incircles of certain triangles inside a concyclic quadrilateral are vertices of a rectangle.Triangulate an arbitrary concyclic quadrilateral by its diagonals, this yields four overlapping… …   Wikipedia

  • Lebesgue's density theorem — In mathematics, Lebesgue s density theorem states that for any Lebesgue measurable set A, the density of A is 1 at almost every point in A. Intuitively, this means that the edge of A, the set of points in A whose neighborhood is partially in A… …   Wikipedia

  • Pappus's theorem — ▪ geometry  in mathematics, theorem named for the 4th century Greek geometer Pappus of Alexandria that describes the volume of a solid, obtained by revolving a plane region D about a line L not intersecting D, as the product of the area of D and… …   Universalium

  • Ultraparallel theorem — In hyperbolic geometry, the ultraparallel theorem states that every pair of ultraparallel lines in the hyperbolic plane has a unique common perpendicular hyperbolic line.Proof in the Poincaré half plane modelLet :a < b < c < d be four distinct… …   Wikipedia

  • Exterior angle theorem — The exterior angle theorem is a theorem in elementary geometry which states that the exterior angle of a triangle is equal to the sum of the two remote interior angles.A triangle has three corners, called vertices . The sides of a triangle that… …   Wikipedia

  • Arithmetic combinatorics — arose out of the interplay between number theory, combinatorics, ergodic theory and harmonic analysis. It is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division). Additive… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”