TY - JOUR

T1 - Counting sum-free sets in abelian groups

AU - Alon, Noga

AU - Balogh, József

AU - Morris, Robert

AU - Samotij, Wojciech

N1 - Funding Information:
∗Research supported in part by: (NA) ERC Advanced Grant DMMCA, a USA-Israeli BSF grant and the Israeli I-Core program; (JB) NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grant 11067, and OTKA Grant K76099; (RM) a CNPq bolsa de Produtividade em Pesquisa; (WS) ERC Advanced Grant DMMCA and a Trinity College JRF. Received January 31, 2012 and in revised form October 18, 2012

PY - 2014/1/1

Y1 - 2014/1/1

N2 - In this paper we study sum-free sets of order m in finite abelian groups. We prove a general theorem about independent sets in 3-uniform hypergraphs, which allows us to deduce structural results in the sparse setting from stability results in the dense setting. As a consequence, we determine the typical structure and asymptotic number of sum-free sets of order m in abelian groups G whose order n is divisible by a prime q with q ≡ 2 (mod 3), for every m ⩾ (Formula presented.), thus extending and refining a theorem of Green and Ruzsa. In particular, we prove that almost all sumfree subsets of size m are contained in a maximum-size sum-free subset of G. We also give a completely self-contained proof of this statement for abelian groups of even order, which uses spectral methods and a new bound on the number of independent sets of a fixed size in an (n, d, λ)-graph.

AB - In this paper we study sum-free sets of order m in finite abelian groups. We prove a general theorem about independent sets in 3-uniform hypergraphs, which allows us to deduce structural results in the sparse setting from stability results in the dense setting. As a consequence, we determine the typical structure and asymptotic number of sum-free sets of order m in abelian groups G whose order n is divisible by a prime q with q ≡ 2 (mod 3), for every m ⩾ (Formula presented.), thus extending and refining a theorem of Green and Ruzsa. In particular, we prove that almost all sumfree subsets of size m are contained in a maximum-size sum-free subset of G. We also give a completely self-contained proof of this statement for abelian groups of even order, which uses spectral methods and a new bound on the number of independent sets of a fixed size in an (n, d, λ)-graph.

UR - http://www.scopus.com/inward/record.url?scp=84886736803&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84886736803&partnerID=8YFLogxK

U2 - 10.1007/s11856-013-0067-y

DO - 10.1007/s11856-013-0067-y

M3 - Article

AN - SCOPUS:84886736803

VL - 199

SP - 309

EP - 344

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

SN - 0021-2172

IS - 1

ER -