Penn Arts & Sciences Logo

Graduate Student Combinatorics Seminar

Wednesday, December 16, 2009 - 12:30pm

Saúl Blanco Rodríguez

Cornell University

Location

University of Pennsylvania

4C8

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.