An avoidance coupling of two Markov processes is a common
implementation of these processes so that they are, viewed separately,
faithful to their own probability matrices. We will look at such
couplings of simple random walks. Under what circumstances is it
possible to set up two tokens on a graph, so that they never collide but
if you can only see one, it looks like it's doing a simple random walk?
We will introduce a class called uniform avoidance coupling, and show
that it's possible if and only if a matching or a network flow condition
on the graph is satisfied. We will then talk about a privacy paradigm
called k-anonymity and discuss what graph theory can teach us about how
anonymous communication systems should be designed.