Don't take life too seriously: it's just a temporary situation

Hadwiger – Nelson (problema di)

Geometria  Problemi 

Il problema di Hadwiger – Nelson, così chiamato perché discusso da Hugo Hadwiger e proposto da Edward Nelson nel 1950, chiede quale sia il minimo numero di colori necessari per colorare l’intero piano, in modo che due punti a distanza 1 siano di colori diversi.

 

Il grafo di Moser (v. numeri di Heawood) dimostra che 4 colori sono necessari e una tassellatura del piano con esagoni regolari che 7 sono sufficienti.

Per oltre 60 anni non sono stati fatti grandi progressi verso la soluzione del problema, poi nel 2014 Aubrey D.N.J. de Gray costruì un grafo di 20425 vertici, con archi di lunghezza 1, che richiede 5 colori; in seguito de Gray ridusse il numero di vertici a 1581. Non è noto quale sia il minimo numero di punti che richiedano 5 colori.

 

Il problema può essere formulato in 3 o più dimensioni, ma su tali varianti sa sa ben poco. In n dimensioni un grafo analogo a quello di Moser, con punti ai vertici di (iper)tetraedri, mostra che n + 2 colori sono necessari e una tassellatura tramite (iper)cubi dimostra che 3n – 2n – 1 colori sono sufficienti; nessuno però è riuscito a colmare il divario (crescente col numero di dimensioni) tra questi valori. Solo in 3 dimensioni sono stati fatti piccoli progressi, perché è stato dimostrato che 6 colori sono necessari e 15 sufficienti.

Vedi anche

Numeri di Heawood.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.