Descripción del mosaico cuadrado de orden 5 del plano hiperbólico como gráfico

Question

¿Cuál es la descripción del gráfico que representa las caras del Ordenar 5 baldosas cuadradas . Alternativamente, esto puede ser visto como el gráfico de vértices de su dual, el Ordenar 4 pentágonos .

Preferiblemente, debería ser una descripción útil para usar con un ordenador (todo lo que se necesita es una forma de encontrar los vecinos de cualquier nodo). La razón por la que se interesó en el uso de la geometría hiperbólica en los juegos, así que como un atajo a todo el cálculo necesario decidí que haría un montón de habitaciones correspondientes a una teselación del plano hiperbólico (y aproximar cada habitación como euclidiana).

Además, esta descripción debería ser discreta (es decir, no depender de números reales (que habría que aproximar con números flotantes en un ordenador))

Answer 1

(Trabajar con grupos era demasiado difícil, así que decidí utilizar un enfoque diferente, tomando una hoja de HyperRogue de los libros).

Comenzamos construyendo un árbol de expansión para el grafo. Su aspecto es el siguiente, salvo que es infinito:

Cada camino desde la raíz hasta un vértice del gráfico se describe mediante un paso inicial hacia el Norte, el Este, el Sur o el Oeste, seguido de una secuencia de pasos hacia delante, hacia la izquierda o hacia la derecha. De hecho, todo Los caminos desde la raíz pueden describirse de este modo, pero los caminos que corresponden a las aristas de este árbol de expansión cumplen dos condiciones más:

1. No puedes dar dos pasos consecutivos hacia la derecha.

2. No puedes dar dos pasos a la izquierda sin un paso a la derecha en medio.

   (Izquierda, Izquierda e Izquierda, Adelante, Izquierda e Izquierda, Adelante, Adelante, Izquierda y así sucesivamente están prohibidos).

En cada cuarto del árbol, el número de vértices a una profundidad determinada parece estar dado por la secuencia A033303 en la OEIS.

Para especificar un vértice en el grafo, especificamos el camino desde la raíz hasta ese vértice.

De los cuatro vecinos de un vértice, al menos tres son vecinos en el árbol, y son fáciles de encontrar. Sólo tenemos que tomar el camino que especifica nuestro vértice, y hacer uno de:

• Borrar el último paso, o
• Añade un paso a la izquierda, al frente o a la derecha.

Sin embargo, a veces obtenemos una arista no arbórea de este modo: esto sucede exactamente cuando damos uno de los pasos prohibidos anteriormente. En ese caso, tenemos que simplificar el resultado a un camino que es válido en el árbol.

Dejemos que $\ell$ es la función que "gira una dirección a la izquierda", asignando Norte a Oeste, Oeste a Sur, Sur a Este, Este a Norte, Derecha a Avance y Avance a Izquierda; sea $r$ sea su inversa. (Los valores $\ell(\text{Left})$ y $r(\text{Right})$ son ambos indefinidos). Entonces:

1. El final prohibido " $\dots, x$ , Derecho, Derecho" se simplifica a la terminación " $\dots, r(x)$ , "Izquierda".
2. El final prohibido " $\dots, x$ , Izquierda, Izquierda" se simplifica a la terminación " $\dots, \ell(x)$ , Derecho".
3. El final prohibido $\dots, x$ , Izquierda, Adelante, Izquierda" se simplifica a la terminación $\dots, \ell(x)$ , Derecha, Adelante, Derecha".
4. En general, la terminación prohibida " $\dots, x$ , Izquierda, Adelante, ..., Adelante, Izquierda" se simplifica a la terminación " $\dots, \ell(x)$ . Derecha, Adelante, ..., Derecha, Adelante, Derecha", con igual número de pasos hacia adelante que antes intercalados con pasos hacia la derecha.

Answer 2

Puede representar esto como el $\Delta(2,4,5)$ Grupo Von Dyck .

En particular, se puede generar el grupo por

• Girar a la izquierda 90 grados ( $L$ )
• Girar a la derecha 90 grados ( $R$ )
• Avanza una casilla y luego da la vuelta ( $F$ )

Dada una cadena de símbolos de este tipo, podemos simplificarla a una forma normal con las siguientes operaciones:

• Sustituir $L^2$ con $R^2$
• Eliminar $F^2$
• Sustituir $R^3$ con $L$
• Sustituir $(FL)^2F$ con $(RF)^2R$
• Sustituir $FLFR^2(FL)^2$ con $RF(RFR)^2F$
• Sustituir $(FLFR^2)^2$ con $RF(RFR)^2FL$

(generado con sagemath).

Dos representaciones cualesquiera del mismo elemento en el grupo de Von Dyck se normalizarán al mismo resultado bajo estas operaciones.

Por último, hay que tener en cuenta que cada elemento representa tanto un cuadrado como una dirección. Por lo tanto, diremos que dos elementos representan el mismo cuadrado ignorando $R$ y $L$ al principio de la cadena.

Dos celdas son adyacentes si se puede pasar de una a otra con cero a tres $R$ operaciones y exactamente una $F$ operación.