School of Mathematical Sciences

Synchronization, primitive permutation groups, and graph colouring exploiting symmetry menu

Synchronization, primitive permutation groups, and graph colouring exploiting symmetry

Speaker: 
Leonard Soicher (QMUL)
Date/Time: 
Mon, 30/10/2017 - 16:30
Room: 
Queens W316
Seminar series: 

The notion of a synchronizing permutation group arose from attempts to prove the
long-standing Černý conjecture in automata theory. The class of synchronizing permutation
groups is of interest in its own right, and lies strictly between the classes of finite primitive
permutation groups and finite 2-transitive groups. I will discuss my recent determination
of the synchronizing permutation groups of degree at most 255, using my newly
developed algorithms and programs for proper vertex-k-colouring a graph making use
of that graph's automorphism group.

This seminar may be of interest to combinatorialists as well as algebraists.