Discrete mathematics

Speaker: 
Sophie MacDonald
Speaker Affiliation: 
UBC

October 26, 2021

Zoom - https://ubc.zoom.us/j/62676242229?pwd=RURtUC9UYXEweVZTMTNGT1EvY1FLZz09
Vancouver, BC V6T 1Z2
Canada

View All Events

Abstract: 

You live in a town with a finite number of houses, each with some one-way roads leaving it and ending at other houses. Can you colour the roads going out from each house so that a set sequence of colours takes everyone to your house, regardless of where they start? This is an imprecise statement of the road colouring problem, which arose in ergodic-theoretic work of Adler-Weiss in the late 1960's and was solved by Trakhtman in 2007. I will give an overview of Trakhtman's solution and present progress on a more general problem posed by Ashley-Marcus-Tuncel in the late 1990's, which remains open. In particular, I will introduce a handful of problems, involving incidence structures on the vertex set of a directed graph, that have emerged in my ongoing efforts to adapt Trakhtman's method to the AMT problem. I aim to advertise this interplay between ergodic theory, automata theory, and extremal combinatorics, and to invite collaboration.

Event Topic: