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

This paper is the second in a series in which the authors study the conjugacydecision problem (CDP) and the conjugacy search problem (CSP) in Garsidegroups. The ultra summit set USS(X) of an element X in a Garside group G is afinite set of elements in G, introduced by the second author, which is acomplete invariant of the conjugacy class of X in G. A fundamental question, ifone wishes to find bounds on the size of USS(X), is to understand itsstructure. In this paper we introduce two new operations on elements of USS(X),called `partial cycling' and `partial twisted decycling', and prove that if Yand Z belong to USS(X), then Y and Z are related by sequences of partialcyclings and partial twisted decyclings. These operations are a concrete way tounderstand the minimal simple elements which result from the convexity theoremin the mentioned paper by the second author. Using partial cycling and partialtwisted decycling, we investigate the structure of a directed graph \Gamma_Xwhich is determined by USS(X), and show that \Gamma_X can be decomposed into`black' and `grey' subgraphs. There are applications which relate to theprogram, outlined in the first paper in this series, for finding a polynomialsolution to the CDP/CSP in the case of braids. A different application is togive a new algorithm for solving the CDP/CSP in Garside groups which is fasterthan all other known algorithms, even though its theoretical complexity is thesame as that given by the second author. There are also applications to thetheory of reductive groups.