computer science


The combinatorics of permutations

This has been the focus of my research since joining the computer science department, having been introduced to it by Mike Atkinson, who also provides a brief explanation of the subject. Much of our collaborative work has been done here with the theory of computing research group, but we also have many international collaborators including: Robert Brignall, Nik Ruskuc and Vince Vatter.

The class counter applet is a useful tool for experimental investigations in this area. It has now been replaced by a more advanced set of tools, PermLab, which provides both a more extensive user interface as well as a large collection of libraries. I recently spoke about its development (130M, mp4) in the CSIS seminar series. In November and December 2011 I gave seminars at the University of Florida, and UCLA on exact and approximate enumeration of permutation classes. The "handout" version linked above provides some sort of an overview of our recent work in this area.

The research landscape in this area is still wide open, accessible, and suitable for student work at all levels from fourth year projects through to PhD. Some of the areas of particular interest to me are:

  • development and analysis of effective algorithms for working with permutations,
  • understanding the operation of sorting operators in general,
  • the development of structural theory for (certain types of) restricted permutations,
  • a better understanding of the asymptotic behaviour and characteristics of random restricted permutations,
  • generalization of this theory to other classes of relational structures.

Back to Michael Albert's personal page

Back to CS Home Page

This page is maintained by Michael Albert
Last modified: May 2012.