Cameron–Erdős-sejtés

A kombinatorika területén a Cameron–Erdős-sejtés (most már tétel) az az állítás, hogy $|N|=\{1,\dots ,N\}$ összegmentes részhalmazai száma $O\left(2^{N/2}\right).$

Ha a páratlan számok halmazát tekintjük: két páratlan szám összege mindig páros, így bármely, kizárólag páratlan számokat tartalmazó halmaz összegmentes. Az |N|-ben pontosan $\lceil N/2\rceil$ páratlan szám van, ezek részhalmazainak száma $2^{N/2}$. A Cameron–Erdős-sejtés azt mondja ki, hogy ez valamennyi összegmentes halmazra igaz.

A sejtést Peter Cameron és Erdős Pál fogalmazta meg 1988-ban. Ben Green, illetve tőle függetlenül Alexander Sapozhenko igazolta 2003-ban.

Kapcsolódó szócikkek

• Erdős Pál sejtéseinek listája