An upper bound on the size of avoidance couplings

Erik Bates, Lisa Sauermann

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 kno…