Incrustar el Infinito Árbol Binario en Regular Apuntados

Question

Considere la posibilidad de regular mosaico $(m,n)$ en que $m$ $n$-agons cumplir en cada vértice. La mayoría de las veces, esta apuntados tienen que "vivir" en el plano hiperbólico. Los bordes de sus polígonos definir un gráfico en el que dos vértices son adyacentes si comparten una arista de un polígono. Me gustaría demostrar que la mayoría de estos gráficos tienen el infinito árbol binario como un subgrafo.

Por supuesto, sería imposible demostrar que esta para el suelo de baldosas $(4,4)$ debido a que la cantidad de vértices a una determinada distancia desde un vértice dado crece cuadráticamente, no de manera exponencial como en el árbol binario. Sin embargo, para la mayoría de las $(m,n)$ este crecimiento es exponencial y así al infinito árbol binario podría encajar. Al observar las imágenes de estos mosaicos esto parece completamente plausible, pero estoy teniendo problemas en la formalización de la misma.

He sido capaz de demostrar que este hecho ocurre en $(4,5)$. He intentado utilizar el grafo de Cayley de argumentos, pero se perdió. Así que, básicamente, tengo las siguientes preguntas:

• ¿Cómo puedo saber si el gráfico I se describe para la $(m,n)$ es el grafo de Cayley de un grupo? Y si es así, es el grafo de Cayley de un grupo bien conocido?
• Es mi Cayley argumento demasiado complicado y no es una simple prueba?
• ¿Tienes algún consejo para la elaboración de las $(m,n)$ mosaico?
• Me pueden ayudar con esta prueba, o me apunte a una teoría que puede ayudar?

Gracias de antemano! : )

Answer 1

Para terminar joriki la solución...

Ambos de estos algoritmos tienen la propiedad de que la región entre el subárbol izquierdo y el subárbol derecho es la misma forma en cada vértice del árbol. Tan sólo tenemos que demostrar que esta región es infinito, es decir, que los dos subárboles no colisionan.

En la primera foto, por ejemplo, la región tiene una infinita L de plazas como de sus límites.

Para demostrar que las cosas se ponen mejor con mayor m o n, considere la ruta que conecta los centros de los polígonos de tocar el límite (incluso con un vértice). El aumento de m o n sólo añadir que se convierte en la "caja fuerte" de la dirección (con lo que la región entre los subárboles aún más grande).

El mismo enfoque funciona para m≥4, n>4 algoritmo. Cuando n=5, las dos ramas de la L inicio de la misma (el ángulo es de 0°), pero pronto comienzan pesca en la dirección segura. (Incluso si no, la sola tira de n-ágonos sería suficiente para la separación de los dos subárboles.)

Más preguntas:

Esta pregunta podría ser podría ser frecuentes, no sólo para árboles binarios pero para q-ary árboles.

¿Hay alguna (m,n,q) combinaciones para que el árbol "sólo se ajusta a", es decir, no hay suficiente espacio entre los subárboles para colocar una línea infinita?

Answer 2

No estoy seguro de esto y no tengo una prueba formal, pero creo que la respuesta debería ser que esto es imposible iff $m\le3$ o $m=n=4$.

Para $m\le3$, miren esta imagen. (Tenga en cuenta que su ${p,q}$ se invierte con respecto a su $(m,n)$.) Si pones la raíz en algún vértice (es decir, el uno en el centro), todas las opciones para las dos primeras ramas son equivalentes. A partir de entonces, no hay opciones a la izquierda, y usted está obligado a ir alrededor de la una de la $n$-ágonos hasta dos hojas coinciden. Este será el caso cuando $m=3$. Obviamente, la situación es aún peor para $m=2$.

Para $m=n=4$, ya señalado por qué es imposible. Así que queda demostrado que es posible si $m>4$ o $n>4$.

Para $m>4$, miren esta imagen. Comenzando en el vértice en el centro, elegir dos bordes adyacentes y, a continuación, elija siempre el centro de los dos vértices de las cuatro opciones. Parece claro a partir de la imagen que estas ramas no chocan entre sí, y creo que no debería ser demasiado difícil de probar formalmente por la suma de los ángulos o algo por el estilo. Las cosas sólo pueden mejorar si aumenta el $m$ más, ya que se acaba de generar más ramificaciones entre los elegidos, y el aumento de la $n$ calabaza cosas en un ángulo más pequeño de la gama, pero no debería reducir las opciones para las ramas. (Soy consciente de que algunos de esto es bastante handwaving, pero se siente bien y podría señalar el camino hacia una prueba formal.)

Para $n>4$, miren esta imagen. (Este es el que ya ha demostrado que es posible.) Comenzando en el vértice en el centro, elige cualquiera de los dos bordes adyacentes. Cuando se llega a un vértice, optar siempre por el borde, que sigue recta y el que hace un giro hacia el hermano de rama. (Imaginar un letrero de la calle "rama Derecha gira a la izquierda". :-) Aquí, también, parece claro que estas ramas no se cumple, y que el aumento de $n$ o $m$ no se puede cerrar esta opción.