# Teorema di Ramsey

In combinatoria, il teorema di Ramsey afferma che per ogni colorazione degli archi di un grafo completo con un numero abbastanza elevato di vertici è possibile trovare un sottografo completo monocromatico.
Nel caso in cui il grafo sia colorato con soli due colori, per esempio rosso e blu, il teorema di Ramsey afferma che comunque scelti due interi positivi r e s esiste un intero R(r,s) tale per cui in un grafo completo con almeno R(r,s) vertici è sempre possibile, per qualunque colorazione, trovare un sottografo completo totalmente blu con r vertici, o un sottografo completo totalmente rosso con s vertici. Il numero R(r,s) è da intendersi come il più piccolo intero per cui vale questa proprietà, e viene chiamato numero di Ramsey.
Il teorema di Ramsey è valido anche per più di due colori: scelto un numero c di colori, per qualunque scelta di interi positivi n$_1$,...,n$_c$ esiste un numero R(n$_1$,...,n$_c$) tale per cui in ogni grafo con almeno R(n$_1$,...,n$_c$) vertici è sempre possibile trovare, per un certo i tra 1 e c, un sottografo completo con n$_i$ vertici totalmente colorato con il colore i.
Il teorema di Ramsey è un risultato fondamentale in combinatoria. La prima versione fu dimostrata da Frank P. Ramsey, e diede inizio a quella che è chiamata teoria di Ramsey.

## Esempio: R(3,3)=6

Nel seguente esempio si vuole trovare il numero minimo di persone necessarie per fare in modo che si verifichi sempre almeno una delle due seguenti possibilità:
* Tre persone si conoscono reciprocamente.
* Tre persone sono tra loro completamente estranee.
Se si considera ogni persona come il vertice di un grafo completo, si può:
* Colorare di rosso lo spigolo che le unisce se queste si conoscono.
* Colorare di blu lo spigolo che le unisce se queste non si conoscono.
Il problema diventa quindi trovare il numero minimo di vertici necessari per fare in modo che esista sempre un triangolo (sottografo completo con 3 vertici) totalmente rosso o totalmente blu. Si sta quindi cercando di dare un valore al numero di Ramsey R(3,3).
È facile dimostrare che nel caso di sei persone le due alternative si verificano sempre, e quindi che il numero di Ramsey R(3,3) è più piccolo o uguale a 6. Si prenda un gruppo di sei persone, che si chiamano A, B, C, D ,E e F, e si consideri A. Poiché ci sono altre cinque persone, si verifica sempre che o A ne conosce almeno tre tra queste, oppure A non ne conosce almeno tre. Senza perdita di generalità, si può supporre che A ne conosca almeno tre, ad esempio C, D e F. Se almeno due tra queste tre persone si conoscessero tra loro, per esempio C con F, si sarebbero trovate tre persone, A, C ed F che si conoscono reciprocamente (e formano un triangolo rosso nel grafo). Se invece queste tre persone non si conoscono, si è trovato un gruppo di tre persone che sono tra loro completamente estranee (e formano un triangolo blu nel grafo). Comunque vada, quindi, una delle due opzioni alternative deve avverarsi.
In realtà, il numero di Ramsey R(3,3) è proprio uguale a 6: è infatti possibile trovare un gruppo di 5 persone in cui nessuna delle due alternative si verifica. Per fare ciò, si dispongono le 5 persone attorno ad un tavolo rotondo, e si suppone che ognuna conosca solo le persone sedute al proprio fianco. In questo modo, ognuno conosce esattamente due persone, e esattamente due persone gli sono estranee. Nessuna delle due alternative si verifica. Graficamente, questa costruzione si può visualizzare come un grafo in cui i lati esterni sono tutti colorati di rosso, mentre i lati interni sono tutti colorati di blu. Questo controesempio dimostra che R(3,3)=6.

## Numeri di Ramsey

I numeri R(r,s) presenti nel teorema di Ramsey, ed anche la loro estensione a più colori, sono detti numeri di Ramsey. La dimostrazione del teorema fornisce da sé un limite superiore per ognuno di questi numeri, e limiti inferiori possono essere trovati attraverso altri metodi. (Il primo limite inferiore è stato ottenuto da Paul Erdős usando un metodo probabilistico). Generalmente vi è però un grande differenza tra i due limiti, e il valore esatto del numero di Ramsey R(r,s) è conosciuto solo per pochi casi.
È utile notare che, siccome l'ordine dei colori non è importante, invertire i due valori r e s non cambia il numero di Ramsey a loro associato, ovvero R(r,s)=R(s,r). Più in generale, nel caso di più di due colori, qualunque permutazione dei valori non cambia il numero di Ramsey (per esempio, R(2,4,7)=R(7,2,4)).
Come descritto in precedenza, R(3,3)=6. È facile dimostrare che R(r,2)=r per ogni r (e lo stesso vale per R(2,r)). Sono anche conosciuti R(4,3)=9 e R(4,4)=18, e R(3,r) fino a r=9. Gli altri valori esatti sono ancora sconosciuti, e si conoscono solo dei limiti superiori e inferiori. Per esempio, è stato dimostrato che R(5,5) si trova tra 43 e 48 (inclusi).
Nella seguente tabella sono descritti i valori dei numeri di Ramsey conosciuti, e, per quelli sconosciuti, i migliori limiti inferiore e superiore.
| r,s | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | | | | | | | | | |
| 2 | 1 | 2 | | | | | | | | |
| 3 | 1 | 3 | 6 | | | | | | | |
| 4 | 1 | 4 | 9 | 18 | | | | | | |
| 5 | 1 | 5 | 14 | 25 | 43–48 | | | | | |
| 6 | 1 | 6 | 18 | 36–40 | 59–85 | 102–161 | | | | |
| 7 | 1 | 7 | 23 | 49–58 | 80–133 | 115–273 | 205–497 | | | |
| 8 | 1 | 8 | 28 | 59–79 | 101–194 | 134–427 | 219–840 | 282–1532 | | |
| 9 | 1 | 9 | 36 | 73–106 | 133–282 | 183–656 | 252–1379 | 329–2683 | 565–5366 | |
| 10 | 1 | 10 | 40–41 | 92–136 | 149–381 | 204–949 | 292–2134 | 343–4432 | 581–9797 | 798–17730 |