Ramsey-tala

Úr Wikipediu, frjálsa alfræðiritinu

Ramsey-talan R(m,n), þar sem m, n \in \mathbb{N}, n \geq 2, m \geq 2, er lágmarksfjöldi einstaklinga í veislu þar sem að lágmarki eru m pör vina eða n pör óvina, að því gefnu að allir í veislunni séu ýmist vinir eða óvinir. Sjá má að R(3,3) \leq 6.

Eiginleikar Ramsey-talna eru m.a. að R(m,n) = R(n,m). Ennfremur er R(2,n) = n fyrir allar jákvæðar heiltölur n \geq 2.

Eingöngu eru þekkt nákvæm gildi á 9 Ramsey-tölum, með 3 \leq m \leq n. Þær eru m.a. R(4,4) = 18, en ennfremur eru þekkt takmörk fyrir ýmsar Ramsey-tölur, t.a.m. 43 \leq R(5,5) \leq 49.

Ramsey-tölur eru nefndar eftir Frank Plumpton Ramsey, sem skilgreindi þær.