Cameron–Erdős conjecture explained

In combinatorics, the Cameron–Erdős conjecture (now a theorem) is the statement that the number of sum-free sets contained in

[N] = \{ 1 ,\ldots,N\} is O ( { 2 ^{N/2} }\big).

The sum of two odd numbers is even, so a set of odd numbers is always sum-free. There are

\lceil N/ 2 \rceil odd numbers in [''N'' ], and so 2 ^{N/2} subsets of odd numbers in [''N'' ]. The Cameron–Erdős conjecture says that this counts a constant proportion of the sum-free sets.

The conjecture was stated by Peter Cameron and Paul Erdős in 1988.^[1] It was proved by Ben Green^[2] and independently by Alexander Sapozhenko^{[3] [4]} in 2003.

See also

• Erdős conjecture

Notes and References

1. .
2. .
3. .
4. .