The Cameron-Erdos theorem, in combinatorics, concerns the number of sum-free sets contained in the integers from 1 to N, establishing that this count is O(2 to the power N/2). Peter Cameron and Paul Erdos formulated the statement as a conjecture in 1988, and it was proved independently by Ben Green and by Alexander Sapozhenko in 2003; the result reflects that every subset of the roughly N/2 odd numbers in that range is automatically sum-free, since two odd numbers never sum to an odd number, and shows that such odd-only subsets make up a constant fraction of all sum-free sets.
Sources
Cameron-Erdos conjecture (Wikipedia)
Lead sectionQuote, Lead section
In combinatorics, the Cameron-Erdős conjecture (now a theorem) is the statement that the number of sum-free sets contained in [ N ] = { 1, …, N } {\displaystyle [N]=\{1,\ldots,N\}} is O ( 2 N / 2). {\displaystyle O{\big (}{2^{N/2}}{\big)}.} The sum of two odd numbers is even, so a set of odd numbers is always sum-free.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.