On a Question of Benjamini on First-Passage Percolation in Hierarchical Graphs: The Recursive Constant Exceeds the Branching Random Walk Constant

Abstract

In Question 9.1 of his survey "Euclidean vs. Graph Metric" (2013), Benjamini considers first-passage percolation on the hierarchical graphs G_n obtained by replacing, recursively, every edge by one edge followed by two parallel edges. With independent positive edge weights of law ξ, the source–sink distance satisfies D_n =d D_{n−1} + min(D′_{n−1}, D″_{n−1}). The question asks to compute γ_rec = lim 2^{−n} E D_n in terms of ξ, and in particular to show, if true, that γ_rec > γ_brw, the speed of the minimal position of the binary branching random walk with step law ξ, which is a lower bound for γ_rec. We give a partial answer. We prove γ_rec > γ_brw for every non-degenerate law ξ that is bounded below and has finite mean, hence for every non-degenerate law of positive weights with finite mean. The proof is a standard first-moment (union) bound taken one level up the hierarchy, combined with the inequality e^{−t min(x,y)} < e^{−tx} + e^{−ty}; at level zero the first-moment bound is γ_brw, by the classical theorem of Hammersley, Kingman and Biggins. We also show that γ_rec is the increasing limit of explicit first-moment bounds and the decreasing limit of 2^{−k} E D_k, that D_n/2^n → γ_rec in L¹, as anticipated in the source, and that 2^{−k} E D_k − γ_rec ≤ ((1+√2)/2) ‖ξ − ess inf ξ‖₂ 2^{−k/2}. Certified computer-assisted computations give γ_rec ∈ [0.268785599, 0.268808710] for weights uniform on [0,1], where γ_brw = 0.18482…, and γ_rec ∈ [0.379282228, 0.379412906] for exponential weights of mean one, where γ_brw = 0.23196…; in particular, the remark in the UnsolvedMath collection that the two constants coincide in the exponential case is incorrect. A closed formula for γ_rec in terms of ξ, the "compute" part of the question, remains open. The method is standard; no answer to the question was found in the literature accessible to us, and no priority is claimed. This is an unrefereed note. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifier: AMR-099-0065 (Benjamini, Euclidean vs. Graph Metric, Question 9.1, Erdős Centennial, Bolyai Soc. Math. Stud. 25 (2013)).