Teorema di Ramsey

Da Wikipedia, l'enciclopedia libera.

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 n1,...,nc esiste un numero R(n1,...,nc) tale per cui in ogni grafo con almeno R(n1,...,nc) vertici è sempre possibile trovare, per un certo i tra 1 e c, un sottografo completo con ni 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 una delle due seguenti alternative:

  • 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.

Il controesempio che dimostra che R(3,3)>5.

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 49 (inclusi).

Nella seguente tabella sono descritti i valori dei numeri di Ramsey conosciuti, e, per quelli sconusciuti, 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–49
6 1 6 18 36–41 58–87 102–165
7 1 7 23 49–61 80–143 113–298 205–540
8 1 8 28 58–84 101–216 132–495 217–1031 282–1870
9 1 9 36 73–115 126–316 169–780 241–1713 317–3583 565–6588
10 1 10 40–42 92–149 144–442 179–1171 289–2826 331–6090 581–12677 798–23556

Note[modifica | modifica wikitesto]

  1. ^ B. M. Landman, A. Robertson, pp. 5-6

Bibliografia[modifica | modifica wikitesto]

  • Bruce M. Landman, Aaron Robertson, Ramsey Theory on the Integers, American Mathematical Society, 2004, ISBN 0-8218-3199-2.
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica