Counting sum-free sets in abelian groups

被引:23
作者
Alon, Noga [1 ]
Balogh, Jozsef [2 ]
Morris, Robert [3 ]
Samotij, Wojciech [1 ,4 ]
机构
[1] Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel
[2] Univ Illinois, Dept Math, Urbana, IL 61801 USA
[3] IMPA, Jardim Bot, Rio De Janeiro, RJ, Brazil
[4] Univ Cambridge Trinity Coll, Cambridge CB2 1TQ, England
基金
美国国家科学基金会;
关键词
HARD-CORE MODEL; INDEPENDENT SETS; ASYMPTOTIC STRUCTURE; RANDOM SUBSETS; GRAPHS; NUMBER; SUBGRAPHS; ENTROPY;
D O I
10.1007/s11856-013-0067-y
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 a parts per thousand 2 (mod 3), for every m a (c) 3/4 , 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, lambda)-graph.
引用
收藏
页码:309 / 344
页数:36
相关论文
共 44 条