A nearly tight upper bound on tri-colored sum-free sets in characteristic 2

2016/05/26 by Robert Kleinberg, Kleinberg, Robert
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1605.08416

openalex publication_date 2016/05/26 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

A tri-colored sum-free set in an abelian group H is a collection of ordered triples in H³, \(a_i,b_i,c_i)\_i=1^m, such that the equation a_i+b_j+c_k=0 holds if and only if i=j=k. Using a variant of the lemma introduced by Croot, Lev, and Pach in their breakthrough work on arithmetic-progression-free sets, we prove that the size of any tri-colored sum-free set in \mathbbF₂ⁿ is bounded above by 6 n \choose \lfloor n/3 \rfloor. This upper bound is tight, up to a factor subexponential in n: there exist tri-colored sum-free sets in \mathbbF₂ⁿ of size greater than n \choose \lfloor n/3 \rfloor ⋅ 2^{-√(16 n / 3)} for all sufficiently large n.

Related

• On the number of sum-free triplets of sets
• An upper bound on tricolored ordered sum-free sets
• Maximum number of sum-free colorings in finite abelian groups
• Complete 3-term arithmetic progression free sets of small size in vector spaces and other abelian groups
• Counting sum-free sets in Abelian groups