From Wikipedia, the free encyclopedia
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. There are
⌈
N
/
2
⌉
{\displaystyle \lceil N/2\rceil }
odd numbers in [N ], and so
2
N
/
2
{\displaystyle 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
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 .