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(2^N/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 2^N/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 ∼ c₀ 2^N/2 si N est pair, et ∼ c₁ 2^N/2 si N est impair, où c₀ et c₁ 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, 1990, p. 61-79
2. Ben Green, « The Cameron–Erdős conjecture », Bulletin of the London Mathematical Society, vol. 36,‎ 2004, 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, n^o 6,‎ 2003, p. 749–752 (MR 2088503).
4. Alexander A. Sapozhenko, « The Cameron–Erdős conjecture », Discrete Mathematics, vol. 308, n^o 19,‎ 2008, 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).