Diameter Bounds for Friends-and-Strangers Graphs

Abstract

Consider two $n$-vertex graphs $X$ and $Y$, where we interpret $X$ as a social network with edges representing friendships and $Y$ as a movement graph with edges representing adjacent positions. The friends-and-strangers graph $\mathsf{FS}(X,Y)$ is a graph on the $n!$ permutations $V(X)\to V(Y)$, where two configurations are adjacent if and only if one can be obtained from the other by swapping two friends located on adjacent positions. Friends-and-strangers graphs were first introduced by Defant and Kravitz, and generalize sliding puzzles as well as token swapping problems. Previous work has largely focused on their connectivity properties. In this paper, we study the diameter of the connected components of $\mathsf{FS}(X,Y)$. We extend the result of Kornhauser, Miller, and Spirakis on sliding puzzles to general graphs in two ways. First, we show that the diameter of $\mathsf{FS}(X,Y)$ is polynomially bounded when both the friendship and the movement graphs have large minimum degree. Second, when both the underlying graphs $X$ and $Y$ are Erdős-Rényi random graphs, we show that the distance between any pair of configurations is almost always polynomially bounded under certain conditions on the edge probabilities.

14 pages, 1 figure