Ramsey, teoria di
Ramsey, teoria di
Ramsey, teoria di branca autonoma della matematica discreta e dell’analisi combinatoria che muove dai lavori di F.P. Ramsey nei primi decenni del secolo scorso e fu successivamente sviluppata da P. Erdős. Intuitivamente, i principi cui si ispira la teoria si basano sull’idea che un sistema sufficientemente largo di oggetti contenga al suo interno un sottosistema con un grado di organizzazione maggiore del sistema dato. Banalmente, per esempio, il principio dei cassetti (o pigeonhole principle, cioè principio della piccionaia) afferma che se si devono disporre n + k oggetti in n cassetti (con n e k ovviamente interi positivi) deve esistere almeno un cassetto contenente più di un oggetto. Tale principio, che si basa sull’enumerazione in insiemi a cardinalità finita, per quanto banale, conduce a risultati sorprendenti: in base a esso, infatti, si dimostra immediatamente che, nel mondo, esistono almeno due persone con lo stesso numero di capelli (giacché la cardinalità dell’insieme della popolazione vivente eccede largamente il numero massimo di capelli, che G. Peano, il quale aveva proposto il problema, stimò in circa 150.000). Ai risultati generali di Ramsey, ci si può avvicinare con il seguente problema: da quanti R nodi deve essere al minimo formato un grafo completo A (si può pensare agli R vertici di un poligono e a tutti i suoi lati e diagonali) in modo tale che, scelti k = 2 colori (per esempio F1 = blu e F2 = rosso), si possano colorare i suoi archi (che sono coppie di vertici, cioè sottoinsiemi di A con n = 2 elementi) in modo tale che, scelti k numeri, per esempio q1 = 3 e q2 = 3, un sottoinsieme Ai formato da qi elementi (cioè un sottografo con 3 nodi) abbia tutti i suoi lati o rossi o blu? Tale numero è indicato con Rn(q1, q2) e nell’esempio R2(3, 3) = 6. Talvolta, questo problema è formulato in altro modo, affermando che in una festa con N ≥ 6 persone, o ci sono 3 persone che si conoscono tra loro oppure ci sono 3 persone che non si conoscono. Il risultato è un caso particolare dei più generali teoremi di Ramsey, locuzione con la quale si indicano numerosi teoremi di matematica discreta da lui formulati e dimostrati.
Teorema di Ramsey nel caso finito
Sia A un insieme contenente m elementi e sia F la famiglia di tutti i sottoinsiemi di A contenenti esattamente n elementi (con n < m). Si decomponga tale famiglia in k sottofamiglie disgiunte F1, ..., Fk, non importa come, e siano q1, ..., qk degli interi tali che, per ogni i, qi ≥ n ≥ 1; allora esiste un minimo numero Rn(q1, ..., qk), successivamente chiamato numero di Ramsey, tale che se N ≥ Rn(q1, ..., qk), allora per qualche i = 1, ..., k esiste un sottoinsieme Ci di A, con qi elementi, che ha tutti i suoi sottoinsiemi di n elementi nella sottofamiglia Fi.
Teorema di Ramsey nel caso infinito
Fu questo il primo dei teoremi dimostrati da Ramsey, utilizzando l’assioma della → scelta, da cui si deduce anche quello nel caso finito. Se A è un insieme numerabile, k e n due interi positivi e si considerano tutte le n-ple formate con elementi di A (cioè la famiglia F formata da tutti i sottoinsiemi di A con n elementi), ripartiti a loro volta, ma non importa come, in k sottoinsiemi disgiunti Fi, con i = 1, ..., k, allora A contiene un sottoinsieme infinito Ci tale che tutte le n-ple di Ci appartengono a qualche Fi.
Si osservi che i teoremi di Ramsey sono teoremi di esistenza non costruttivi. E, in effetti, il problema di determinare i numeri di Ramsey presenta un’elevata complessità. Esistono tuttavia alcuni risultati parziali: per esempio R2(4, 4) = 18, R2(4, 5) = R2(5, 4), ma già per R2(5, 5) si conosce a oggi [2013] soltanto l’intervallo cui deve necessariamente appartenere: 43 ≤ R2(5, 5) ≤ 49. Per n = 3 (che corrisponderebbe a una colorazione con 3 colori di un grafo completo) si conosce soltanto R3(3, 3) = 17.