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
Références
- 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
- 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)
- Alexander A. Sapozhenko, « The Cameron-Erdős conjecture », Doklady Akademii Nauk, vol. 393, no 6, , p. 749–752 (MR 2088503).
- 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)