When presented with a group defined by generators and relations (as Coxeter groups are usually given), a natural thing to do is to think of the elements of the group as words on some alphabet, (where the alphabet is the generating set). This makes multiplication really easy: the product of $u$ and $v$ is the concatenation of $u$ and $v$. However, some problems arise as well; for instance, the same element can have multiple representations. Given two words in a finitely presented group, is there an algorithm that decides whether or not $u$ and $v$ correspond to the same element? This problem is known as the \emph{word problem}. In general, the answer is negative, but the word problem is solvable for Coxeter groups. Furthermore, the language of reduced expressions in any Coxeter group turns out to be regular; that is, it can be recognized by \emph{deterministic finite automaton}. The key to construct this automaton is the set of \emph{small} roots of a Coxeter system, which turns out to be finite. Coxeter groups also have many combinatorial properties. One can define a partial order (called the Bruhat order) on the elements of the group, which has a very simple description. An interval $[u,v]$ in this partial order is Eulerian and shellable. In this talk, I'll try to give the basic definitions and explain some of the facts just mentioned.
Graduate Student Combinatorics Seminar
Wednesday, December 16, 2009 - 12:30pm
Saúl Blanco Rodríguez
Cornell University