Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Sum-Free Subset Results

DZone 's Guide to

Sum-Free Subset Results

· Big Data Zone ·
Free Resource

This posts gives some results for the sum-free subset problem in the previous post.

Paul Erdős proved in 1965 that a set of n non-zero integers contains a sum-free subset of size larger than kn where k = 1/3.

The best value of k is unknown. Erdős proved k is at least 1/3. Alon and Kleitman proved that kmust be less than 12/29.

Alon and Kleitman also consider the problem of sum-free subsets of an arbitrary Abelian group. They proved that set of n non-zero elements of an Abelian group must have a sum-free subset of at least 2n/7 elements. The constant 2/7 is the best value in general. But for the specific case of the integers one can do better, since 1/3 > 2/7, but the best constant for the integer case is unknown.

Source: The Probabilistic Method

Topics:

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}