Avoidance couplings on non‐complete graphs. Issue 1 (12th February 2021)

• Record Type: Journal Article
• Authors: Bates, Erik; Podder, Moumanti
• Is Part Of: Random structures & algorithms. Volume 59:Issue 1(2021)
• Page Start: 25
• Page End: 52
• Publication Date: 2021-02-12
• Subjects: avoidance coupling -- regular graph -- square‐free graph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20999
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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 noncolliding 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.