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. 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 ∼ 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
- Portail des mathématiques
