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, ma nell’ultimo mezzo secolo non sono stati fatti grandi progressi verso la soluzione del problema.

 

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.