Are there Hamilton paths in Cayley graphs of Coxeter groups? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T11:31:13Z http://mathoverflow.net/feeds/question/91734 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91734/are-there-hamilton-paths-in-cayley-graphs-of-coxeter-groups Are there Hamilton paths in Cayley graphs of Coxeter groups? Johannes Hahn 2012-03-20T16:35:20Z 2012-03-21T00:37:14Z <p>Hi everyone.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm" rel="nofollow">algorithm</a> 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.</p> <p>So my questions are:</p> <ol> <li><p>If $(W,S)$ is a finite Coxeter system, does there exists a Hamilton path in the Cayley graph $\Gamma(W,S)$?</p></li> <li><p>If this is indeed the case, is there an easy algorithm to traverse a Hamilton path?</p></li> </ol> http://mathoverflow.net/questions/91734/are-there-hamilton-paths-in-cayley-graphs-of-coxeter-groups/91746#91746 Answer by Nathan Reading for Are there Hamilton paths in Cayley graphs of Coxeter groups? Nathan Reading 2012-03-20T19:04:07Z 2012-03-20T19:04:07Z <p>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:</p> <p>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:</p> <p>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.</p> <p>You can get it on his website: <a href="http://www.math.lsa.umich.edu/~jrs" rel="nofollow">http://www.math.lsa.umich.edu/~jrs</a></p> <p>Look at Section 4. His traversal uses the Cayley graph explicitly, so it will be very compatible with what you're trying to do. </p> <p>Stembridge has maple packages available for Coxeter group calculations:</p> <p><a href="http://www.math.lsa.umich.edu/~jrs/maple.html" rel="nofollow">http://www.math.lsa.umich.edu/~jrs/maple.html</a></p> <p>I don't remember if maple code for the traversal is available on that website.</p> http://mathoverflow.net/questions/91734/are-there-hamilton-paths-in-cayley-graphs-of-coxeter-groups/91748#91748 Answer by Igor Rivin for Are there Hamilton paths in Cayley graphs of Coxeter groups? Igor Rivin 2012-03-20T19:22:07Z 2012-03-20T19:22:07Z <p>There is a very nice survey by Dave Witte Morris <a href="http://people.uleth.ca/~dave.morris/talks/HamCycCayGrf-Newark.pdf" rel="nofollow">here.</a></p> http://mathoverflow.net/questions/91734/are-there-hamilton-paths-in-cayley-graphs-of-coxeter-groups/91774#91774 Answer by Igor Pak for Are there Hamilton paths in Cayley graphs of Coxeter groups? Igor Pak 2012-03-21T00:37:14Z 2012-03-21T00:37:14Z <p>In fact, for any tree of transpositions in $S_n$ the corresponding Cayley graph is Hamiltonian. Start with <a href="http://www.math.ucla.edu/~pak/papers/hamcayley9.pdf" rel="nofollow">my mini-survey with Radoicic</a> 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") (<a href="http://tinyurl.com/yfo57t4" rel="nofollow">preliminary version</a> can be downloaded from the internet archive). See also Frank Ruskey's book <a href="http://www.1stworks.com/ref/RuskeyCombGen.pdf" rel="nofollow">"Combinatorial generation"</a>.</p>