Paths maximize expected range of graph-indexed random walks
Paths maximize the expected range of graph-indexed random walks
This is a significant theoretical advancement in the field of graph theory and random walks, providing a new proof for a long-standing conjecture.
A new academic paper proves 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-Haagström-Mossel conjecture. The proof involves restricting and rescaling a homomorphism on each bipartition class, contracting edges where the resulting height function is constant, and using a quantitative estimate for the rank of zero edges to compensate for a parity term in the expected range of a simple random walk, allowing an induction on the number of vertices. The main results were also formalized and checked in Lean~4.
Paths maximize the expected range of graph-indexed random walks
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 number of vertices. We then prove that the BHM inequality implies the Loebl--Ne\v set\v ril--Reed inequality for uniformly chosen integer 1-Lipschitz functions on arbitrary connected graphs, and hence obtain the LNR conjecture as a corollary of BHM. The proof was obtained through interaction with OpenAI GPT-6 Astra and verified by the author. The main results have also been formalized and checked in Lean~4.
