19
$\begingroup$

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:

  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?

Improve this question
$\endgroup$
2

4 Answers 4

Reset to default
9
$\begingroup$

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".

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much. It seems that Lemma 1 in your mini-survey shows the existence of Hamilton cycles for finite Coxeter groups of rank 3. Maybe it's possible to adapt the proof for higher rank Coxeter groups. I will look into that. $\endgroup$
    – Johannes Hahn
    Commented Mar 21, 2012 at 15:03
  • $\begingroup$ I thought about it and indeed found a way to adapt that Lemma to the situation of a generating set $S$ of involutions with circle-free commuting graph (vertex-set: $S$, edges: between every non-commuting pair of vertices). This is satisfied for all finite Coxeter systems where these commuting graphs are just the dynkin-diagrams which are circle-free for finite Coxeter groups. Hence this is the existence result I was looking for. I'll also try to reformulate the proof into an algorithm. $\endgroup$
    – Johannes Hahn
    Commented Mar 22, 2012 at 18:46
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the article. It was indeed useful and I will probably implement that variant if the search for a general Hamilton-path-algorithm fails. $\endgroup$
    – Johannes Hahn
    Commented Mar 22, 2012 at 18:42
6
$\begingroup$

The answer to both questions is yes. See the paper of Conway, Sloane and Wilks called "Gray codes for reflection groups":

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

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .