Matthew J. Samuel
Word posets, with applications to Coxeter groups.
Fri, 08/19/2011 - 15:01 — SomNambulAuthors: Matthew J. Samuel
Subjects: Discrete Mathematics
AbstractWe discuss the theory of certain partially ordered sets that capture the
structure of commutation classes of words in monoids. As a first application,
it follows readily that counting words in commutation classes is #P-complete.
We then apply the partially ordered sets to Coxeter groups. Some results are a
proof that enumerating the reduced words of elements of Coxeter groups is
#P-complete, a recursive formula for computing the number of commutation
classes of reduced words, as well as stronger bounds on the maximum number of
commutation classes than were previously known.Word posets, complexity, and Coxeter groups.
Wed, 01/26/2011 - 16:01 — SomNambulAuthors: Matthew J. Samuel
Subjects: Combinatorics
AbstractA monoid $M$ generated by a set $S$ of symbols can be described as the set of
equivalence classes of finite words in $S$ under some relations that specify
when some contiguous sequence of symbols can be replaced by another. If $a,b\in
S$, a relation of the form $ab=ba$ is said to be a \emph{commutation relation}.
Words that are equivalent using only a sequence of commutation relations are
said to be in the same \emph{commutation class}. We introduce certain partially
ordered sets that we call \emph{word posets} that capture the structure of
commutation classes in monoids.
User login
