{"id":"arxiv/2609.19728","url":"https://arxiv.org/abs/2609.19728","tags":["math.CO","math.PR"],"score":0,"title":"Paths maximize the expected range of graph-indexed random walks","domain":"math.CO","source":"arxiv","authors":["Yinfeng Zhu"],"reviews":0,"subject":"math.CO","summary":"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 of the same order. This establishes the expectation form of the Benjamini--Häggström--Mossel conjecture. The proof restricts and rescales a homomorphism on each bipartition class, then contracts the edges on which the resulting height function is constant. A quantitative estimate for the rank of these zero edges compensates for a parity term in the expected range of a simple random walk, allowing an induction on the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-17","reactions":{}}