论文标题
在朋友和纠缠的直径上
On the Diameters of Friends-and-Strangers Graphs
论文作者
论文摘要
在相同数量的顶点上，给定简单的图形$ x $和$ y $，朋友和纠缠的图形$ \ mathsf {fs}（fs}（x，y）$都具有其顶点，从$ v（x）$到$ v（y）$，在两个相邻的$ v（x）$ v（x）$至$ v（y）$中仅在$ v（x）$ v（x）$ v（x）上差异。我们研究了朋友和缠绕器图形的连接组件的直径：$ \ Mathsf {fs}（x，y）$的组件的直径对应于从组件中的一种配置到另一个配置所需的最大数量的交换数。我们表明，$ \ mathsf {fs}的任何组件（\ Mathsf {path} _n，y）$都有$ o（n^2）$直径，并且$ \ mathsf {fs}的任何组件$ \ mathsf {fs}（\ Mathsf {cycle} _n，y）$已连接。这些结果解决了Defant和Kravitz提出的一个空旷的问题。使用显式结构，我们表明存在$ n $ -VERTEX图$ x $和$ y $，因此$ \ mathsf {fs}（x，y）$具有$ e^{ω（n）} $直径的组件。这回答了Alon，Defant和Kravitz在负面的问题中提出的一个问题。作为推论，我们观察到，对于这种$ x $和$ y $，在$ \ mathsf {fs}（x，y）$的懒惰随机步行中，有$ e^{ω（n）} $混合时间。该结果偏离了有关快速混合马尔可夫链的相关经典定理，并在另一个Alon，Defant和Kravitz的开放问题上取得了进展。我们以几个未来研究的建议结束。
Given simple graphs $X$ and $Y$ on the same number of vertices, the friends-and-strangers graph $\mathsf{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 $\mathsf{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 $\mathsf{FS}(\mathsf{Path}_n, Y)$ has $O(n^2)$ diameter and that any component of $\mathsf{FS}(\mathsf{Cycle}_n, Y)$ has $O(n^4)$ diameter, improvable to $O(n^3)$ whenever $\mathsf{FS}(\mathsf{Cycle}_n, Y)$ is connected. These results address an open problem posed by Defant and Kravitz. Using an explicit construction, we show that there exist $n$-vertex graphs $X$ and $Y$ such that $\mathsf{FS}(X,Y)$ has a component with $e^{Ω(n)}$ diameter. This answers a question raised by Alon, Defant, and Kravitz in the negative. As a corollary, we observe that for such $X$ and $Y$, the lazy random walk on this component of $\mathsf{FS}(X,Y)$ has $e^{Ω(n)}$ mixing time. This result deviates from related classical theorems regarding rapidly mixing Markov chains and makes progress on another open problem of Alon, Defant, and Kravitz. We conclude with several suggestions for future research.
