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
Local repair checked

Scope: Scoped local replacement for original Proposition 4 and a twelve-obligation audit of proposed planar/surface improvements. The remainder of the original paper and longer notes is not cleared by this release.

Headline results: No main-result refutation is asserted. The checked improvement chain is supported after two qualifications; broader claims and priority remain outside scope.

A link-cycle replacement is checked for Proposition 4. The reconstruction needs an integer/real degree qualification and a depth-one degree-bound correction. Ten returned assessments retain declared coverage and metadata failures.

An assessment of the stated scope, not a formal proof certificate. What the labels mean ↗

Panel commentary

This page contains assessments and source-audit conclusions. Human comparison remains pending. Return to the reading view to form your own assessment first.

Decisions by result

Open the decorated graph ↗

Double borders mark terminal results in the recorded proof graph. Green, yellow and red summarize scoped adjudications. Yellow also marks unadjudicated claims and unresolved dependencies; a paper-level assessment does not fill in missing node decisions.

Benjamini–Tzalik: a scoped improvement audit

Updated 19 November 2026. The checked planar/surface argument chain is supported after two explicit qualifications. This is not a complete audit of the original paper or of either combined reconstruction. No novelty claim is established.

The publication combines a neutral reading map of Benjamini–Tzalik's four-page 2023 paper with a separate audit of selected improvements proposed in two later, exchanged model notes. Ten independent audit responses—two each from Sol 6.1, Sol 6.2, Astra 6, Astra 6.2 and Fable 5.2—were followed by coordinator source adjudication. Agreement is evidence, not certification; this is neither formal verification nor blind human grading.

What the checked work supports

For simple planar graphs, the weighted two-walk method controls branching using planarity. Together with expanding constructions, it gives a shortest-path exponential growth rate $\sqrt\Delta(1+o(1))$ as the degree budget grows. The order of limits matters: first take the distance limsup at each fixed degree, then let the degree grow. The exact rate at each fixed degree above six is not determined.

At distance four, the checked bounds and constructions give $\Delta(\Delta+1)$ for simple planar graphs when $\Delta\ge4$, and $\Delta(\Delta-1)$ for simplicial sphere triangulations when $\Delta\ge6$. Thus maximum degree at most six gives 42 and 30 paths respectively. Yu–Zhu's later Theorem 1.5 supplies the unrestricted simple-graph value 90. These statements concern a fixed pair at distance four, unit edges and no parallel edges. They do not assert an extension of the planar rate to all closed surfaces or multigraphs.

Source packets and actual coverage

  • M: pages 3–8 and only section 3.3 on page 9 of the supplied Astra-origin combined PDF.
  • N: the supplied Fable-origin TeX, original lines 14–21, 91–136, 358–387 and 401–525, including the macro definitions.
  • O: all four pages of Benjamini–Tzalik arXiv:2311.10014v1, used for the assigned comparison.

Both combined notes were produced after an exchange. The audit prompts concealed their author-model labels but could not undo the shared source history. Their agreement is not an independent replication. All requests used high effort, native Batch, a 65,536-token output/reasoning limit and no tools.

All ten responses returned mathematical text but initially failed the exact-source-label schema check. Hash-bound, explicit reconciliation changes only the source-access labels in separate derivatives. It preserves native answers, statuses, costs and mathematical content. Nine declare complete access to their supplied packet; Sol 6.2 upper remains partial, with M8, M9, O4 and the undeclared N material uncredited. Access declarations do not prove that every supplied page was read or every claim audited.

Sol 6.1 upper repeats the real-parameter qualification and the original Proposition 4 proof defect. Its lower response finds no issue in L1–L6; it does not flag N's depth-one exact-degree wording. There is no new Sol 6.1 objection requiring a further repair. The two earlier qualifications remain in the corrected package.

Two repairs in the proposed improvement

Integer versus real degree budget. The rounded intermediate expression is not bounded by the proposed continuous expression for every real $D$. For $D=9/2$ and $r=1$, the rounded expression is 6 while the proposed continuous value is $81/16$. This does not refute the theorem: the offending rounded degree pair is infeasible for that real budget. Specify integer $D$, or apply AM–GM directly to feasible $a,b\ge2$ with $a+b\le D$:

$$\left(2+\frac{a-2}{r}\right)\left(2+\frac{b-2}{r}\right) \le\left(2+\frac{a+b-4}{2r}\right)^2 \le\left(2+\frac{D-4}{2r}\right)^2.$$

Astra 6, Astra 6.2, Sol 6.2 and the newly returned Sol 6.1 upper response identify this issue. Fable 5.2's response does not supply the missing domain qualification. The corrected TeX explicitly uses an integer degree budget; the companion addendum gives the direct continuous argument.

Exact degree at depth one. For $h=1,D=5,k_0=3$, N's construction gives $K_{2,3}$ of maximum degree three; adding the middle cycle gives a triangular bipyramid of maximum degree four. Those satisfy the intended degree budgets but do not attain the printed exact degrees five and seven. Say “degree at most,” or require $h\ge2$ for exact attainment. This does not change the distance-four case or the asymptotic lower bound. Astra 6.2 and Sol 6.2 identify the defect; their checked repairs can also attain the exact budget by suitable pendant or stellar additions. The simpler degree-bound wording is used in the corrected note.

Twelve checked obligations

“Supported” means the coordinator checked the supplied mechanism and hypotheses against the frozen sources. It is not a guarantee that every possible defect has been excluded.

ID Checked obligation Source-based disposition
U1 Weighted two-walk inequality Supported in the checked scope. Forward reciprocal weights and reverse weights cancel along a path; both path measures have mass one, so Cauchy–Schwarz applies. Planarity is unnecessary here.
U2 At most two shared children/parents Supported for simple planar geodesic graphs. Three shared children produce a K3,3 minor using disjoint connected lower/upper branch sets; reverse the layers for parents.
U3 Local weights and endpoint factors Supported with the specified edge-weight rules. Keep the two notes' different endpoint conventions separate. The t>=3 refinement uses distinct first/last internal layers.
U4 Continuous and integer optimization Supported after the real-D repair below. Integer rounding and the direct continuous AM–GM argument have distinct domains. Small degree cases require their separate formulas.
U5 Surface link and degree reduction Supported for internal geodesic vertices of a simplicial closed surface. Two same-layer link neighbors remove two edges from the geodesic degree budget. The stronger rate also requires planarity.
U6 Assembled upper bounds Supported for the stated simple-graph domains: planar effective degree D=Delta, spherical D=Delta-2, with small D handled separately. No arbitrary-genus or multigraph extension follows.
L1 Expanding triangulated disks Supported. For spherical degree budget Delta>=7, each rim vertex has one or two parents and the specified positive number of private children. The annulus and distance layers preserve the required graph properties.
L2 Even and odd closure Supported after replacing the depth-one exact-degree assertion by a degree bound. The even seam has degree at most six; the odd antiprism seam has the stated adjacent-product path count.
L3 Moment recurrence and asymptotic root Supported. The three square/product sums reproduce the stated matrix, characteristic polynomial z^3-(Delta-1)z^2+6z-2 and positive parity readouts; Perron–Frobenius gives the fixed-degree lower rate.
L4 Degree six and leading constant Supported. Capped triangular-ring strips give rate two at degree six. First take the distance limsup at fixed Delta, then let Delta grow to obtain rate/sqrt(Delta) tending to one; exact fixed-Delta rates above six are not determined.
L5 Distance-four upper bound Supported. Averaging the two directional interface estimates gives N<=Delta(D+1)-(p+p')/2. The displayed cross-term estimate needs D>=3; D=2 is handled separately because each internal vertex then has one parent and one child.
L6 Distance-four equality examples Supported. One expansion and reflection gives Delta(D-3) middle vertices of weight one and Delta of weight two, hence Delta(D+1) paths. This single-annulus construction only needs D>=4.

Original Proposition 4: a local replacement

The graph induced by all neighbors of a vertex in a sphere triangulation can have chords, even though its simplicial link is a cycle. The printed contraction also needs justification, and the auxiliary degree assertion must be restricted to internal geodesic vertices rather than arbitrary ambient vertices.

A direct replacement avoids the contraction. Let an internal geodesic vertex $v$ have level $i=d(x,v)$, predecessor $u$ at level $i-1$ and successor $w$ at level $i+1$. The two link arcs between $u$ and $w$ each contain a distinct vertex at level $i$, since distance changes by at most one along an edge. These two incident edges cannot advance toward either endpoint. Hence $d^-(v)+d^+(v)\le\Delta-2$. Applying the two directional path measures and Cauchy–Schwarz yields the stated sphere bound. The same link fact holds on every closed simplicial surface; the stronger planar branching argument still needs planarity.

This checked replacement is the only original numbered result assigned an explicit decision in the published decision records. Other original claims remain unadjudicated in this scoped release. The decision graph preserves the original proof dependencies: a verified local replacement does not silently mark all nodes in that original proof path as checked.

Computation and its limits

The saved exact checks include 34,220 feasible degree-pair AM–GM comparisons, the real-parameter and depth-one examples, 128 exact-degree repair graphs, 64 spherical-complex checks, the two original-Proposition-4 counterexamples, and recurrence checks for 26 degree values. They corroborate conventions and finite cases. The infinite families rely on the written arguments, not enumeration.

These saved checks were produced in the source adjudication. Publication copied their code and results without rerunning them. Earlier computations described elsewhere in the combined note have not all been independently replayed or audited here.

Later literature and attribution

Benjamini and Tzalik's original v1 owns the original degree-sensitive bound. Jing Yu and Jie-Xiang Zhu's September 2026 preprint, Theorems 1.3 and 1.5, owns the exact unrestricted multigraph and simple-graph maxima. It is subsequent context, not a justification for the original 2023 proof.

Dvořák and Mohar's 2009 planar spectral-radius theorem, combined with the classical Chebyshev argument, already gives square-root order with a weaker leading constant. The present comparison concerns sharper constants, explicit arguments and exact small-distance bounds. A targeted search has not established priority for them. No claims that a model invented these results or that no earlier result exists are made.

Coverage, costs and remaining limits

Response Effort Declared packet access Ordinary estimate Conservative ceiling
Sol 6.1 — lower / distance four high Complete supplied packet $0.097702 $0.160159
Sol 6.1 — upper high Complete supplied packet $0.115473 $0.186808
Sol 6.2 — lower / distance four high Complete supplied packet $0.076647 $0.128636
Sol 6.2 — upper high Partial; see record $0.083448 $0.138831
Astra 6 — lower / distance four high Complete supplied packet $0.573035 $0.927582
Astra 6 — upper high Complete supplied packet $0.493915 $0.808867
Astra 6.2 — lower / distance four high Complete supplied packet $0.312748 $0.523786
Astra 6.2 — upper high Complete supplied packet $0.297472 $0.500844
Fable 5.2 — lower / distance four high Complete supplied packet $0.827348 $0.827348
Fable 5.2 — upper high Complete supplied packet $0.872704 $0.872704

These ten audit responses account for $3.750492 ordinary uncached estimated cost** and a **$5.075567 conservative usage ceiling. These are not invoices or customer prices. They exclude the original desktop discovery sessions, whose full cost records were not supplied. Failed metadata validation is included; publication used no new inference.

The unexamined portions of both combined notes include several general extremal, equality, girth, random-walk, higher-dimensional, numerical and priority claims. Some may be correct; this scoped audit does not settle them. The attached longer note visibly retains its own broader assessment and discovery statements under a front-page scope warning. They must not be read as conclusions of this panel report.

Corrected working documents

Start with the short correction addendum, then consult the longer working note and the scoped report together. The PDFs and mathematical TeX are unchanged from the corrected v1.1 package. A separate public bundle replaces private paths and stale administrative material with this dated report and public provenance; it makes no further mathematical edits.

The neutral manuscript, reading worksheet and original-source roadmap remain separate from these assessments.

Source record

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

Download panel reportDownload curated review packageSeparate reading packet

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}
}