PaperlayerView exact revision on arXiv

Source-linked AI summary

The Price of Almost Navigability

Tomer Waizer, Yoav Danieli

arXiv:2609.02498v1cs.DS

TL;DR

Navigability guarantees greedy search a progress-making edge toward every target, but worst-case sparse constructions are difficult; almost navigability permits a small fraction of targets to fail. This paper proves matching lower bounds using spherical cap neighborhoods and extremal graph constructions connected to the Zarankiewicz problem. The results establish the optimal almost-navigability scale and hard instances for full navigability, while the small-error constructions require higher dimension.

  • Problem

    Navigable graphs guarantee progress toward every target but can be costly, motivating the question of how sparse graphs can be when an ε fraction of targets may fail.

    Source: §1 · pp. 1, 3

  • Method

    The paper uses charging arguments on low-overlap neighborhoods, including random spherical caps and Euclidean realizations of extremal graphs.

    Source: §3 · p. 6, §6 · p. 10

  • Results

    Random Euclidean datasets force out-degree Ω(1/ε) for log n/n ≤ ε ≤ ε0, while full navigability can require Ω(n^3/2) edges in dimension O(√n log^3/2 n).

    Source: §1 · p. 3

  • Takeaways & Limitations

    The Zarankiewicz connection lets extremal graph constructions produce sharp navigation lower bounds through low-overlap neighborhood systems.

    Source: §6 · p. 10

    The algebraic witnesses require substantially larger dimension in the small-error regime, and it remains open whether the full phase or fully navigable endpoint can be realized in polylogarithmic or constant dimension.

    Source: §6 · p. 10

Abstract

from arXiv · show

Navigability is a fundamental property of graph-based search structures and plays an important role in the analysis of nearest-neighbor algorithms. Informally, a graph is navigable if, from any current point and toward any desired target, there is always an outgoing edge that moves strictly closer to that target. While this property provides a strong guarantee for greedy search, it can be inherently expensive: in the worst case, navigable graphs require $\Omega(n^{3/2})$ edges, where $n$ is the size of the dataset. Recently, Avi and Musco introduced $(1-\epsilon)$-almost navigability, a natural relaxation in which, from every current point, such a progress-making edge is required for almost all targets, while an $\epsilon$ fraction of targets may fail this condition \cite{avimusco2026almost}. They showed that every dataset admits such a graph with $O(n/\epsilon)$ edges. In this work, we prove a matching lower bound, establishing the optimality of their construction and giving a complete characterization of the sparsity achievable by almost-navigable graphs. For most values of $\epsilon$, our hard instances lie in Euclidean spaces of polylogarithmic dimension, across the full worst-case range of $\epsilon $, dimension $d=O(\sqrt{n}\log^{3/2} n)$ suffices. The same construction also sharpens our understanding of ordinary navigability: in the latter dimension, we exhibit datasets for which every navigable graph has $\Omega(n^{3/2})$ edges. Our proof reveals a surprising connection between almost navigability and the classical Zarankiewicz problem of constructing dense graphs with limited pairwise neighborhood overlap. This connection lets us translate extremal graph constructions into hard geometric instances for navigation, linking two seemingly different notions of graph sparsity.

1 Introduction

Navigability gives greedy graph search a progress-making edge toward every target, but can be expensive; almost navigability relaxes this guarantee by allowing an ε fraction of targets to fail. This work establishes matching worst-case sparsity scales for the relaxation and full navigability, using Euclidean constructions and a connection to extremal graph theory.

1 Introduction

  • The results show that both the 1/ε almost-navigability scale and the √n full-navigability scale are unavoidable, with a complete transition between them.The introduction states this conclusion while referring to the transition in equation (1).Source: §1 · p. 3
  • For log n/n ≤ ε ≤ ε0, random Euclidean datasets force every source to have out-degree Ω(1/ε), matching the known almost-navigability upper-bound scale.The stated construction uses dimension O(log n log^2(1/ε)).Source: §1 · pp. 2–3
  • The paper connects almost navigability to the Zarankiewicz problem: dense graphs avoiding K2,t+1 yield hard navigation instances, and navigation upper bounds imply bounds on such graph densities.Applying the known O(1/ε) construction recovers the O(tn^3/2) bound for K2,t+1-free graphs.Source: §1 · p. 3
  • For 0 ≤ ε ≤ C log n/n, the construction yields datasets in dimension O(√n log^3/2 n) requiring Ω(n^3/2) edges at full navigability.When ε = 0, dimension O(√n log n) suffices.Source: §1 · p. 3
  • The paper’s proof plan develops a global charging theorem, proves a spherical lower bound, then transfers extremal graph constructions through a Euclidean realization theorem.Füredi’s K2,t+1-free graphs supply the small-error construction.Source: §1 · p. 3

2 The global charging theorem

The global charging theorem lower-bounds the number of edges by counting source–target pairs that require progress and limiting how many targets a single edge can serve. Its strength comes from downward-closed target sets with large size and small pairwise overlap.

2 The global charging theorem

  • A downward-closed family assigns each target a set that contains the target and retains every point closer to that target than any member.Thus, if a source lies in its target’s set, a progress-making move stays in that set.Source: §2 · p. 4
  • Pair load Λ(B) is the largest number of target sets that can simultaneously contain the same pair of points, limiting how many targets one edge can serve.A progress-making edge from a source in Bt must have both endpoints in Bt.Source: §2 · p. 4
  • Charging surviving source–target pairs to improving edges gives a lower bound on edges because each edge receives at most Λ(B) charges.At most εn(n−1) ordered pairs may fail in a (1−ε)-almost navigable graph.Source: §2 · p. 4
  • Families of large sets with small pairwise overlap strengthen the lower bound; equal-radius metric balls also permit a pointwise out-degree bound.The section identifies local common-ball charging as a useful special case.Source: §2 · p. 5

3 The spherical construction

The spherical construction uses random points and cap neighborhoods whose pairwise overlaps are small, then applies local charging to force large out-degree. In the moderate-error regime, a single polylogarithmic-dimensional sample witnesses the lower bound simultaneously across ε values.

3 The spherical construction

  • The construction samples points uniformly from the sphere and takes, around each target, a cap containing an Θ(ε) fraction of the sphere.The resulting cap neighborhoods provide the sets used in the charging argument.Source: §3 · p. 5
  • Cap membership behaves nearly independently for distinct centers: one cap contains about pn sample points, while two typically overlap in about p^2n points.With p = Θ(ε), cap size controls the targets a source must serve, and overlap controls how many can reuse one edge.Source: §3 · p. 5
  • The proof must make the cap-size and overlap estimates hold simultaneously for all sample points and pairs of centers.The proof overview uses uniform Chernoff bounds for cap sizes and a geometric estimate for paired caps.Source: §3 · pp. 5–6
  • For n^−1 ≤ ε ≤ ε0 and d ≥ C log n log^2(1/ε), random sphere samples force every (1−ε)-almost navigable graph to have minimum out-degree Ω(1/ε).The theorem gives this conclusion with probability at least 1−n^−2.Source: §3 · p. 5
  • One sample in dimension O(log^3 n) simultaneously certifies the optimal Ω(1/ε) lower bound throughout the moderate-error regime.The corollary states probability at least 1−n^−1 and a minimum out-degree of at least c/ε.Source: §3 · p. 6

4 The Zarankiewicz correspondence

Dense graphs with limited neighborhood overlap yield hard Euclidean navigation instances, while universal navigation upper bounds conversely constrain Zarankiewicz density.

4 The Zarankiewicz correspondence

  • Closed neighborhoods of any finite graph can be realized as equal-radius Euclidean balls in a generic point set in R^(n−1).The realization makes each graph neighborhood N_H[t] the points within a common radius of t.Source: §4 · p. 7
  • Any universal upper bound on almost-navigability cost implies an upper bound on Zarankiewicz density.The correspondence works in both directions between navigation bounds and extremal graph bounds.Source: §4 · pp. 7–8
  • Small perturbations shorten distances for graph edges and lengthen them for nonedges, then remove ties while preserving a Euclidean realization.A radius between the two distance bands makes each graph neighborhood a metric ball.Source: §4 · pp. 7–8
  • The reverse inequality explains why the navigation law has the same square-root shape as the classical extremal bound.The stated relationship follows after optimizing over the graph H.Source: §4 · p. 8
  • At codegree zero, the extremal edge count is Z(n, 0) = ⌊n/2⌋.Source: §4 · p. 8
  • Dense K2,t+1-free graphs yield hard navigation instances because bounded codegree limits overlap between their neighborhoods.The Euclidean realization turns those neighborhoods into metric balls usable in the navigation counting argument.Source: §4 · pp. 6, 8

5 F¨uredi’s construction

Füredi graphs provide low-overlap neighborhoods for lower bounds, with compressed Euclidean realizations extending the worst-case tradeoff into the small-error regime.

5 F¨uredi’s construction

  • The Füredi-graph theorem witnesses its lower bound on a generic N-point Euclidean dataset in dimension O(q log N).Source: §5 · p. 9
  • Füredi’s graphs have minimum degree at least q − 1 and maximum codegree at most t, yielding a navigation lower bound of order q/t after realization.Each realized neighborhood ball contains at least q points, while two such balls intersect in at most t + 2 points; the construction gives a sourcewise bound.Source: §5 · pp. 8–9
  • A shifted adjacency matrix, spectral structure, and Johnson–Lindenstrauss projection compress the realization to O(q log N) dimensions while preserving edge–nonedge separation.A final small perturbation removes distance ties without changing the realized neighborhoods.Source: §5 · p. 9
  • For arbitrary n, the construction uses a choice of t and a prime q, then padding and global charging to cover the small-error part of the phase.The remaining error range is supplied by Theorem 3.1.Source: §5 · p. 9
  • At ε = 0, some generic datasets in dimension O(√n log n) require average out-degree Ω(√n), or Ω(n^(3/2)) edges.Source: §5 · p. 9
  • The worst-case degree cost follows Θ(min(1/ε, √n)), saturating at Θ(√n) once ε falls below order 1/√n.The fully navigable endpoint is part of this same phase transition.Source: §5 · pp. 9–10

6 Discussion

The paper builds navigation lower bounds from low-overlap neighborhood systems, connecting geometric constructions to bounded-codegree graphs and Zarankiewicz extremal constructions.

6 Discussion

  • Random spherical caps provide low-overlap systems directly in Euclidean space, while a realization theorem transfers bounded-codegree graphs into that framework.Source: §6 · p. 10
  • The connection to Zarankiewicz extremal graph theory lets algebraic constructions, including Füredi graphs, produce sharp navigation lower bounds.Source: §6 · p. 10
  • It remains open whether the full Θ(min(1/ε, √n)) phase, especially the fully navigable endpoint, can be realized in polylogarithmic or constant dimension.Source: §6 · p. 10

A.1 Proof of Corollary 2.3

The proof counts targets that require progress from a source, then bounds how many such targets any one outgoing edge can serve.

A.1 Proof of Corollary 2.3

  • Symmetry of the common-radius balls makes exactly |B_u| − 1 other targets satisfy u ∈ B_t.Source: §A.1 · p. 13
  • Almost navigability allows at most ε(n − 1) failures, so the remaining targets must be served by outgoing edges from u.Source: §A.1 · p. 13
  • An edge (u, v) that makes progress toward t can serve only when t ∈ B_u ∩ B_v, limiting its service to that ball intersection.Source: §A.1 · p. 13

A.2 Random-sphere estimates and supplementary consequences

The appendix gives a parameterized random-sphere lower-bound theorem and identifies the estimates used to prove it.

A.2 Random-sphere estimates and supplementary consequences

  • The parameterized statement assumes n ≥ n0 and 0 ≤ ε ≤ ε0, with dimension d ≥ C log n log^2(1/p).The constants are universal; the theorem passage also notes this statement is slightly stronger than Theorem 3.1 and convenient for the proof.Source: §A.2 · p. 13
  • With probability at least 1 − n^-2, every (1 − ε)-almost navigable graph on the sampled sphere points satisfies the theorem’s lower-bound conclusion.The supplied theorem passage does not include the conclusion’s formula.Source: §A.2 · pp. 13–14
  • The proof combines a uniform relative estimate for intersections of two spherical caps with the local charging inequality from Corollary 2.3.Source: §A.2 · p. 14

A.2.1 Relative spherical-cap estimates

The appendix develops spherical-cap tail estimates, including a relative two-cap estimate, to support the random-sphere lower bound.

A.2.1 Relative spherical-cap estimates

  • The required two-cap estimate is uniform even when the cap mass vanishes with n, a regime not covered by the cited idealized graph-search analyses.Source: §A.2.1 · pp. 14–15
  • The proof compares spherical marginal tails with Gaussian tails, then bounds correlated Gaussian joint upper tails using a two-dimensional specialization of Savage’s Mills-ratio method.The method is included in full to track constants.Source: §A.2.1 · pp. 14–16
  • A spherical-cap Chernoff argument uses the representation of a uniform sphere point as a normalized vector of independent standard Gaussians to establish a spherical subgaussian estimate.Source: §A.2.1 · p. 15
  • The two error terms arise from positive center correlation changing the Gaussian large-deviation exponent by Θ(ρa^2) and spherical-to-Gaussian comparison contributing exp(O(a^4/d)).The latter correction applies in the moderate-deviation range.Source: §A.2.1 · p. 16

A.2.2 Uniform incidence and the stronger parameterized theorem

The proof controls cap-neighborhood incidences and pairwise codegrees uniformly, enabling the parameterized random-sphere lower-bound argument.

A.2.2 Uniform incidence and the stronger parameterized theorem

  • The sampled points define common-radius cap neighborhoods that are downward-closed metric balls, so the global charging result applies to their incidences and codegrees.Source: §A.2.2 · p. 16
  • For every distinct center pair, the common-neighborhood codegree is at most C3 p^2 n with probability at least 1 − n^-2.The proof first bounds the conditional codegree probability by C4 p^2, then applies a union bound over pairs.Source: §A.2.2 · pp. 16–17
  • The proof controls center correlations before bounding codegrees, and combines coherence, codegree, and incidence failure probabilities to obtain the theorem’s stated probability.Source: §A.2.2 · p. 17
  • With high probability, each cap neighborhood contains at least p(n − 1)/2 other sample points.The incidence bound holds simultaneously for all centers, except with probability o(n^-3).Source: §A.2.2 · p. 17

A.2.3 Proof of Theorem A.1

This appendix develops graph-theoretic and projective-incidence constructions that yield sourcewise geometric lower bounds for almost-navigable and fully navigable graphs. It extends the constructions across parameter ranges using grids, spectral compression, and finite fields, and relates almost navigability to a classical Zarankiewicz bound.

A.2.3 Proof of Theorem A.1

  • When p = 8ε, Theorem A.1 gives minimum out-degree Ω(1/ε) and Ω(n/ε) arcs, and a dyadic grid extends the guarantee to intermediate ε values.The grid has O(log n) values; its union-bound failure probability is at most n⁻¹ for sufficiently large n, and each intermediate ε uses ε ≤ ε′ < 2ε.Source: §A.2.3 · p. 18, §A.2.4 · p. 18

A.3.1 The common-ball realization

  • A small perturbation of a regular-simplex squared-distance matrix realizes any simple graph as a distance-threshold graph on affinely independent Euclidean points with distinct pairwise distances.Edges have squared distance below 1 − α, while nonedges have squared distance above 1 − α/2.Source: §A.3.1 · pp. 18–19

A.3.2 The transference inequality

  • The transference argument applies the low-codegree obstruction to extremal Zarankiewicz graphs, and the resulting route recovers the classical Kővári–Sós–Turán theorem.The proof describes almost navigability as the intermediate object in this alternative derivation.Source: §A.3.2 · p. 20, §A.3.3 · p. 20

A.3.3 Proof of Corollary 4.2

  • For t = 0, an extremal graph is a matching; for t ≥ 1, the proof derives the classical Zarankiewicz bound from the rearranged transference inequality.The supplied passages state the qualitative recovery but omit the full displayed bound.Source: §A.3.3 · p. 20

A.4 Spectral compression of common-ball realizations

  • If a graph’s least adjacency eigenvalue is at least −L, its common-ball realization can be compressed to dimension O(L² log m) while preserving the graph.Johnson–Lindenstrauss projection preserves a gap between edge and nonedge distance bands; small perturbations then make the realization generic.Source: §A.4 · pp. 20–21

A.5 F¨uredi’s construction and the complete phase

  • For 1 ≤ t ≤ B log n, the paper gives a uniform logarithmic-codegree Zarankiewicz lower-bound construction with a generic common-radius Euclidean realization.The same construction supports the complete phase; in the sphere regime, AN(n, ε) = Ω(min{1/ε, √n}) in dimension O(log n log²(1/ε)).Source: §A.5 · pp. 23–24
  • For exact F¨uredi sizes N = q² − 1, a generic N-point set in dimension O(N log N) forces every fully navigable graph to satisfy the sourcewise endpoint bound.The same conclusion up to a factor of two holds when ε(N − 1) ≤ (q − 1)/2; the bound’s expression is not present in the supplied passage.Source: §A.5 · p. 25

A.6 Additional sourcewise constructions from projective incidence geometry

  • The appendix also introduces a symmetric family from projective point–hyperplane incidence graphs, where the charging bound applies uniformly at every source.The supplied passage identifies projective-plane incidence as the case m = 2 but does not include the family’s parameter counts.Source: §A.6 · p. 25
  • For every prime power q and m ≥ 2, a generic Euclidean N-point set forces G(u) ≥ k/(2 max{λ, 2}) = Ω(q); choosing ε = k/[4(N −1)] gives ε = Θ(1/q) and minimum out-degree Ω(1/ε).Here N = 2(1 + q + ··· + q^m), k = 1 + q + ··· + q^(m−1), and λ = 1 + q + ··· + q^(m−2).Source: §A.6 · p. 25
  • For every prime power q, the projective-plane endpoint gives a generic Euclidean set of N = 2(q^2 + q + 1) points whose fully navigable graphs require Ω(q) source out-degree.This follows from Theorem A.10 with m = 2 and ε = 0, yielding k = q + 1 and λ = 1.Source: §A.6 · pp. 25, 27
  • The projective-incidence corollary uses symmetric design identities as a sourcewise navigability obstruction, with discrete sizes and error values complementing rather than interpolating the uniform average-degree phase theorem.The construction combines incidence parameters, a local charging bound, and a Euclidean realization.Source: §A.6 · pp. 25, 27

AI Disclosure

  • OpenAI GPT-5.6-Sol generated the theoretical results and proofs in Sections 2–5 and Appendices A.1–A.6; the human authors independently verified the claims, proofs, and other content.The authors state that they take full responsibility for correctness, originality, and integrity.Source: AI Disclosure · p. 27
Loading 2609.02498v1…