Conjecture de Cameron-Erdős

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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, une 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[modifier | modifier le code]

Conjecture d'Erdős

Références[modifier | modifier le code]

  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, no 6,‎ 2003, p. 749–752.
  4. Alexander A. Sapozhenko, « The Cameron–Erdős conjecture », Discrete Mathematics, vol. 308, no 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)