Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Conjecture de Cameron-Erdős
Résumé
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).
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 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 si N est pair, et ∼ c 2 si N est impair, où c et c sont des constantes.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.