Christopher Jefferson

Towards a unified framework for search in permutation groups

Many problems involve finding a permutation group which satisfies some list of properties, including graph isomorphism, group intersection, set stabilizer, centraliser and normalizer.

These problems are solved by a family of backtracking algorithms, including Brendan McKay’s Nauty, Jeffery Leon’s Partition Backtrack, which was recently extended with orbital graphs by Jefferson, Pfeiffer and Waldecker.

This talk will show how all these algorithms have a common basis, group-the common basis of all of these algorithms, which are functions known as refiners, which commute with permutation groups. All existing techniques can be expressed in this framework, and understanding this framework allows for non-experts to usefully extend and improve existing algorithms.