Skip to main content

Mathematical Sciences Department, Discrete Mathematics Seminar - Bill Martin (WPI) "Synchronization and designs in the symmetric group" SH106

Wednesday, October 05, 2022
3:00 pm to 3:50 pm


Floor/Room #: 
Mathematical Sciences Department
Discrete Mathematics Seminar


Bill Martin, WPI

Wednesday, October 5, 2022

3:00 pm - 3:50 pm

Stratton Hall 106

Title: Synchronization and designs in the symmetric group
Abstract: Entering the maze, you will be randomly placed in one of these eight rooms. The rooms all look identical to one another; each room has four exit doors: Red, Blue, Green, and White. The White door exiting Room 1 leads to safety while the White door in each other room leads to certain death. Can you find your way to safety? 
You don’t know where you will start — and you can’t see what room you are in at any point in time — yet you want to specify a word in the alphabet {R, B, G} which will bring you to Room 1: you want to be certain that, after you follow directions, choosing doors according to this word, you’ll finish in Room 1 and can safely walk through the white door. What’s the synchronizing word? (Another such puzzle is included below.) 
This talk will start and end with such puzzles, but will mainly deal with designs in association schemes. The classical motivating example is a collection of k-element subsets of [v] = {1, . . . , v} such that each telement subset of [v] is contained in exactly one of them. A more recent analogue, still closely tied to classical ideas, is the concept of λ-transitive sets of permutations. This is based on joint work with Bruce Sagan [J. London Math. Soc., 2006] where we apply a coding theory approach to such collections of permutations using character theory. In the past 11 years, this concept of λ-transitive (or λ-homogeneous) sets of permutations has been applied by Ara´ujo et al. to the study of synchronizing automata, which is where we started the talk!