Conjecture de Cameron-Erdős

En combinatoire, la conjecture de Cameron-Erdős est l'énoncé selon lequel le nombre d'ensembles sans somme contenus dans l'ensemble {1, … , N} est O(2N/2).

Comme la somme de deux entiers impairs est un entier pair, un ensemble d'entiers impairs est toujours sans somme. Il y a ⎡N/2⎤ entiers impairs inférieurs ou égaux à N, et il y a donc 2N/2 sous-ensembles de nombres impairs dans {1, … , N}. La conjecture de Cameron-Erdős affirme que ceci compte le nombre d'ensembles sans somme, à une constante multiplicative près.

La conjecture a été formulée par Peter J. Cameron et Paul Erdős en 1988[1]. Elle a été démontrée par Ben Green[2] et indépendamment par Alexander Sapozhenko[3]. Sapozhenko[4] donne une borne plus précise : le nombre de sous-ensembles sans somme est ∼ c0 2N/2 si N est pair, et ∼ c1 2N/2 si N est impair, où c0 et c1 sont des constantes.

Voir aussi

Conjecture d'Erdős

Références
  1. Peter J. Cameron et Paul Erdős, « On the number of sets of integers with various properties », dans R. A. Mullin (éditeur), Number Theory : Proceedings of the First Conference of the Canadian Number Theory Association (Banff, 1988), Berlin, de Gruyter, , p. 61-79
  2. Ben Green, « The Cameron–Erdős conjecture », Bulletin of the London Mathematical Society, vol. 36,‎ , p. 769-778 (DOI 10.1112/S0024609304003650, arXiv math.NT/0304058)
  3. Alexander A. Sapozhenko, « The Cameron-Erdős conjecture », Doklady Akademii Nauk, vol. 393, no 6,‎ , p. 749–752 (Math Reviews 2088503).
  4. Alexander A. Sapozhenko, « The Cameron–Erdős conjecture », Discrete Mathematics, vol. 308, no 19,‎ , p. 4361-4369 (DOI 10.1016/j.disc.2007.08.103)
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cameron–Erdős conjecture » (voir la liste des auteurs).
  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.