Monotonicity of Avoidance Coupling on $K_N$

Abstract

Answering a question by Angel, Holroyd, Martin, Wilson and Winkler, we show that the maximal number of non-colliding coupled simple random walks on the complete graph $K_N$, which take turns, moving one at a time, is monotone in $N$. We use this fact to couple $\lceil \frac{N}{4}\rceil$ such walks on $K_N$, improving the previous $\Omega (N/\log N)$ lower bound of Angel et al. We also introduce a new generalization of simple avoidance coupling which we call partially ordered simple avoidance coupling and provide a monotonicity result for this extension as well.

9 pages, 2 figure

References in corpus (2)

• Shy couplings, CAT(0) spaces, and the lion and man
• Avoidance Coupling

Cited by in corpus (1)

• An upper bound on the size of avoidance couplings