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₁,...,n_c esiste un numero R(n₁,...,n_c) tale per cui in ogni grafo con almeno R(n₁,...,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[modifica | modifica wikitesto]

Nel seguente esempio vogliamo 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 consideriamo ogni persona come il vertice di un grafo completo, possiamo:

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. Stiamo 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. Prendiamo un gruppo di sei persone, che chiamiamo A, B, C, D ,E e F, e consideriamo 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 perdità di generalità, possiamo supporre che A ne conosca almeno tre, che scegliamo essere C, D e F. Se almeno due tra queste tre persone si conoscessero tra loro, per esempio C con F, avremmo trovato 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, abbiamo 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 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ò, disponiamo le 5 persone attorno ad un tavolo rotando, e supponiamo 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.^[1]

Numeri di Ramsey[modifica | modifica wikitesto]

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