EVENT: Groups and Combinatorics Seminar: Orbital graphs

Speaker: Rebecca Waldecker (Martin-Luther-Universität Halle-Wittenberg)

Time and place: 16:00 Friday 10/03/2017 in Weatherburn LT

Title: Orbital graphs

Abstract: In joint work with Markus Pfeiffer and Chris Jefferson (both in St Andrews) I got interested in algorithms for permutation groups, in particular search algorithms that use partition backtracking. Typical examples would be algorithms that calculate the intersection of two permutation groups, a set stabiliser in a given group or the normaliser of a subgroup. We noticed that some algorithms could be improved by exploiting some group action, and this is where graphs enter the scene. In my talk I will introduce orbital graphs in this specific context and explain how they improve our algorithms. Moreover I will discuss in detail why, sometimes, these graphs do not help at all!