Cameron–Erdős-sejtés

A kombinatorika területén a Cameron–Erdős-sejtés (most már tétel) az az állítás, hogy $|N|=\{1,\ldots ,N\}$ összegmentes részhalmazai száma $O\left({2^{N/2}}\right).$

Ha a páratlan számok halmazát tekintjük: két páratlan szám összege mindig páros, így bármely, kizárólag páratlan számokat tartalmazó halmaz összegmentes. Az |N|-ben pontosan $\lceil N/2\rceil$ páratlan szám van, ezek részhalmazainak száma $2^{N/2}$ . A Cameron–Erdős-sejtés azt mondja ki, hogy ez valamennyi összegmentes halmazra igaz.

A sejtést Peter Cameron és Erdős Pál fogalmazta meg 1988-ban.^[1] Ben Green,^[2] illetve tőle függetlenül Alexander Sapozhenko^[3]^[4] igazolta 2003-ban.

Kapcsolódó szócikkek szerkesztés

Erdős Pál sejtéseinek listája

Jegyzetek szerkesztés

↑ 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, <http://books.google.com/books?id=68g0Ds4FNM0C&pg=PA61&lpg=PA61>.
↑ Green, Ben (2004), "The Cameron-Erdős conjecture", The Bulletin of the London Mathematical Society 36 (6): 769–778, DOI 10.1112/S0024609304003650.
↑ 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.

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

[2] Green, Ben (2004), "The Cameron-Erdős conjecture", The Bulletin of the London Mathematical Society 36 (6): 769–778, 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.

[1]

[2]

[3]

[4]