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

The proposed argument

The manuscript bounds the number of shortest paths by combining two entropy expansions and a bound on incoming/outgoing degree products. It then discusses extremal examples, simple graphs, random walks, girth, sphere triangulations and higher-dimensional fillings. This map records the original 2023 text and its argument structure; later developments and assessments are separate.

The reading materials preserve the four-page November 2023 v1. The accompanying publication studies selected 2026 reconstruction arguments separately; it is not a complete review of the original paper. The source cutoff uses the arXiv v1 submission date because no earlier received-date evidence was supplied.

Reading order

  1. 01

    1. Geodesic support and the degree budget

    Identify the relevant edges before counting paths.

  2. 02

    2. The main entropy argument

    Combine directional conditional entropies into the shortest-path estimate.

  3. 03

    3. Examples and refinements

    Read the proposed equality cases, simple-graph bound, random-walk statement and girth discussion separately.

  4. 04

    4. Surface geometry and fillings

    Track the geometric degree reduction separately from the higher-dimensional questions.

Follow the dependencies

Open the full map ↗

Select a claim to see its prerequisites and consumers. Edge labels distinguish proof inputs, source references, background and exclusions.

Your independent assessment

Trace the two entropy expansions and degree-product bound, keep graph classes and distances separate, and reconstruct the surface degree reduction. Assess later comments and filling definitions individually.

Notes stay on this device.