Speaker: Wilf Wilson (St Andrews)
Title: Perfect Refiners for Permutation Group Backtracking Algorithms
Abstract:
Backtrack search in finite permutation groups has been formulated around points, ordered partitions, and more recently, graphs. We now need a framework for comparing and understanding the capabilities of these techniques, and for choosing the most appropriate algorithm for a given problem. We also wish to develop better refiners (which are used to prune the search space), particularly for difficult problems like computing normalisers.
In that context, I will talk about the new concept of perfect refiners, which are those refiners with maximal pruning power. I will classify the groups for which there exist perfect refiners, and give several examples of perfect refiners that are implemented in the new GAP package 'Vole'.
This talk covers ongoing joint work with Chris Jefferson (St Andrews) and Rebecca Waldecker (Halle).