An upper bound on the size of avoidance couplings on $K_n$

Erik Bates, Lisa Sauermann

Published 2017-12-01Version 1

We show that a coupling of non-colliding simple random walkers on the complete graph on $n$ vertices can include at most $n - \log n$ walkers. This improves the only previously known upper bound of $n-2$ due to Angel, Holroyd, Martin, Wilson, and Winkler (Electron. Commun. Probab. 18, 2013).