  There has been significant recent interest in graph-based nearest neighbor
search methods, many of which are centered on the construction of navigable
graphs over high-dimensional point sets. A graph is navigable if we can
successfully move from any starting node to any target node using a greedy
routing strategy where we always move to the neighbor that is closest to the
destination according to a given distance function. The complete graph is
navigable for any point set, but the important question for applications is if
sparser graphs can be constructed. While this question is fairly well
understood in low-dimensions, we establish some of the first upper and lower
bounds for high-dimensional point sets. First, we give a simple and efficient
way to construct a navigable graph with average degree $O(\sqrt{n \log n })$
for any set of $n$ points, in any dimension, for any distance function. We
compliment this result with a nearly matching lower bound: even under the
Euclidean metric in $O(\log n)$ dimensions, a random point set has no navigable
graph with average degree $O(n^{\alpha})$ for any $\alpha < 1/2$. Our lower
bound relies on sharp anti-concentration bounds for binomial random variables,
which we use to show that the near-neighborhoods of a set of random points do
not overlap significantly, forcing any navigable graph to have many edges.
