Counting sum-free sets in abelian groups

DOI10.1007/S11856-013-0067-YzbMATH Open1332.11030arXiv1201.6654OpenAlexW1970126555WikidataQ105583497 ScholiaQ105583497MaRDI QIDQ2017119FDOQ2017119

Authors: Noga Alon, József Balogh, Robert Morris, Wojciech Samotij 

Publication date: 25 June 2014

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Abstract: In this paper we study sum-free sets of order $m$ in finite Abelian groups. We prove a general theorem on 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 is divisible by a prime $q$ with $qequiv2pmod3$, for every $mgeC(q)sqrtnlogn$, thus extending and refining a theorem of Green and Ruzsa. In particular, we prove that almost all sum-free 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 size $m$ in an $(n,d,lambda)$-graph.

Full work available at URL: https://arxiv.org/abs/1201.6654

Recommendations

• The number of sum-free sets in abelian groups
• Sum-free sets in abelian groups
• Counting polynomial subset sums
• Maximal sum-free sets in finite abelian groups
• Maximal sum-free sets in finite abelian groups
• On maximal sum-free sets in abelian groups
• The number of sumsets in abelian group
• Sum-free sets in Abelian groups.
• On subset sums of zero-sum free sets of abelian groups
• Asymptotics of the number of sum-free sets in abelian groups of even order.

zbMATH Keywords

Type Isum-free set\((n, d, \lambda)\)-graphmaximum-size sum-free subsetsecond eigenvalue of a graphsum-free subsets of size mType I(q)

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Ramsey theory (05D10) Additive bases, including sumsets (11B13) Finite abelian groups (20K01)

Cites Work

• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• On the structure of linear graphs
• Expander graphs and their applications
• An entropy approach to the hard-core model on bipartite graphs
• Extremal results for random discrete structures
• Combinatorial theorems in sparse random sets
• The number of independent sets in a regular graph
• On sets of integers containing k elements in arithmetic progression
• Hypergraph containers
• Independent sets in hypergraphs
• Explicit construction of linear sized tolerant networks
• On the number of graphs without 4-cycles
• Arithmetic progressions of length three in subsets of a random set
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
• The number of \(K_{s,t}\)-free graphs
• The number of \(K_{m,m}\)-free graphs
• Sharp bounds for some multicolour Ramsey numbers
• Independent sets in regular graphs and sum-free subsets of finite groups
• Rado Partition Theorem for Random Subsets of Integers
• Threshold Functions for Ramsey Properties
• Sum-free sets in Abelian groups.
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• On Schur properties of random subsets of integers
• A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
• Extremal subgraphs of random graphs
• On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
• Matchings and independent sets of a fixed size in regular graphs
• Entropy, independent sets and antichains: A new approach to Dedekind's problem
• Sum-free sets in abelian groups
• On the asymptotic structure of sparse triangle free graphs
• For which densities are random triangle-free graphs almost surely bipartite?
• Maximal sum-free sets of elements of finite groups
• A refinement of the Cameron-Erdős conjecture
• Random sum-free subsets of abelian groups

Cited In (36)

• On subset sums of a zero-sum free set of seven elements from an abelian group
• Counting Gallai 3-colorings of complete graphs
• Sum-free sets in abelian groups
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Independent sets in hypergraphs
• Counting independent sets in graphs
• THE TYPICAL STRUCTURE OF MAXIMAL TRIANGLE-FREE GRAPHS
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
• On the structure of large sum-free sets of integers
• Right-angled Coxeter groups, universal graphs, and Eulerian polynomials
• On the Number ofB_h-Sets
• Sum-Free Sets of Integers with a Forbidden Sum
• Probabilistic hypergraph containers
• Random sum-free subsets of abelian groups
• Title not available (Why is that?)
• A characterization of elementary abelian 2-groups
• The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
• On the number of matroids compared to the number of sparse paving matroids
• Independent sets in graphs
• Sum-free subsets of finite abelian groups of type III
• On the number of matroids
• Sum-free sets in groups: a survey
• Asymptotics of the number of sum-free sets in abelian groups of even order.
• Maximum number of sum-free colorings in finite abelian groups
• Sum-free sets in Abelian groups.
• On maximal sum-free sets in abelian groups
• Upper bounds for the number of substructures in finite geometries from the container method
• Stability results for random discrete structures
• Number of \(A + B \neq C\) solutions in abelian groups and application to counting independent sets in hypergraphs
• The number of sum-free sets in abelian groups
• Groups containing small locally maximal product-free sets
• How many delta-matroids are there?
• On some sums involving the counting function of nonisomorphic abelian groups
• A note on the largest sum‐free sets of integers
• Intersecting families of discrete structures are typically trivial
• Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition

This page was built for publication: Counting sum-free sets in abelian groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2017119)