Hi everyone.


I want to optimize certain computation on finite Coxeter groups $(W,S)$. Basically I compute the matrices $\rho(T\_w)$ for all $w\in W$ of a matrix representation $H\to K^{d\times d}$ of the Hecke algebra $H=\mathcal{H}(W,S)$ and do some stuff with these matrices. The representation is given as a list of the matrices $\rho(T\_s)$ for $s\in S$. The obvious way to do such a computation is to use the property $l(ws)=l(w)+1 \implies T\_{ws}=T\_w T\_s$ of the standard basis of $H$ to move from layer to layer in the group ("layer" meaning sets of the form $\lbrace w\in W | l(w)=k\rbrace$ for fixed $k$) and by multiplying the matrices $\rho(T\_s)$ to the existing ones.


Since I'm also interested in big examples, I quickly run into trouble with my memory in this way because to compute the $\rho(T\_w)$ with $l(w)=l$ one has to store all the $\rho(T\_y)$ with $l(y)=l-1$ which can be quite a big number if $l$ is around $\frac{1}{2}l\_{max}$. Even though I have access to a machine with 128GB RAM, this is too much if $W$ and the dimension of $\rho$ are big.


A few days ago I read about Hamilton paths in Cayley graphs. This would solve my memory problem, because if I knew a Hamilton path $w\_1,\ldots,w\_n$ I would only need to store the single matrix $\rho(T\_{w\_i})$ to compute $\rho(T\_{w\_{i+1}})$ and forget about it afterwards. If I had access to a Hamilton path in the Cayley graph $\Gamma(W,S)$ I could carry out my calculations with using only little more memory than I already need for the input itself.


Googling showed my that in general it is not even clear if such hamilton paths always exists. That's rather unfortunate, but on the positive side I also found out that there is an easy [algorithm](http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm) in case of the symmetric group and its Coxeter generating set. So I'm hoping that there is a result in the case of Coxeter groups.


So my questions are:


1. If $(W,S)$ is a finite Coxeter system, does there exists a Hamilton path in the Cayley graph $\Gamma(W,S)$?
2. If this is indeed the case, is there an easy algorithm to traverse a Hamilton path?



Are there Hamilton paths in Cayley graphs of Coxeter groups?
In fact, for any tree of transpositions in $S\_n$ the corresponding Cayley graph is Hamiltonian. Start with [my mini-survey with Radoicic](http://www.math.ucla.edu/~pak/papers/hamcayley9.pdf) which is relatively recent. The type of Hamiltonian cycles you are interested in are best explained in Don Knuth's "Art of Computer Programming", Vol. 4, Fascicle 2b ("Generating all permutations") ([preliminary version](http://tinyurl.com/yfo57t4) can be downloaded from the internet archive). See also Frank Ruskey's book ["Combinatorial generation"](http://www.1stworks.com/ref/RuskeyCombGen.pdf).


