¿Existen caminos de Hamilton en los grafos de Cayley de los grupos de Coxeter?

Question

Hola a todos.

Quiero optimizar ciertos cálculos en grupos Coxeter finitos $(W,S)$ . Básicamente calculo las matrices $\rho(T_w)$ para todos $w\in W$ de una representación matricial $H\to K^{d\times d}$ del álgebra de Hecke $H=\mathcal{H}(W,S)$ y hacer algunas cosas con estas matrices. La representación se da como una lista de las matrices $\rho(T_s)$ para $s\in S$ . La forma obvia de realizar dicho cálculo es utilizar la propiedad $l(ws)=l(w)+1 \implies T_{ws}=T_w T_s$ de la base estándar de $H$ para pasar de capa a capa en el grupo ("capa" significa conjuntos de la forma $\lbrace w\in W | l(w)=k\rbrace$ por el hecho de ser fijo $k$ ) y multiplicando las matrices $\rho(T_s)$ a los ya existentes.

Como también me interesan los ejemplos grandes, rápidamente me encuentro con problemas de memoria en este sentido porque para calcular el $\rho(T_w)$ con $l(w)=l$ uno tiene que almacenar todos los $\rho(T_y)$ con $l(y)=l-1$ que puede ser un número bastante grande si $l$ es alrededor de $\frac{1}{2}l_{max}$ . Aunque tengo acceso a una máquina con 128GB de RAM, esto es demasiado si $W$ y la dimensión de $\rho$ son grandes.

Hace unos días leí sobre los caminos de Hamilton en los grafos de Cayley. Esto solucionaría mi problema de memoria, porque si conociera un camino de Hamilton $w_1,\ldots,w_n$ Sólo tendría que almacenar la matriz única $\rho(T_{w_i})$ para calcular $\rho(T_{w_{i+1}})$ y olvidarse de ello después. Si tuviera acceso a un camino de Hamilton en el grafo de Cayley $\Gamma(W,S)$ Podría realizar mis cálculos utilizando sólo un poco más de memoria de la que ya necesito para la propia entrada.

Buscando en Google he visto que, en general, ni siquiera está claro si esas trayectorias de Hamilton existen siempre. Eso es bastante desafortunado, pero en el lado positivo también descubrí que hay un fácil algoritmo en el caso del grupo simétrico y su conjunto generador Coxeter. Así que espero que haya un resultado en el caso de los grupos Coxeter.

Así que mis preguntas son:

1. Si $(W,S)$ es un sistema Coxeter finito, ¿existe un camino de Hamilton en el grafo de Cayley $\Gamma(W,S)$ ?

2. Si este es el caso, ¿existe un algoritmo fácil para recorrer un camino de Hamilton?

Answer 1

No conozco los ciclos de Hamilton en este grafo de Cayley (aunque seguro que alguien los conoce, y tengo la ligera sospecha de que he oído hablar de ellos y los he olvidado). Así que no estoy respondiendo a la pregunta realmente, pero creo que esta es la respuesta que quieres:

Para "atravesar" eficientemente un grupo Coxeter finito (es decir, visitar cada elemento con poca sobrecarga de memoria), probablemente no se puede hacer nada mejor que el método del artículo de John Stembridge:

Aspectos computacionales de los sistemas de raíces, grupos de Coxeter y caracteres de Weyl, en "Interactions of Combinatorics and Representation Theory" (pp. 1-38) MSJ Memoirs 11, Math. Soc. Japan, Tokio, 2001.

Puedes conseguirlo en su página web: http://www.math.lsa.umich.edu/~jrs

Mira la sección 4. Su travesía utiliza el grafo de Cayley explícitamente, por lo que será muy compatible con lo que estás tratando de hacer.

Stembridge dispone de paquetes de maple para el cálculo de grupos Coxeter:

http://www.math.lsa.umich.edu/~jrs/maple.html

No recuerdo si el código de maple para la travesía está disponible en ese sitio web.

Answer 2

De hecho, para cualquier árbol de transposiciones en $S_n$ el correspondiente gráfico de Cayley es hamiltoniano. Empezamos con mi mini-encuesta con Radoicic que es relativamente reciente. El tipo de ciclos hamiltonianos que le interesan se explican mejor en "El arte de la programación informática" de Don Knuth, Vol. 4, Fascículo 2b ("Generar todas las permutaciones") ( versión preliminar puede descargarse del archivo de Internet). Véase también el libro de Frank Ruskey "Generación combinatoria" .

Answer 3

La respuesta a ambas preguntas es sí. Véase el artículo de Conway, Sloane y Wilks titulado "Gray codes for reflection groups":

http://link.springer.com/article/10.1007/BF01788686

Answer 4

Hay una encuesta muy bonita de Dave Witte Morris aquí.