Problemi di colorazione per tutte le età

Considerate n punti e collegateli tutti tra loro con archi di due colori a scelta (blu o rosso). Avete appena disegnato una 2-colorazione del grafo completo K_n . Con cinque punti, è possibile scegliere i colori in modo che nessun triangolo sia di un solo colore. In K₆ , invece, un triangolo monocromatico è inevitabile. Infatti, dal vertice A partono cinque archi e, poiché i colori possibili sono solo due, tre di essi — [AB], [AC] e [AD], per esempio — hanno lo stesso colore (poniamo il blu). Se BCD non è monocromatico, almeno uno dei suoi tre lati è blu e forma quindi un triangolo monocromatico con A.

Questi piccoli e divertenti problemi furono studiati alla fine degli anni Venti dal britannico Frank Plumpton Ramsey (1903–1930). La questione si generalizza così: qual è il più piccolo intero R(n) tale che ogni 2-colorazione di K_R(n) contenga necessariamente un sottografo K_n monocromatico?

Si ha R(3) = 6. Nel 1955 fu stabilito che R(4) = 18: in ogni 2-colorazione di K₁₈ esiste un sottografo completo monocromatico di ordine 4, ma non è così per K₁₇.

è monocromatico. Indicando con ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2\dots {\mathrm{\ell }}_3\backslash ell\_1,\backslash ell\_2\backslash ldots\backslash ell\_3$ le otto possibili lunghezze degli archi, si sono colorati di blu gli archi di lunghezza ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2\dots {\mathrm{\ell }}_4\backslash ell\_1,\backslash ell\_2\backslash ldots\backslash ell\_4$ e ${\mathrm{\ell }}_3\backslash ell\_3$ e di rosso gli altri.

Per i valori successivi si conoscono solo alcune stime: R(5) è compreso tra 43 e 49, e lavori recenti tendono a confermare il limite inferiore. Per R(10), il valore è compreso tra 798 e 23 556.