Open Access Publications from the University of California

Published Web Location

https://doi.org/10.5070/C61055363
Abstract

Given graphs $$X$$ and $$Y$$ with vertex sets $$V(X)$$ and $$V(Y)$$ of the same cardinality, we define a graph $$\mathsf{FS}(X,Y)$$ whose vertex set consists of all bijections $$\sigma\colon V(X)\to V(Y)$$, where two bijections $$\sigma$$ and $$\sigma'$$ are adjacent if they agree everywhere except for two adjacent vertices $$a,b \in V(X)$$ such that $$\sigma(a)$$ and $$\sigma(b)$$ are adjacent in $$Y$$. This setup, which has a natural interpretation in terms of friends and strangers walking on graphs, provides a common generalization of Cayley graphs of symmetric groups generated by transpositions, the famous $$15$$-puzzle, generalizations of the $$15$$-puzzle as studied by Wilson, and work of Stanley related to flag $$h$$-vectors. We derive several general results about the graphs $$\mathsf{FS}(X,Y)$$ before focusing our attention on some specific choices of $$X$$. When $$X$$ is a path graph, we show that the connected components of $$\mathsf{FS}(X,Y)$$ correspond to the acyclic orientations of the complement of $$Y$$. When $$X$$ is a cycle, we obtain a full description of the connected components of $$\mathsf{FS}(X,Y)$$ in terms of toric acyclic orientations of the complement of $$Y$$. We then derive various necessary and/or sufficient conditions on the graphs $$X$$ and $$Y$$ that guarantee the connectedness of $$\mathsf{FS}(X,Y)$$. Finally, we raise several promising further questions.

Mathematics Subject Classifications: 05C40, 05C38, 05A05