Paths maximize the expected range of graph-indexed random walks

Abstract

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.

Mean convergence for Banach space-valued random elements indexed in measure spaces
Nguyen Thi Kim Sang, Nguyen Tran Thuan
arXiv31 Aug 2026PreprintarXiv licenceFull textProbabilityarXiv
Moderate Deviations for Random-Indexed Cluster Counts in Hierarchical Pitman-Yor Models
Nian Yao
arXiv4 Oct 2026PreprintarXiv licenceFull textProbabilityarXiv
Estimating the expected output of wide random MLPs more efficiently than sampling
Wilson Wu, Victor Lecomte, Michael Winer +3
arXiv2 Nov 2026PreprintCC BY 4.0Full textStatistics Condensed matterarXiv
Expected mixed volumes of convex hulls of random walks and Lévy processes
Artyom Bolotin, Dmitry Zaporozhets
arXiv7 Oct 2026PreprintarXiv licenceFull textProbabilityarXiv
Random Clocks on Computation Paths]{Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?
Farzad Didehvar, Saman Farhat
arXiv19 Oct 2026PreprintCC BY 4.0Full textProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{zhu2026paths,
  title = {{Paths maximize the expected range of graph-indexed random walks}},
  author = {Yinfeng Zhu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.19728},
  eprint = {2609.19728},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.19728},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Paths maximize the expected range of graph-indexed random walks
AU  - Yinfeng Zhu
PY  - 2026
DA  - 2026/09/17
PB  - arXiv
DO  - 10.48550/arxiv.2609.19728
UR  - https://arxiv.org/abs/2609.19728
AB  - 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.
ER  -

Abstract

Related

Cite