Ipoteza lui Cameron-Erdő
Conjectura lui Cameron-Erdő este o ipoteză
combinatorie dovedită în 2003 .
Formulare
Numărul de submulțimi fără sumă din este egal cu .
![{\displaystyle \{1,\ldots ,N\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61e58c165c50e8c2366f8dfd296aae80395a4647)
![{\displaystyle O\left({2^{N/2}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7318dac31dcd61cca5cb79e671767797ff72a4d)
Note
Suma a două numere impare este întotdeauna pară, deci orice set de numere impare este întotdeauna lipsită de sume. Există numere impare în , respectiv subseturi de numere impare în . Conjectura afirmă că această mărime, până la o constantă, determină comportamentul asimptotic al numărului de mulțimi fără sumă.
![{\displaystyle \lceil N/2\rceil }](https://wikimedia.org/api/rest_v1/media/math/render/svg/9528d8146811294ff517620c66351acb3a3e4db4)
![{\displaystyle |N|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9becad1e12f3234bef53f3d619b7c9c8dfc2b5a)
![{\displaystyle 2^{N/2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c062cabe9e047674eaaa1e9566c52dd70cd86b2)
![{\displaystyle |N|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9becad1e12f3234bef53f3d619b7c9c8dfc2b5a)
Istorie
Conjectura a fost propusă de Peter Cameron și Pal Erdős în 1988 [1] , dovedită în 2003 de Ben Green [2] și independent de Alexander Sapozhenko [3] [4] .
Sapozhenko a arătat că pentru N par și pentru N impar, unde [5]![{\displaystyle s(N)=C_{0}2^{N/2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b18edcf824b252a3951dbe511617b493eeb60eab)
![{\displaystyle s(N)=C_{1}2^{(N+1)/2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ff7ced8c397348e73ad3a678dc8c278738b455b)
Link -uri
- ↑ Cameron, Peter Jephson & Erdős, Pal ( 1990 ), Despre numărul de mulțimi de întregi cu diverse proprietăți , Teoria numerelor: lucrările primei conferințe a Asociației Canadiane de Teorie a Numerilor, ținută la Centrul Banff, Banff, Alberta, aprilie 17-27, 1988 , Berlin: de Gruyter, p. 61–79 , < https://books.google.Com/books?id=68g0Ds4FNM0C&pg=PA61&lpg=PA61 > Arhivat la 27 iunie 2014 la Wayback Machine
- ↑ Green, Ben Joseph ( 2004 ), The Cameron-Erdős Conjecture , The Bulletin of the London Mathematical Society vol. 36 (6): 769–778 , DOI 10.1112/S0024609304003650
- ↑ Sapozhenko, Alexander Antonovich ( 2003 ), The Cameron-Erdős Conjecture, Rapoartele Academiei de Științe , Vol. 393 (6): 749–752
- ↑ Sapozhenko, Alexander Antonovich ( 2008 ), The Cameron-Erdős Conjecture , Discrete Mathematics T. 308 (19): 4361–4369 , DOI 10.1016/j.disc.2007.08.103
- ↑ Spectral and Evolution problems: Proceedings of the Fourenth Crimean Autumn Mathematical School-Symposium. Vol. 15. /Grupul autorilor.