Combinatorial problems of block transpositions in symmetric groups

Combinatorics Seminar
Tuesday, May 19, 2015 - 13:30
1 hour (actually 50 minutes)
Skiles 005
University of Basilicata
In the study of combinatorial aspects of symmetric groups, a major problem arising from applications to Genetics consists in finding a minimum factorization of any permutation with factors from a given generating set. The difficulty in developing an adequate theory as well as the hardness of the computational complexity may heavily vary depending on the generator set. In this talk, the generating set consists of all block transpositions introduced by Bafna and Pevzner in 1998 for the study of a particular ''genome rearrangement problem''. Results, open problems, and generalizations are discussed in terms of Cayley graphs and their automorphism groups.