número cromático del plano hiperbólico

Question

Un problema notorio en la combinatoria es la siguiente:

Si tenemos en color $\mathbb{R}^2$, de modo que ningún par de puntos por unidad de distancia de obtener el mismo color, ¿cuál es el menor número de colores necesarios?

Este número es a veces llamado "el cromática número del plano" $\chi$ (ya que es realmente un gráfico para colorear problema en un infinito gráfico), y es fácil ver que $ 4 \le \chi \le 7$, pero estos límites se han mantenido durante bastante tiempo.

Es natural preguntarse acerca de la coloración de otros espacios métricos, y muchas personas tienen. En particular, hay límites conocidos para el cromática número de $\mathbb{R}^d$ para $d \ge 3$ (y algunos asymptotics como $d \to \infty$). También ha habido algunos trabajos sobre la coloración de las dos dimensiones de la esfera de radio $r$. (Una buena referencia para este tipo de problema es Soifer "La matemática de libro para colorear.")

Mi pregunta es si alguien los ha visto en la cromática número del plano hiperbólico. Como con la esfera, no es un parámetro libre --- uno podría tomar fijo curvatura $-1$ y dejar que la distancia variar, o la revisión de la unidad de distancia y dejar que la curvatura negativa constante variar.

Que no podría esperar a ser capaz de resolver este en general, ya que la determinación de la cromática número del plano parece difícil, y ahora tenemos una familia infinita de tales problemas. Pero deberíamos ser capaces de poner límites, y me estoy preguntando lo que es conocido.

En particular, las siguientes dos preguntas vienen a la mente. Agradecería ideas o sugerencias a las referencias si estas cosas han sido previamente estudiados.

(1) hay un $5$-cromática unidad de distancia gráfica en el plano hiperbólico (para algunos curvatura negativa constante)?

(2) ¿existe un límite superior absoluto en el cromática número de la hiperbólico el avión, que se mantiene constante para todos negativo curvaturas?

Uno podría pensar que la cromática número del plano hiperbólico aumenta a medida que la curvatura negativa constante disminuye, pero si lo hace crecer sin límite?

Answer 1

Esto en realidad no responder a sus preguntas, pero hace poco tuve un par de resultados en el cromática número de los planos hiperbólicos. Están formulados por la fijación de la curvatura y dejar que la distancia varían, y yo uso la notación $\chi(\mathbb{H}^2,\{d\})$ para el cromática número de la distancia-$d$ gráfico en el plano hiperbólico con curvatura $-1$.

1. para los pequeños $d$, $\chi(\mathbb{H}^2,\{d\})\leq 12$ (esto probablemente puede ser mejorado, pero tal vez no fácilmente a $7$),

2. para grandes $d$, $\chi(\mathbb{H}^2,\{d\})\leq \frac{4}{\ln 3} d + O(1)$.

Las pruebas a las que se puede encontrar aquí: https://arxiv.org/abs/1305.2765publicado en Geombinatorics Vol XXIV (3) 2015, pp 117-134 (pero la prueba de la lineal límite superior tiene algunos pequeños problemas, se corrige con una mejora de la une en el trabajo posterior de Parlier y Petit https://arxiv.org/abs/1701.08648). Todo esto no es difícil, y el papel que plantea más preguntas que respuestas.

Mi impresión es que la monotonía cromática número de con $d$ parece razonable, pero que en realidad es un problema sutil; y prefiero apostar a una respuesta negativa a la pregunta (2), pero no demasiado alto. Con todo, estas preguntas son probablemente muy difícil, porque tenemos muy engorroso herramientas necesarias para relacionar la geometría con la distancia gráfica.

Para la historia: alrededor de un año después de leer, les gustó y de marcado su pregunta, me había olvidado de él, pero leer "Teoría de Ramsey, de Hoy y de Mañana", y se dio cuenta de que yo pudiera responder algunas preguntas en el mismo por Johnson y Szlam. En el curso de la redacción de un documento a partir de estas respuestas, he investigado el caso del plano hiperbólico. Después de escribir una primera versión, se me ocurrió mirar en mis MO favoritos, y vio a su pregunta de nuevo-que es, por tanto, citado en el papel (¿habrá pronto un @mathoverflow en el estándar de bibTeX definiciones?)

Answer 2

Curiosamente, Soifer Matemáticos para Colorear Libro no menciona esta variante, y me gustaría pensar que él habría si algo se sabe sobre ella.

No sé mucho más de mí mismo, pero por lo menos puedo relacionar a otro problema conocido, Ringel círculo de problema en cuanto a la cromática número de sistemas de círculos, sin tres de la tangente en un punto único, con pares de círculos tangentes se requiere tener diferentes colores. Ringel preguntó si la cromática número de estos sistemas es limitada. Existen sistemas de círculos de donde es, al menos, cinco; ver, por ejemplo, http://www.ics.uci.edu/~eppstein/depósito de chatarra/tangencies/

Para los sistemas de círculos, no importa si usted está utilizando hiperbólica o de la geometría Euclidiana - los círculos son el mismo. Así que si usted puede encontrar un hiperbólico conjunto de puntos cuya unidad de distancia gráfico requiere más de cinco colores, a continuación, el sistema de círculos de radio 1/2 centrado en los puntos a mejorar de la conocida límite inferior en el círculo de problema. Por otro lado, si usted puede demostrar que Ringel círculo del problema tiene un límite superior finito, entonces lo haría el plano hiperbólico.

Answer 3

Un nuevo artículo sobre el tema ha aparecido, y aunque no responder a su pregunta, debo encontrar el resultado lo suficientemente interesante como para ser mencionado en una de respuestas separada.

DeCorte y Golubev probar ahí que para $r$ lo suficientemente grande ($r\ge 12$ es suficiente), la distancia a-$r$ gráfico del plano hiperbólico con curvatura $\kappa=-1$ ha medibles cromática número mínimo de $6$ (aquí "medibles" significa que los mapas envío de un punto a su color es Lebesgue Medible). Es sabido por mucho tiempo que la medibles cromática punto de que el avión es, al menos, $5$ (Falconer 1981), por lo que el punto interesante aquí es que el límite inferior se pone mejor para grandes distancias (es decir, por muy curvatura negativa, si se prefiere arreglar $r=1$ y deje $\kappa$ atropellado $(-\infty,0)$).

Tenga en cuenta que bajo el Solovay axiomas, la medibles hipótesis pueden ser retirados ya que todos los conjuntos son Lebesgue medibles (pero luego no tenemos la plena axioma de elección, y por lo tanto no DeBruin-Erdös teorema: no podemos deducir que en virtud de la Solovay axiomas hay un número finito de la unidad de distancia gráfico cuya cromática número es al menos $6$).