On an almost all version of the Balog-Szemeredi-Gowers theorem

2018/11/26 by Xuancheng Shao, Shao, Xuancheng · 1 citation
Computer Science · Mathematics · #11B13 #11B30 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.1811.10707

openalex publication_date 2018/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We deduce, as a consequence of the arithmetic removal lemma, an almost-all version of the Balog-Szemerédi-Gowers theorem: For any K≥ 1 and ε > 0, there exists δ= δ(K,ε)>0 such that the following statement holds: if |A+_ΓA| ≤ K|A| for some Γ≥ (1-δ)|A|², then there is a subset A' ⊂ A with |A'| ≥ (1-ε)|A| such that |A'+A'| ≤ |A+_ΓA| + ε |A|. We also discuss issues around quantitative bounds in this statement, in particular showing that when A ⊂ ℤ the dependence of δ on ε cannot be polynomial for any fixed K>2.

Cited by

• Graphs With the Same Edge Count in Each Neighborhood

Related

• A quantitative improvement on the hypergraph Balog-Szemerédi-Gowers theorem
• On a certain generalization of the Balog-Szemeredi-Gowers Theorem
• Yet another proof of Szemeredi's theorem
• A note on the Freiman and Balog-Szemeredi-Gowers theorems in finite fields
• Improved Bounds for Szemerédi's Theorem