Teoria di Ramsey

La teoria di Ramsey, così chiamata dal nome di Frank Plumpton Ramsey, è un ramo della matematica discreta che si occupa di problemi della forma: qual è il minor numero di elementi necessario affinché una certa proprietà sia vera?

Esempi

La teoria di Ramsey si occupa di generalizzare il principio dei cassetti. Supponiamo, per esempio, che n piccioni siano stati sistemati in x piccionaie. Quanto grande deve essere n perché si possa essere sicuri che almeno una piccionaia contenga almeno due piccioni? Chiaramente, ciò avviene con certezza solo se $n>x$.

Un altro esempio è costituito dal teorema di Ramsey. Esso afferma che se coloriamo con un certo numero (fissato) di colori un grafo completo sufficientemente grande, esso conterrà un sottografo completo monocromatico (non banale). Ad esempio, nel caso si scelgano 2 colori, come rosso e blu, si ha che per n ≥ 6 ogni grafo completo di n vertici contiene almeno un triangolo (che non è altro che un grafo completo con 3 vertici) tutto blu o tutto rosso. Una forma equivalente e più intuitiva di questo caso è il fatto seguente: in una festa con almeno sei persone ci sono sempre almeno tre persone che tra loro si conoscono (cioè ciascuno conosce gli altri due) o che tra loro non si conoscono (cioè ciascuno non conosce gli altri due).

Bibliografia

• R. Graham, B. Rothschild, J.H. Spencer, Ramsey Theory, John Wiley and Sons, New York (1990)
• Landman and A. Robertson, Ramsey Theory on the Integers, Student Mathematical Library Vol. 24, AMS (2004)
• F. P. Ramsey, On a Problem of Formal Logic, Proc. London Math. Soc., Vol. s2-30, no 1 (1930),
• P. Erdös, G. Szekeres, A combinatorial problem in geometry, Compositio Math., Vol. 2, p. 463-470 (1935)
• G. Boolos, J. P. Burgess and R. Jeffrey, Computability and Logic, Cambridge: Cambridge University Press. (1974, rivisto nel 2004)

Collegamenti esterni

• (EN) Eric W. Weisstein, Teoria di Ramsey, su MathWorld, Wolfram Research.