Cameron–Erdős conjecture

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{\big (}{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.

Notes

^ Cameron, P. J.; Erdős, P. (1990), "On the number of sets of integers with various properties", Number theory: proceedings of the First Conference of the Canadian Number Theory Association, held at the Banff Center, Banff, Alberta, April 17-27, 1988, Berlin: de Gruyter, pp. 61–79, ISBN 9783110117233, MR 1106651.
^ Green, Ben (2004), "The Cameron-Erdős conjecture", The Bulletin of the London Mathematical Society, 36 (6): 769–778, arXiv:math.NT/0304058, doi:10.1112/S0024609304003650, MR 2083752, S2CID 119615076.
^ Sapozhenko, A. A. (2003), "The Cameron-Erdős conjecture", Doklady Akademii Nauk, 393 (6): 749–752, MR 2088503.
^ Sapozhenko, Alexander A. (2008), "The Cameron-Erdős conjecture", Discrete Mathematics, 308 (19): 4361–4369, doi:10.1016/j.disc.2007.08.103, MR 2433862.

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

[1] Cameron, P. J.; Erdős, P. (1990), "On the number of sets of integers with various properties", Number theory: proceedings of the First Conference of the Canadian Number Theory Association, held at the Banff Center, Banff, Alberta, April 17-27, 1988, Berlin: de Gruyter, pp. 61–79, ISBN 9783110117233, MR 1106651.

[2] Green, Ben (2004), "The Cameron-Erdős conjecture", The Bulletin of the London Mathematical Society, 36 (6): 769–778, arXiv:math.NT/0304058, doi:10.1112/S0024609304003650, MR 2083752, S2CID 119615076.

[3] Sapozhenko, A. A. (2003), "The Cameron-Erdős conjecture", Doklady Akademii Nauk, 393 (6): 749–752, MR 2088503.

[4] Sapozhenko, Alexander A. (2008), "The Cameron-Erdős conjecture", Discrete Mathematics, 308 (19): 4361–4369, doi:10.1016/j.disc.2007.08.103, MR 2433862.

[1]

[2]

[3]

[4]

See also

Notes