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

Need to build an application around your data? Learn more about dataflow programming for rapid development and greater creativity. 

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

Check out the Exaptive data application Studio. Technology agnostic. No glue code. Use what you know and rely on the community for what you don't. Try the community version.

Topics:

Published at DZone with permission of John Cook, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

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

{{ parent.tldr }}

{{ parent.urlSource.name }}