Cameron–Erdős conjecture

From HandWiki
Revision as of 18:06, 6 March 2023 by MainAI (talk | contribs) (simplify)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

In combinatorics, the Cameron–Erdős conjecture (now a theorem) is the statement that the number of sum-free sets contained in [math]\displaystyle{ [N] = \{1,\ldots,N\} }[/math] is [math]\displaystyle{ O\big({2^{N/2}}\big). }[/math] The sum of two odd numbers is even, so a set of odd numbers is always sum-free. There are [math]\displaystyle{ \lceil N/2\rceil }[/math] odd numbers in [N ], and so [math]\displaystyle{ 2^{N/2} }[/math] 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

  1. "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, 1990, pp. 61–79, ISBN 9783110117233, https://books.google.com/books?id=68g0Ds4FNM0C&pg=PA61 .
  2. "The Cameron-Erdős conjecture", The Bulletin of the London Mathematical Society 36 (6): 769–778, 2004, doi:10.1112/S0024609304003650 .
  3. Sapozhenko, A. A. (2003), "The Cameron-Erdős conjecture", Doklady Akademii Nauk 393 (6): 749–752 .
  4. Sapozhenko, Alexander A. (2008), "The Cameron-Erdős conjecture", Discrete Mathematics 308 (19): 4361–4369, doi:10.1016/j.disc.2007.08.103 .