MIT-Harvard-MSR Combinatorics Seminar

Speaker:  Colin Defant  (Harvard/Princeton)

Title:  Friends and strangers walking on graphs

Abstract: 

Let X and Y be simple graphs on n vertices. Identify the vertices of Y with n people, any two of whom are either friends or strangers (according to the edges and non-edges in Y), and imagine that the people sit on distinct vertices of X.  Two people are allowed to swap places with each other if they are friends with each other and they are sitting on adjacent vertices of X. The friends-and-strangers graph FS(X,Y) has as its vertex set the collection of all configurations of people sitting on the vertices of X, where two configurations are adjacent when they are related via a single swap of this form. It is natural to study the connected components of FS(X,Y), which correspond to the equivalence classes of mutually-reachable configurations. This framework provides a common generalization for the famous 15-puzzle, transposition Cayley graphs of symmetric groups, and earlier works of Stanley and Wilson.

We will explicitly describe the connected components of FS(X,Y) in the special cases where X is a path or a cycle; the results for the latter are closely related to toric partial orders.  We will also discuss minimum degree conditions on X and Y that guarantee FS(X,Y) is connected.  Finally, we will show that if X and Y are n-vertex random graphs with edge probability p, then the threshold probability for the connectedness of FS(X,Y) is p=n^-1/2+o(1). 

This talk is based on join work with Noga Alon and Noah Kravitz, and it will touch upon recent (separate) works of Kiril Bangachev and Ryan Jeong.