On a Generalization of Szemeredi's Theorem

2005/03/28 by Ilya D. Shkredov, I. D. Shkredov, Shkredov, I. D. · 2 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Dynamical Systems (math.DS) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Number Theory (math.NT) #math.DS #math.NT

paper · pdf · doi:10.48550/arxiv.math/0503639

51 pages

arxiv created 2005/03/28 · openalex publication_date 2005/03/28 · arxiv updated 2009/12/01 · openalex created_date 2016/09/30 · openalex updated_date 2026/07/28

Abstract

Let A ⊆ [1,..,N]² be a set of cardinality at least N²/(log log N)^c, where c>0 is an absolute constant. We prove that A contains a triple (k,m), (k+d,m), (k,m+d), where d>0. This theorem is a two-dimensional generalization of Szemeredi's theorem on arithmetic progression.

Cited by

• The Lens of Abelian Embeddings
• Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics

Related

• On a two-dimensional analog of Szemeredi's Theorem in Abelian groups
• New bounds for Szemeredi's theorem, II: A new bound for r₄(N)
• New bounds for Szemerédi's theorem, III: A polylogarithmic bound for r₄(N)
• A Constructive Lower Bound on Szemerédi's Theorem
• An Improved Construction of Progression-Free Sets