Paths maximize the expected range of graph-indexed random walks

Yinfeng Zhu

We prove that a path maximizes the expected range of a uniformly chosen graph homomorphism into the integers, with one vertex pinned at zero, among all connected bipartite graphs o…