Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.23511 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908818215010304 |
|---|---|
| author | Akella, Amogh Li, Rupert |
| author_facet | Akella, Amogh Li, Rupert |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_23511 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Diameter Bounds for Friends-and-Strangers Graphs Akella, Amogh Li, Rupert Combinatorics Discrete Mathematics Probability 05C12 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. |
| title | Diameter Bounds for Friends-and-Strangers Graphs |
| topic | Combinatorics Discrete Mathematics Probability 05C12 |
| url | https://arxiv.org/abs/2509.23511 |