Ramsey-tala

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 48$.

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