论文标题
避免在不完整图上的耦合
Avoidance couplings on non-complete graphs
论文作者
论文摘要
如果步行者从未碰撞，则依次转弯的同一有限图上的随机步行者的耦合被认为是一种回避耦合。对这些过程的先前研究几乎只关注完整的图表，特别是可以包括多少个避免耦合的步行者。对于其他图表，除特殊情况外，是否可以耦合两个非coll缩的简单随机步行者，这也尚未解决。在本文中，我们在（i）任何$ d $的图形上构建了这样的耦合，避免了固定子图，具体取决于$ d $； （ii）至少三个的任何无平方图。第一个结果的推论是，$ n $顶点上的均匀随机图形承认避免耦合的可能性很高。
A coupling of random walkers on the same finite graph, who take turns sequentially, is said to be an avoidance coupling if the walkers never collide. Previous studies of these processes have focused almost exclusively on complete graphs, in particular how many walkers an avoidance coupling can include. For other graphs, apart from special cases, it has been unsettled whether even two non-colliding simple random walkers can be coupled. In this article, we construct such a coupling on (i) any $d$-regular graph avoiding a fixed subgraph depending on $d$; and (ii) any square-free graph with minimum degree at least three. A corollary of the first result is that a uniformly random regular graph on $n$ vertices admits an avoidance coupling with high probability.
