Are there Hamilton paths in Cayley graphs of Coxeter groups? - MathOverflow

Are there Hamilton paths in Cayley graphs of Coxeter groups?

2012-03-20T16:35:20Z

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 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:

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

Answer by Nathan Reading for Are there Hamilton paths in Cayley graphs of Coxeter groups?

2012-03-20T19:04:07Z

I don't know about Hamilton cycles in this Cayley graph (although someone surely does, and I have a sneaking suspicion that I have heard about them and forgotten). So I'm not answering the question really, but I think this is the answer you want:

To efficiently "traverse" a finite Coxeter group (i.e. visit every element with low memory overhead), then you probably can't do better than the method in John Stembridge's article:

Computational Aspects of Root Systems, Coxeter Groups, and Weyl characters, in "Interactions of Combinatorics and Representation Theory" (pp. 1-38) MSJ Memoirs 11, Math. Soc. Japan, Tokyo, 2001.

You can get it on his website: http://www.math.lsa.umich.edu/~jrs

Look at Section 4. His traversal uses the Cayley graph explicitly, so it will be very compatible with what you're trying to do.

Stembridge has maple packages available for Coxeter group calculations:

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

I don't remember if maple code for the traversal is available on that website.

Answer by Igor Rivin for Are there Hamilton paths in Cayley graphs of Coxeter groups?

2012-03-20T19:22:07Z

There is a very nice survey by Dave Witte Morris here.

Answer by Igor Pak for Are there Hamilton paths in Cayley graphs of Coxeter groups?

2012-03-21T00:37:14Z

In fact, for any tree of transpositions in $S_n$ the corresponding Cayley graph is Hamiltonian. Start with my mini-survey with Radoicic 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 can be downloaded from the internet archive). See also Frank Ruskey's book "Combinatorial generation".