Cameron–Erdős conjecture

{{Short description|Theorem in combinatorics}}

In combinatorics, the Cameron–Erdős conjecture (now a theorem) is the statement that the number of sum-free sets contained in $[N]\; =\; \backslash \{1,\backslash ldots,N\backslash \}$ is $O\backslash big(\{2^\{N/2\}\}\backslash big).$

The sum of two odd numbers is even, so a set of odd numbers is always sum-free. There are $\backslash lceil\; N/2\backslash 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.{{citation

| last1 = Cameron | first1 = P. J. | author1-link = Peter Cameron (mathematician)

| last2 = Erdős | first2 = P. | author2-link = Paul Erdős

| contribution = On the number of sets of integers with various properties

| location = Berlin

| mr = 1106651

| pages = 61–79

| publisher = de Gruyter

| title = Number theory: proceedings of the First Conference of the Canadian Number Theory Association, held at the Banff Center, Banff, Alberta, April 17-27, 1988

| url = https://books.google.com/books?id=68g0Ds4FNM0C&pg=PA61

| year = 1990| isbn = 9783110117233 }}. It was proved by Ben Green{{citation

| last = Green | first = Ben | author-link = Ben J. Green

| arxiv = math.NT/0304058

| doi = 10.1112/S0024609304003650

| issue = 6

| journal = The Bulletin of the London Mathematical Society

| mr = 2083752

| pages = 769–778

| title = The Cameron-Erdős conjecture

| volume = 36

| year = 2004| s2cid = 119615076 }}. and independently by Alexander Sapozhenko{{citation

| last = Sapozhenko | first = A. A.

| issue = 6

| journal = Doklady Akademii Nauk

| mr = 2088503

| pages = 749–752

| title = The Cameron-Erdős conjecture

| volume = 393

| year = 2003}}.{{citation

| last = Sapozhenko | first = Alexander A.

| doi = 10.1016/j.disc.2007.08.103

| issue = 19

| journal = Discrete Mathematics

| mr = 2433862

| pages = 4361–4369

| title = The Cameron-Erdős conjecture

| volume = 308

| year = 2008| doi-access = free

}}. in 2003.