Graph theory and probability

On the Number of Shortest Paths in Graphs

Itai Benjamini and Elad Tzalik

4 pages16 claims indexed4 referencesManuscript 2023-11-16

Literature and attribution context

Checked against primary sources on 19 November 2026. This is targeted attribution checking, not a systematic novelty search.

Original result. Itai Benjamini and Elad Tzalik, On the Number of Shortest Paths in Graphs, arXiv:2311.10014v1, submitted 16 November 2023, provides the degree-sensitive shortest-path bound and the sphere discussion studied here. The neutral reading materials preserve this edition.

Subsequent unrestricted maxima. Jing Yu and Jie-Xiang Zhu, The Maximum Number of Shortest Paths in Graphs, arXiv:2609.02334v1, submitted 2 September 2026, proves the exact multigraph maximum (Theorem 1.3) and exact simple-graph maximum (Theorem 1.5). Those achievements belong to Yu–Zhu. At degree six and distance four their simple-graph formula gives $2(6-1)\cdot9=90$. This later paper is retrospective context; it is not used to justify an inference in the original 2023 proof.

Earlier spectral antecedent. Zdeněk Dvořák and Bojan Mohar's 2009 author preprint, Spectral radius of finite and infinite planar graphs and of graphs of bounded genus, Theorem 5.2, gives $\rho(G)\le\sqrt{8\Delta-16}+2\sqrt{15}$ in its stated planar degree range. Combining that result with the Chebyshev estimate $n_G(x,y)\le2(\rho(G)/2)^t$ yields a shortest-path exponential base of order $\sqrt\Delta$, with leading constant $\sqrt2$. This combination is an inference recorded here, not a claim that their paper states the present exact distance-four formulas. The square-root order alone must not be advertised as a new discovery.

What this reconstruction adds to the comparison. The scoped work supports the sharper leading constant one, the explicit weighted argument and the exact distance-four planar/spherical counts, subject to the stated hypotheses and repairs. No priority claim is made: wider literature may contain related or equivalent results. Classical tools, including Cauchy–Schwarz, Chebyshev polynomials and Perron–Frobenius theory, are not inventions of this experiment.

Discovery provenance. The owner supplied two initial model analyses and two notes created after their exchange. Model names and provenance were omitted from the new audit packets, but agreement between the exchanged notes is not independent replication. Exact API identifiers, complete tools/transcripts and costs of those original desktop sessions were not supplied. Statements of novelty and earlier computations inside the longer note remain its authors' supplied claims, outside the scoped audit.

Source record

Additional supporting archive items are identified in the original report. View the manuscript hashes and repository snapshot.

Cite this review

If this review or its supporting reports inform your work, please cite it.

Igor Rivin. Review of On the Number of Shortest Paths in Graphs. Math Referee, .

Download .bib
View BibTeX
@misc{rivin2026review-human-benjamini-tzalik-shortest-paths,
  author = {Rivin, Igor},
  title = {{Review of On the Number of Shortest Paths in Graphs}},
  year = {2026},
  month = {November},
  date = {2026-11-19},
  howpublished = {Math Referee},
  url = {https://mathreferee.dimensionreducers.ai/papers/human-benjamini-tzalik-shortest-paths/panel/},
  note = {Review report}
}