Random friends walking on random graphs

Let $X$ and $Y$ be two $n$-vertex graphs. 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 friendly swap. This provides a common generalization for the famous 15-puzzle, transposition Cayley graphs of symmetric groups, and early work of Wilson and of Stanley.
I will describe several recent results and open problems addressing the extremal and typical aspects of the notion, focusing on the result that the threshold probability for connectedness of $FS(X,Y)$ for two independent binomial random graphs $X$ and $Y$ in $G(n,p)$ is $p=p(n)=n-1/2+o(1)$.
Joint work with Colin Defant and Noah Kravitz.