Cameron–Erdős förmodan

Inom kombinatorik är Cameron–Erdős förmodan (numera en sats) en förmodan som säger att antalet summafria delmängder av $|N|=\{1,\ldots ,N\}$ är $O\left({2^{N/2}}\right).$

Summan av två udda tal är alltid jämn, så en mängd av udda tal är summafri. Det finns $\lceil N/2\rceil$ udda tal i |N| och härmed $2^{N/2}$ delmängder av udda tal i |N|. Cameron–Erdős förmodan säger att antalet summafria mängder är en konstant gånger det.

Förmodan framlades av Peter Cameron och Paul Erdős 1988.^[1] Den bevisades av Alexander Sapozhenko^[2]^[3] och oberoende av Ben Green 2004.^[4]

Källor

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Cameron–Erdős conjecture, 25 januari 2014.

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

[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, s. 61–79, http://books.google.com/books?id=68g0Ds4FNM0C&pg=PA61&lpg=PA61 .

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

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

[4] Green, Ben (2004), ”The Cameron-Erdős conjecture”, The Bulletin of the London Mathematical Society 36 (6): 769–778, doi:10.1112/S0024609304003650 .

[1]

[2]

[3]

[4]