Cayley Graphs of Coxeter Groups

Race Against Time

2008-04-04T07:48:00.000-07:00

(this entry was to mostly map out my thoughts so I don't get lost
within the next few weeks. Sorry if I don't explain some
or any of the terms I use).

Reading papers is easy ... Reading and Understanding papers is hard.
I currently have about a month (possibly more time but I'm using a
month for approximation purposes) to complete my thesis.
Needless to say, I somewhat underestimated how long it would
take me to get exactly what Casselman was saying in his papers.

Right now I can sum up where I am so far as this:
The key to building the Cayley Graph lies in being
able to do multiplication of a group element by a generator.

Casselman's first paper proposes a group multiplication algorithm
that uses some geometry , orderings, coset factorization ,
the Exchange property and a trick from du Cloux.
It is deeply recursive (and inefficient ) in some cases so even
though I have read about it and have a cursory
understanding of it, I won't be using it.

The other two papers do the group multiplication using a
Minimal Root Reflection Table (mrrt). Once you obtain a
Coxeter group's mrrt, group multiplication is relatively easy.
Note that the set of Minimal Roots is finite.
This doesn't say much about size, but it is a good thing.

So now where are we?
Build Minimal Root Reflection Table ->
Multiplication by generator ->
Build Cayley Graph.

One method for building the mrrt is explained in the
Automata paper. A 2nd is described in more detail in
Casselman's 2nd paper. Now I have two
choices -> Method 1 or Method 2.
The advantage of Method 1 is that if I choose it,
I'll be able to code it up before the semester ends.
It will probably take me all of the rest of the
semester (if not more time) to understand Method 2.
I have been lucky to have been furnished
with java source code from Casselman and so I would still be able
to build Cayley Graphs (even) after picking Method 2.

I have decided to take the risk of attempting
to use Method 2. The reason being that I started
reading Method 2's paper (because it contained some
details needed to implement Method 1) and
inadvertently read more than I intended to:
it wasn't as difficult to understand as I had originally thought.

So I'll be racing against time trying to juggle
my other classes, applications, transition to after-Laf-life,
and this project. I think I should be able to
finish in time though.

Casselman's Papers

2008-02-04T07:17:00.000-08:00

From the way things are going now, it looks as if setting myself the goal of understanding the results of Casselman's work with Coxeter Groups and their Automatic Structures will be a good one for my thesis. If I manage to do more that will be nice. I am hoping that before this semester ends, I will be able to understand the results of the following papers and show how they can be used in building Coxeter group Cayley Graphs.

I have done some teXing. I'll post it in due time. Meanwhile, the following papers are where I would like to be by the time this semester ends:
(for the third link, I am referring to the second paper on the page)

Casselman Paper 1
Casselman Paper 2
Automata to perform basic Calculations in Coxeter groups

Sources

2007-12-23T08:05:00.000-08:00

Here are the sources I'm using so far; where possible I will try to post links to the pdf files for some of the articles. For others, I'll post links to their Journals' websites. I won't be using all the materials from the sources below .... just what I need as when when I need it.

General Introduction to (Coxeter) Groups

Combinatorics of Coxeter Groups, Anders Bjorner & Francesco Brenti (2000)
Reflection Groups and Coxeter Groups, James E. Humphreys (1990)
Introduction to Coxeter Groups, Robert B. Howlett

Infinite Groups, Automatic Groups, Regular Languages, Automata etc.

GROUPS , GRAPHS & TREES : An Introduction to the Geometry of Infinite Groups, John Meier (2007)
Word Processing in Groups, David B. A. Epstein, J. W. Cannon, D. F. Holt, S. V.F Levy, M.S. Paterson, W.P. Thurston (1992)
The Use of Knuth-Bendix methods to solve the word problem in Automatic groups, Journal of Symbolic Computation D. B. A. Epstein, D. F. Holt, S. E. Rees (1991) (available on request)
The Warwick Automatic Groups Software , D. F. Holt (1994)

I don't know what category the rest of my sources fall in. They do however play significant roles in giving me material for the thesis.

Regular Polytopes, H.S.M. Coxeter (1973)
Cells in Coxeter Groups , Paul E. Gunnels
The Cayley Graphs of Coxeter and Artin Groups , Carl Droms and Herman Servatius (1993)
A Transducer Approach to Coxeter Groups , Fokko du Cloux (1999)
Computation in Coxeter Groups , Bill Casselman (2001ish)

If I was doing this in graduate school ... I would probably be using this book. I have it in my possession but I doubt I will actually get around to using it:

The Geometry and Topology of Coxeter Groups , Michael Davis (2007)

Why did I decide to do this

2007-10-13T06:56:00.000-07:00

Because I told enough people that I would so I kind of had no choice ....

Initially, the main goal of my thesis was to study the various ways in which Cayley Graphs of Coxeter Groups (cagcogs) can be built (and possibly rendered).

I have recently been able to distill this to the following question:
Constructing Cayley graphs of Coxeter groups is an inherently exponential process.
(Multiply each generator by every other generator for every step in the process ... so a group with n generators and k steps needs [Summation(n^i) for 0 < i < k] multiplications) We know that Coxeter groups grow polynomially, using that and other known facts about Coxeter groups, can we build the cayley graph in anything less than exponential time?

My biggest challenge in writing this thesis has been the fact that Coxeter group theory is so vast. A lot is known about them, which means there is so much for me to learn. I'm however picking up what to learn as I go along rather than wading though the
theory for its own sake. I ran the risk of possibly not recognizing solutions when they might be staring at me in the face.

I think the hardest part of this thesis is actually getting the actual teXing done. For that reason, I won't spend that much time here. I'll only be posting pdf updates on what I've teXed so far.

Finally the main reason I created this blog was because I want feedback, lots of it, on any aspects of the thesis. I am hoping to use that to mitigate my limited knowledge of this topic. I also want to thank everyone, especially my thesis adviser and readers and anyone else who would have helped contribute to my learning this material by the time I'm done.

Enough talk ... time to teX ....