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 these people are standing one at each vertex of X.  At each point in time, two friends standing at adjacent vertices of X may swap places, but two strangers may not. The friends-and-strangers graph FS(X,Y) has as its vertex set the collection of all configurations of people standing 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 work 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 obtain bounds on the minimum degrees of X and Y that guarantee FS(X,Y) being connected.  In a different direction, 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)}. We will conclude with several open problems and avenues for future research.

This talk is partly based on joint work with Noga Alon.