1 votos

Límites del número cromático del $\mathbb{R^n}$ grafo con distancia prohibida $1$

Tenemos el gráfico $G$ con un conjunto de vértices $\mathbb{R}^n$ ( $n \in \mathbb{N}^*$ ) y dos vértices cualesquiera tienen una arista si su distancia euclídea es igual a $1$ . Ahora dos puntos cualesquiera con una arista deben tener colores diferentes. El número cromático $\chi$ de un gráfico es el menor número de colores necesarios para colorear el gráfico. Los siguientes límites con $\zeta = 1.239...$ son conocidos:

$(\zeta + o(1))^n \leq \chi(G) \leq (3+o(1))^n$ .

Para cualquier función real $f$ tenemos $f \in o(1) \Leftrightarrow |f(x)| \rightarrow 0$ para $x\to \infty$ .

¿Puede alguien explicarme este resultado? O mejor, ¿alguien puede dar un ejemplo para algunos $n \in \mathbb{N^*}$ para que tengamos números naturales como límites?

1voto

kabenyuk Puntos 1

La fórmula que has dado fue demostrada por A. M. Raigorodskii (el límite inferior) y Larman-Rodgers (el límite superior).

Esta fórmula significa que el número cromático $\chi(\mathbb{R}^n)$ de la gráfica anterior crece como una función exponencial. En la literatura se pueden encontrar estimaciones más precisas del número cromático para pequeños $n\leq24$ . Por ejemplo, $5\leq\chi(\mathbb{R}^2)\leq7$ y $5\leq\chi(\mathbb{R}^3)\leq18$ .

Se puede encontrar un buen estudio en el libro de A. Soyfer "The mathematical coloring book", capítulo 10.

i-Ciencias.com

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.

Powered by:

X