Organizzare una serata… nel rispetto delle restrizioni sanitarie -------------------------------------------------
Il BDF ritiene che la festa sarà riuscita se almeno tre invitati si conoscono tra loro — perché sapranno così creare una buona atmosfera durante la serata — oppure se, al contrario, almeno tre invitati non si conoscono affatto — perché gli incontri sono sempre stimolanti. Consapevole dei rischi sanitari, il BDF desidera inoltre invitare il minor numero possibile di persone. Quanti invitati deve estrarre a sorte per rispettare tutti questi vincoli?
La risposta è 6. Ma quante persone avrebbe dovuto invitare se, anziché tre, il BDF avesse voluto garantire un gruppo di k invitati che si conoscessero tutti tra loro oppure, al contrario, che non si conoscessero affatto? In termini di teoria dei grafi, la questione si riformula così: determinare il kº numero diagonale di Ramsey R(k).
Forme e colori --------------------------
Traduciamo il problema del BDF in termini matematici. Rappresentiamo ogni invitato con un punto (un vertice) su un foglio, poi colleghiamo ogni coppia di punti con un tratto (un arco), rosso se i due invitati che rappresentano si conoscono, blu altrimenti. Abbiamo così costruito un grafo completo. Richiedere che esista un gruppo di tre persone che si conoscono tutte tra loro oppure un gruppo di tre persone che non si conoscono affatto equivale dunque a richiedere che, nel nostro grafo, vi siano tre punti collegati a due a due da archi rossi (un triangolo rosso) oppure tre punti collegati a due a due da archi blu (un triangolo blu). Determinare R(3) significa trovare il numero minimo di vertici che deve avere il grafo per garantire che, qualunque sia la colorazione degli archi, vi sia necessariamente un triangolo rosso o un triangolo blu. Cinque vertici non bastano, come mostra la figura a sinistra.