# Groups, Geometry, and Dynamics

Full-Text PDF (606 KB) | Metadata | Table of Contents | GGD summary

**Volume 2, Issue 1, 2008, pp. 13–61**

**DOI: 10.4171/GGD/30**

Published online: 2008-03-31

Conjugacy in Garside groups II: structure of the ultra summit set

Joan S. Birman^{[1]}, Volker Gebhardt

^{[2]}and Juan González-Meneses

^{[3]}(1) Barnard College, Columbia University, New York, United States

(2) University of Western Sydney, Australia

(3) Universidad de Sevilla, Spain

This paper is the second in a series in which the authors study the
conjugacy decision problem (CDP) and the conjugacy search problem
(CSP) in Garside groups.

The ultra summit set USS(`X`) of an element `X` in a Garside group
`G` is a finite set of elements in `G`, which is a complete
invariant of the conjugacy class of `X` in `G`. A fundamental
question, if one wishes to find bounds on the size of
USS(`X`), is to understand its structure. In this paper we
introduce two new operations on elements `Y` ∈ USS(`X`),
called ‘partial cycling’ and ‘partial twisted decycling’, and prove
that if `Y`, `Z` ∈ USS(`X`), then `Y` and `Z` are related by
sequences of partial cyclings and partial twisted decyclings. These
operations are a concrete way to understand the minimal simple
elements whose existence follows from the convexity property of
ultra summit sets.

Using partial cycling and partial twisted decycling, we investigate
the structure of a directed graph Γ_{X} determined by
USS(`X`), and show that Γ_{X} can be decomposed into
‘black’ and ‘grey’ subgraphs. There are applications relating to the
authors’ program for finding a polynomial solution to the CDP/CSP in
the case of braids, which is outlined in the first paper of this
series. A different application is to give a new algorithm for
solving the CDP/CSP in Garside groups which is faster than all other
known algorithms, even though its theoretical complexity is the same
as that of the established algorithm using ultra summit sets. There
are also applications to the theory of reductive groups.

*Keywords: *Garside groups, conjugacy problem, ultra summit set, partial cycling

Birman Joan, Gebhardt Volker, González-Meneses Juan: Conjugacy in Garside groups II: structure of the ultra summit set. *Groups Geom. Dyn.* 2 (2008), 13-61. doi: 10.4171/GGD/30