Conjectura de Cameron–Erdős

La conjectura de Cameron-Erdős, en combinatòria, la van enunciar Peter Cameron i Paul Erdős el 1988.[1] La van demostrar Ben Green[1] i independentment Alexander Sapozhenko[2][3] el 2003.

La conjectura afirma que el nombre de conjunts suma lliure continguts en | N | = { 1 , … , N } {\displaystyle |N|=\{1,\ldots ,N\}} és O ( 2 N / 2 ) . {\displaystyle O\left({2^{N/2}}\right).} La suma de dos nombres senars és parell, per tant un conjunt suma de conjunts de nombres senars és sempre suma lliure. Hi ha ⌈ N / 2 ⌉ {\displaystyle \lceil N/2\rceil } nombres senars a|N|, i per tant 2 N / 2 {\displaystyle 2^{N/2}} subconjunts de nombres senars en|N|. La conjectura de Cameron-Erdős diu que això compta una proporció constant de conjunts suma lliure.

Notes

  1. ↑ 1,0 1,1 B. Green, "The Cameron-Erdős conjecture", Bulletin of the London Mathematical Society 36 (2004) pp. 769-778. 2003 arXiv preprint
  2. ↑ A. Sapozhenko, "The Cameron-Erdős conjecture", Doklady Mathematics 68:3 (2003), p. 438.
  3. ↑ Sapozhenko, Alexander A. «The Cameron-Erdős conjecture». Discrete Mathematics, 308, 19, 2008, p. 4361–4369. DOI: 10.1016/j.disc.2007.08.103.