Premium
Avoidance couplings on non‐complete graphs
Author(s) -
Bates Erik,
Podder Moumanti
Publication year - 2021
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20999
Subject(s) - corollary , combinatorics , mathematics , random regular graph , graph , coupling (piping) , discrete mathematics , chordal graph , 1 planar graph , engineering , mechanical engineering
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.