Supongamos que se quiere colorear los puntos del plano de forma que dos puntos cualesquiera a una distancia de uno sean de distinto color. ¿Cuántos colores se necesitan?
Escuché este problema cuando era niño. Entonces lo máximo que sabía era que 3 es imposible y 7 es posible (hexágonos de baldosas de diámetro 1-ε). No he oído hablar de este problema desde entonces y no sé cómo buscarlo. ¿Se sabe más? ¿Es un problema muy conocido en ciertos círculos?
Esta es la Problema de Hadwiger-Nelson .
Recuerdo haber visto esto mientras pastoreaba por internet allá por el siglo XX. La frase pertinente para buscar en Google sería algo así como "número cromático del plano"; véase también esta página de la wikipedia.
Se trata del conocido problema del gráfico de la distancia unitaria. Si llamamos $U=U(\mathbb R^2)$ como el gráfico de distancia unitaria en el plano; es decir, los vértices son los puntos del plano y las aristas son los pares a distancia uno del otro.
Es bien sabido que $$4 \leq \chi(U(\mathbb R^2))\leq 7.$$
El límite inferior se encuentra dibujando un subgrafo de distancia unitaria finita de $U$ que tiene el número cromático 4 mientras que el límite superior se encuentra coloreando el plano con 7 colores después de dividirlo en hexágonos de un diámetro fijo y pequeño.
\medskip
Recientemente, me encontré con el estudio del índice cromático de un supergrafo de $U$ llamados gráficos de impar-distancia. Además, creo que este problema es equivalente a encontrar una medida de algún tipo, pero eso es todo lo que recuerdo.
Una vez intentamos utilizar las bases de Hammel del plano para llegar a una prueba que al menos mejora los límites anteriores, pero no parece funcionar (bueno, pudimos demostrar que $\mathbb Z$ es un dominio integral... divertido...).
Si se asume la mensurabilidad de los conjuntos correspondientes en la partición del plano, los límites son más estrictos. Véase, por ejemplo Límites inferiores para números cromáticos medibles , Geom. Funct. Anal. 19 (2009), 645-661.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
