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¹. Elle a été démontrée par Ben Green² et indépendamment par Alexander Sapozhenko³. Sapozhenko⁴ 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[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 [archive] », 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.
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).

• Portail des mathématiques

Source : wikipedia