pith. sign in

arxiv: 2604.19733 · v1 · submitted 2026-04-21 · 🧮 math.CO · cs.DS· cs.NI· cs.SI

Greedy Routing in a Sequentially Grown One-Dimensional Random Graph

Alexander Ponomarenko This is my paper

Pith reviewed 2026-05-10 02:04 UTC · model grok-4.3

classification 🧮 math.CO cs.DScs.NIcs.SI
keywords greedy routingrandom graphssequential insertionpermutation minimalogarithmic complexityone-dimensional networksinsertion order
0
0 comments X

The pith

In this sequentially grown one-dimensional random graph, greedy routing from vertex 1 to n takes Theta(log n) steps with high probability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that in a random graph on vertices 1 to n where each new vertex connects only to its nearest left and right already-present neighbors, a greedy walk from 1 toward n takes a number of steps that grows like log n. Specifically, the step count equals the total left-to-right and right-to-left minima in the random insertion order permutation, minus two. This yields an expectation of roughly 2 log n and exponential tail bounds showing concentration around that scale. The result confirms a conjecture from simulations and extends to show that any start and target pair also has expected routing length 2 log n plus a constant.

Core claim

For a greedy walk GW starting at vertex 1 targeting vertex n, the number of steps S_n required to reach n satisfies S_n = Theta(log n) with high probability. Precisely, S_n = L_n + R_n - 2, where L_n and R_n are the numbers of left-to-right and right-to-left minima in the insertion-time permutation. Consequently, E[S_n] = 2H_n - 2 ~ 2 log n and P(S_n >= (2+c) log n) <= n^(-h(c/2) + o(1)) for any constant c > 0, with an analogous lower tail bound, where h(u) = (1+u) ln(1+u) - u. For arbitrary or uniformly random start-target pairs, E[S_{s,t}] = 2 log n + O(1).

What carries the argument

The insertion-time permutation and its left-to-right and right-to-left minima, which determine the greedy path length exactly via S_n = L_n + R_n - 2.

If this is right

  • The expected number of routing steps from 1 to n is asymptotically 2 log n.
  • The probability of routing length exceeding (2+c) log n decays as a power of n for any c>0.
  • For any fixed or random pair of start and target vertices the expected routing steps remain 2 log n plus a bounded term.
  • The logarithmic scaling persists when endpoints are chosen dynamically rather than fixed in advance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same minima-counting argument could be applied to higher-dimensional versions of the sequential growth model to address the original multi-dimensional conjecture.
  • This mechanism shows how purely local connection rules can produce navigable networks whose diameter under greedy search matches the small-world scale.
  • Numerical experiments that generate random permutations and count their record minima for large n would give direct confirmation of the exact asymptotic.
  • Replacing the single nearest-neighbor rule with k-nearest neighbors on each side would likely change only the leading constant while preserving the log n order.

Load-bearing premise

The graph is built by inserting vertices in uniform random order and connecting each new vertex exactly to its nearest already-inserted neighbor on the left and on the right.

What would settle it

Construct the graph for increasing n according to the insertion rule and run the greedy walk from 1 to n; if the observed step count exceeds (2+c) log n for some fixed c>0 in a positive fraction of trials that does not vanish with n, the Theta(log n) claim fails.

Figures

Figures reproduced from arXiv: 2604.19733 by Alexander Ponomarenko.

Figure 1
Figure 1. Figure 1: The graph G16 for the permutation τ = (7, 14, 11, 6, 12, 10, 1, 8, 16, 5, 4, 3, 9, 15, 13, 2) (insertion times listed by vertex 1, 2, . . . , 16). Vertex 7 is inserted first (τ (7) = 1) and is the global minimum. The ltrminima of τ are {1, 4, 7} (vertices with τ -values 7 > 6 > 1, each setting a new record scanning left to right), and the rtlminima are {7, 16}. By Theorem 4.3, the greedy walk from 1 to 16 … view at source ↗
Figure 2
Figure 2. Figure 2: Empirical probability mass function of Sn for n ∈ {500, 2000, 10000} (blue bars) compared to the asymptotic normal approximation N (2Hn − 2, 2 log n) (dashed red). The dotted line marks E[Sn]. Theorem 5.3 (Sharp concentration (explicit bounds)). Let h(u) = (1 + u) ln(1 + u) − u for u > −1, and h(u) = ∞ otherwise. For any n ≥ 2 and any t > 0, P [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Empirical vs. theoretical tail bounds for [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Ratio of theoretical bound to empirical tail probability for the upper tail [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
read the original abstract

We analyze greedy routing in a random graph G_n constructed on the vertex set V = {1, 2, ..., n} embedded in Z. Vertices are inserted according to a uniform random permutation pi, and each newly inserted vertex connects to its nearest already-inserted neighbors on the left and right (if they exist). This work addresses a conjecture originating from empirical studies (Ponomarenko et al., 2011; Malkov et al., 2012), which observed through simulations that greedy search in sequentially grown graphs exhibits logarithmic routing complexity across various dimensions. While the original claim was based on experiments and geometric intuition, a rigorous mathematical foundation remained open. Here, we formalize and resolve this conjecture for the one-dimensional case. For a greedy walk GW starting at vertex 1 targeting vertex n -- which at each step moves to the neighbor closest to n -- we prove that the number of steps S_n required to reach n satisfies S_n = Theta(log n) with high probability. Precisely, S_n = L_n + R_n - 2, where L_n and R_n are the numbers of left-to-right and right-to-left minima in the insertion-time permutation. Consequently, E[S_n] = 2H_n - 2 ~ 2 log n and P(S_n >= (2+c) log n) <= n^(-h(c/2) + o(1)) for any constant c > 0, with an analogous lower tail bound for 0 < c < 2, where h(u) = (1+u) ln(1+u) - u is the Bennett rate function. Furthermore, we establish that this logarithmic scaling is robust: for arbitrary or uniformly random start-target pairs, the expected routing complexity remains E[S_{s,t}] = 2 log n + O(1), closely mirroring decentralized routing scenarios in real-world networks where endpoints are chosen dynamically rather than fixed a priori.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript constructs a one-dimensional random graph on vertices {1,...,n} by inserting them according to a uniform random permutation and connecting each new vertex to its nearest already-inserted left and right neighbors. It proves that the greedy routing length S_n from vertex 1 to vertex n satisfies the exact identity S_n = L_n + R_n - 2, where L_n and R_n are the numbers of left-to-right and right-to-left minima in the insertion permutation. From this, the paper derives E[S_n] = 2H_n - 2 ~ 2 log n and Bennett-type tail bounds showing S_n = Theta(log n) with high probability; the same logarithmic scaling is shown to hold in expectation for arbitrary or random start-target pairs.

Significance. If the central identity holds, the work supplies a rigorous proof of the logarithmic routing conjecture previously supported only by simulations, by reducing the problem exactly to classical record statistics whose expectations and concentrations are already known. The deterministic relation S_n = L_n + R_n - 2 together with the direct application of harmonic-number and Bernoulli-sum tail bounds constitutes a parameter-free derivation that cleanly resolves the one-dimensional case and extends naturally to random endpoints.

minor comments (3)
  1. [Abstract] Abstract: the upper-tail bound is stated for any c > 0 while the lower tail is restricted to 0 < c < 2; a brief sentence clarifying the range for which both tails apply simultaneously would improve precision.
  2. [Introduction or Section 2] The manuscript should include a short explicit definition or small-n example of left-to-right and right-to-left minima immediately after their first appearance, to make the identity S_n = L_n + R_n - 2 immediately verifiable by the reader.
  3. [Main text (near first use of h)] Notation: the Bennett rate function h(u) is used without a displayed formula in the abstract; adding the standard expression h(u) = (1+u)ln(1+u) - u once in the main text would aid readers unfamiliar with the reference.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending minor revision. We appreciate the recognition that the exact identity S_n = L_n + R_n - 2, together with the application of known results on harmonic numbers and Bennett-type tail bounds, provides a rigorous and parameter-free resolution of the logarithmic greedy routing conjecture in one dimension.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The central derivation rests on an exact deterministic identity S_n = L_n + R_n - 2 that equates greedy routing length to the count of left-to-right and right-to-left minima in the random insertion permutation; this identity is obtained directly from the graph construction rule (each vertex links to nearest already-inserted left/right neighbors) and the greedy choice rule, without any definitional loop or parameter fitting. The subsequent Theta(log n) claim follows from the classical fact that each minimum count is a sum of independent Bernoulli indicators with P(I_k=1)=1/k, yielding E[L_n]=H_n, E[R_n]=H_n and Bennett tail bounds via union bound. These record statistics are external, parameter-free, and predate the paper. The only self-citation is a non-load-bearing reference to the origin of the empirical conjecture; it is not used to justify any mathematical step. The proof is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard random permutation model and the specific nearest-neighbor connection rule; no free parameters or new entities are introduced.

axioms (2)
  • domain assumption The insertion order is a uniform random permutation of {1,2,...,n}.
    This defines the random graph model G_n.
  • domain assumption Each new vertex connects to its nearest already-inserted left and right neighbors if they exist.
    This is the edge formation rule in the graph construction.

pith-pipeline@v0.9.0 · 5663 in / 1412 out tokens · 69755 ms · 2026-05-10T02:04:13.210736+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Aragon and Raimund Seidel

    Cecilia R. Aragon and Raimund Seidel. Randomized search trees.Algorithmica, 4:351–377, 1989

    work page 1989

  2. [2]

    G. Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297):33–45, 1962. 13

    work page 1962

  3. [3]

    Mathematical results on scale-free random graphs

    B´ ela Bollob´ as. Mathematical results on scale-free random graphs. In Stefan Born- holdt and Heinz Georg Schuster, editors,Handbook of Graphs and Networks, pages 1–34. Wiley-VCH, 2003

    work page 2003

  4. [4]

    A note on the height of binary search trees.Journal of the ACM, 33(3):489–498, 1986

    Luc Devroye. A note on the height of binary search trees.Journal of the ACM, 33(3):489–498, 1986

    work page 1986

  5. [5]

    Gnedin, A

    A. Gnedin, A. Iksanov, and U. Roesler. Records in a partially ordered set.Combi- natorics, Probability and Computing, 17(4):565–580, 2008

    work page 2008

  6. [6]

    Kleinberg

    Jon M. Kleinberg. Navigation in a small world.Nature, 406(6798):845, 2000

    work page 2000

  7. [7]

    Malkov, V

    A. Malkov, V. Krylov, et al. An overlay network for distributed exact and range search in one-dimensional space.Бизнес-информатика, (1 (35)):26–36, 2016

    work page 2016

  8. [8]

    Scalable distributed algorithm for approximate nearest neighbor search problem in high dimensional general metric spaces

    Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Scalable distributed algorithm for approximate nearest neighbor search problem in high dimensional general metric spaces. InInternational Conference on Similarity Search and Applications, pages 132–147. Springer, 2012

    work page 2012

  9. [9]

    Approximate nearest neighbor algorithm based on navigable small world graphs

    Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45:61–68, 2014

    work page 2014

  10. [10]

    Malkov and Alexander Ponomarenko

    Yury A. Malkov and Alexander Ponomarenko. Growing homophilic networks are natural navigable small worlds.PloS One, 11(6):e0158162, 2016

    work page 2016

  11. [11]

    Martel and V

    C. Martel and V. Nguyen. Analyzing kleinberg’s and other small-world models. In Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), pages 179–188, 2004

    work page 2004

  12. [12]

    Kademlia: A peer-to-peer information system based on the xor metric

    Petar Maymounkov and David Mazi` eres. Kademlia: A peer-to-peer information system based on the xor metric. InInternational Workshop on Peer-to-Peer Systems, pages 53–65, 2002

    work page 2002

  13. [13]

    The small world problem.Psychology Today, 1(1):61–67, 1967

    Stanley Milgram. The small world problem.Psychology Today, 1(1):61–67, 1967

    work page 1967

  14. [14]

    Generalized pref- erentialattachment: tunablepower-lawdegreedistributionandclusteringcoefficient

    Polina Ostroumova, Alexandra Ryabchenko, and Anand Tripathi. Generalized pref- erentialattachment: tunablepower-lawdegreedistributionandclusteringcoefficient. InInternational Workshop on Algorithms and Models for the Web Graph, pages 1–13. Springer, 2013

    work page 2013

  15. [15]

    Approximate nearest neighbor search small world approach

    Alexander Ponomarenko, Yury Mal’kov, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor search small world approach. InProceedings of the 2011 International Conference on Theoretical and Applied Computer Science (ICTA 2011), 2011

    work page 2011

  16. [16]

    Graph-based nearest neighbor search: From practice to theory

    Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based nearest neighbor search: From practice to theory. InInternational Conference on Machine Learning, pages 7803–7813, 2020

    work page 2020

  17. [17]

    Raimund Seidel and Cecilia R. Aragon. Randomized search trees.Algorithmica, 16:341–347, 1996. 14

    work page 1996

  18. [18]

    Frans Kaashoek, and Hari Balakrish- nan

    Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrish- nan. Chord: A scalable peer-to-peer lookup service for internet applications. InACM SIGCOMM Computer Communication Review, volume 31, pages 149–160, 2001

    work page 2001

  19. [19]

    A unifying look at data structures.Communications of the ACM, 23(4):229–239, 1980

    Jean Vuillemin. A unifying look at data structures.Communications of the ACM, 23(4):229–239, 1980

    work page 1980

  20. [20]

    Zhao, Ling Huang, Jeremy Stribling, Sean C

    Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph, and John D. Kubiatowicz. Tapestry: A resilient global-scale overlay for service deployment.IEEE Journal on Selected Areas in Communications, 22(1):41–53, 2004

    work page 2004

  21. [21]

    Структура со свойствами тесного мира для решения задачи поиска ближайшего соседа в метрическом пространстве.Вестник Нижегородского университета им

    Александр Александрович Пономаренко, Юрий Андреевич Мальков, Андрей Александрович Логвинов, and Владимир Владимирович Крылов. Структура со свойствами тесного мира для решения задачи поиска ближайшего соседа в метрическом пространстве.Вестник Нижегородского университета им. НИ Лобачевского, (5-2):409–415, 2012. 15

    work page 2012