Combinatorial Theory

Given simple graphs \(X\) and \(Y\) on the same number of vertices, the friends-and-strangers graph \(\operatorname{FS}(X, Y)\) has as its vertices all bijections from \(V(X)\) to \(V(Y)\), where two bijections are adjacent if and only if they differ on two adjacent elements of \(V(X)\) with images adjacent in \(Y\). We study the diameters of connected components of friends-and-strangers graphs: the diameter of a component of \(\operatorname{FS}(X,Y)\) corresponds to the largest number of swaps necessary to go from one configuration in the component to another. We show that any component of \(\operatorname{FS}(\operatorname{Path}_n, Y)\) has \(O(n^2)\) diameter and that any component of \(\operatorname{FS}(\operatorname{Cycle}_n, Y)\) has \(O(n^4)\) diameter, improvable to \(O(n^3)\) whenever \(\operatorname{FS}(\operatorname{Cycle}_n, Y)\) is connected. Answering a question raised by Alon, Defant, and Kravitz in the negative, we use an explicit construction to show that there exist \(n\)-vertex graphs \(X\) and \(Y\) such that \(\operatorname{FS}(X,Y)\) has a component with \(e^{\Omega(n)}\) diameter. We conclude with several suggestions for future research.

Mathematics Subject Classifications: 05C12, 05C35, 05C38

Keywords: Friends-and-strangers graphs, diameter, extremal combinatorics, lower bounds, paths, cycles, token swapping, interchange process