Polymath-REU 2020

I am very much looking forward to being involved with the Polymath REU and to work with eager students on some exciting math.  Two possible projects I might be working on would be the following.

Explorer-Director Games on Graphs:
Two friends (Explorer and Director) are playing a game moving a token around on a graph.  Each turn, Explorer picks a distance that the token will move, and then Director moves the token to any vertex that’s the specified distance away.  Explorer is trying to get the token to see as many different vertices as possible, and Director is trying to minimize this number.  The game ends either after an agreed upon number of moves or when both players decide to stop.  For a given graph G, how well can each player do?  This generalizes the game originally proposed by Nedev and Muthukrishnan (for cycle graphs) [http://www.cs.rutgers.edu/~muthu/dm.pdf] as well as the group-theoretic variant due to Gerbner [https://hal.inria.fr/hal-00965706/PDF/2034-8414-1-PB.pdf] and further explored by Asgeirsson and Devlin [https://arxiv.org/abs/1904.00467].

Hat Guessing Number of Graphs:
We start with a group of people.  We tell them that each person will be given a hat, which will be one of k colors.  Each person will be told the hat colors that each of their friends has, but nobody is told their own hat color or the hat colors of people they aren’t already friends with.  Every person will then have to write down a guess of what they think their own hat color is, and these guesses are all made in secret at the same time.  The group wins if at least one person guesses their hat color correctly, and otherwise they lose.  The group can agree on a strategy ahead of time, but they aren’t allowed to communicate after they’re given their hats.  This game depends on the `graph’ of who can see who as well as on the number of colors (k), and the purpose of this project is to explore when the group can (and cannot) find a strategy that is guaranteed to always win.  This problem was first posed by Butler, Hajiaghayi, Kleinberg, and Leighton [https://epubs.siam.org/doi/abs/10.1137/060652774?journalCode=sjdmec] and has since been studied by a number of authors.