For every connected bipartite graph G with n vertices and every chosen vertex v∈ V(G), let F_G be uniformly distributed over the finite set f:V(G)→Z: f(v)=0 and |f(x)-f(y)|=1 for every xy∈ E(G). Define the range by operatornameRange(f)=max_x∈ V(G)f(x)-min_x∈ V(G)f(x). Then the conjecture asserts that Ebigl[operatornameRange(F_G)bigr]≤ Ebigl[operatornameRange(F_P_n)bigr], where P_n is the path on n vertices and F_P_n is defined analogously, with any one vertex pinned at 0.

Benjamini–Häggström–Mossel conjecture

For every connected bipartite graph $G$ with $n$ vertices and every chosen vertex $v\in V(G)$ , let $F_G$ be uniformly distributed over the finite set $\{f:V(G)\to\mathbb{Z}: f(v)=0\text{ and }|f(x)-f(y)|=1\text{ for every }xy\in E(G)\}$ . Define the range by $\operatorname{Range}(f)=\max_{x\in V(G)}f(x)-\min_{x\in V(G)}f(x)$ . Then the conjecture asserts that

\mathbb{E}\bigl[\operatorname{Range}(F_G)\bigr]\leq \mathbb{E}\bigl[\operatorname{Range}(F_{P_n})\bigr],

where $P_n$ is the path on $n$ vertices and $F_{P_n}$ is defined analogously, with any one vertex pinned at $0$ .

References

Primary source

arXiv

Additional references

Paths maximize the expected range of graph-indexed random walks — arXiv — Yinfeng Zhu

Posted 2 weeks ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Claimed solved

A new preprint claims to prove the expected-range version of the conjecture, while the stronger distributional version remains unresolved.

The Benjamini–Häggström–Mossel conjecture asserts that a path maximizes the expected range of a graph-indexed random walk among graphs with the same number of vertices. The 2019 literature distinguishes this expectation statement from a stronger statement comparing all range-tail probabilities.

Known results

Wu, Xu, and Zhu proved the expectation statement for trees, for both standard and lazy walks.
Bok and Nešetřil extended the expectation result to unicyclic graphs.
Loebl, Nešetřil, and Reed obtained an absolute-constant comparison in the lazy case.
The stronger tail-probability statement was proved for all trees in the lazy case and for spiders in the standard case; the general standard-walk tree case was open in the 2019 account.

September 2026 claimed proof

Yinfeng Zhu’s new preprint claims the expectation form is proved, derives the LNR conjecture as a corollary, and reports a Lean 4 formalization checked for the encoded statements. This is a claimed resolution, but the manuscript is a new preprint and no independent verification was found.

Current status (as of September 2026): The expectation form is claimed solved and formally checked in Lean 4, but remains unverified; the stronger tail-probability form is not established by the retrieved evidence.

OpenAI GPT-6 AstraOpenAIattempted2026-09-17evidence
BHM expected-range conjecture proved and formally checked

Sources

No solutions have been posted yet.