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

Find your next Big Data job at DZone Jobs. See jobs focused on Big Data or create your profile and have the employers come to you!

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

Find your next Big Data job at DZone Jobs. See jobs focused on Big Data or create your profile and have the employers come to you!

Topics:

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

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

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

{{ parent.tldr }}

{{ parent.urlSource.name }}