An improved construction for the triangle removal lemma

2025/07/07 by Hunter, Zach
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2507.05231

Abstract

We construct n-vertex graphs G where εn² edges must be deleted to become triangle-free, which contain less than ε^(C_new-o(1))log₂ 1/εn³ triangles for C_new= (1)/(4log₂(4/3)) ≈ 1.6601. Previously, a bound of the same shape was known, but with C_new replaced by C_old := C_new/2. Our construction uses ideas from additive combinatorics, drawing especially from the corners problem, but does not yield new bounds for those problems.

Citations

• Quasipolynomial bounds for the corners theorem
• A note on Ordered Ruzsa-Szemerédi graphs
• Improving Behrend's construction: Sets without arithmetic progressions in integers and over finite fields
• Strong Bounds for 3-Progressions
• Lower bounds for corner-free sets
• Larger Corner-Free Sets from Better NOF Exactly-N Protocols
• On graphs decomposable into induced matchings of linear sizes
• A note on Elkin's improvement of Behrend's construction
• An Improved Construction of Progression-Free Sets

Related

• Efficient Removal without Efficient Regularity
• Multigraphs (only) satisfy a weak triangle removal lemma
• The maximum number of triangles in K_1,s,t-free graphs
• Removal lemmas and approximate homomorphisms
• Graph removal lemmas