A working lab for hyperbolic geometry: the saddle, the Poincaré disk and ball, Möbius maps, a live re-run of Kleinberg's greedy routing experiment, and what happens to the 6–7 color problem and frequency reuse when the plane stops being flat.
A sphere curves the same way in every direction, so lines that start parallel come together. A saddle curves up along one axis and down along the other. That is negative curvature, and its signature is that space opens up faster than you expect: circles have more circumference than 2πr, triangles have less than 180°, and parallel-looking lines spread apart.
A saddle is only a local picture. Its curvature is strongest at the center and fades outward, and Hilbert proved the full hyperbolic plane cannot sit smoothly inside ordinary 3D space. The pseudosphere has constant curvature −1 but is only a strip of the plane. That is why the disk models below exist: they fit the whole infinite plane into a picture by distorting lengths.
The entire hyperbolic plane is drawn inside a unit circle. The rim is infinitely far away. A step that looks small near the rim is actually huge, because the metric is ds = 2|dz| / (1 − |z|²). Straight lines (geodesics) are circular arcs that meet the rim at right angles, or diameters.
Drag the three corners. The angle sum is always below 180°, and the missing amount equals the triangle's area exactly (Gauss–Bonnet). The dashed ring around A is a circle of hyperbolic radius 1: watch it shrink on screen as A nears the rim while staying the same true size.
A Möbius map is z ↦ (az + b)/(cz + d). The ones that preserve the disk have the form z ↦ (αz + β)/(β̄z + ᾱ) with |α|² − |β|² = 1. They are the rigid motions of hyperbolic space: they slide and turn the plane while keeping every distance and angle. Composing two maps is just multiplying their 2×2 matrices, which is why a node can hand its child a few numbers and the child can compute its own position.
Below is the tiling Kleinberg uses: ideal d-gons whose corners sit on the rim, with the d-regular tree drawn through their centers. Drag to slide the plane. Every tile is congruent; the ones near the rim only look small.
Fix two adjacent tree points u and v = −u on the imaginary axis, and two maps: a(z) = −z swaps them, and b spins the tile around u by one slot. The root sets μ = a. Each node w computes its coordinate f(w) = μw−1(v) and tells its i-th child μ = bⁱ ∘ a ∘ μw. That is the whole distributed algorithm.
The edges of each tile are the "who is closer" boundaries. For any tree edge, the points closer to one end than the other form a half-plane bounded by exactly one tile edge, and tile edges never cross. That non-crossing is the proof that greedy routing can't get stuck.
Greedy routing: hand the packet to whichever neighbor is closest to the destination, and stop if no neighbor is closer. No routing tables. Left is a random sensor network laid out in physical space, set up as in Kleinberg's paper (50 nodes in a circle of radius √5, links of length ≤ 1). Right is the same network after Kleinberg's embedding of its minimum spanning tree into the Poincaré disk. Greedy runs on all links in both, only the coordinates differ.
Tap a node to set the source, tap another for the destination. The starting pair was picked because Euclidean greedy fails on it.
Kleinberg reported three kinds of number, and each is low for a different reason.
Failure rate 0%. This one is a theorem, not luck. In Euclidean coordinates a packet gets stuck at a "void": a node nearer the destination than all its neighbors, typical near holes and the network's edge. In the hyperbolic tree embedding such a node cannot exist, because the tree-path neighbor is always strictly closer.
Stretch 1.2 at the 80th percentile. The proof only promises routes no longer than the tree path, which is bad (4.1). Greedy does far better because the network is dense, about 8–10 links per node, so the closest-to-destination neighbor is often a non-tree link that jumps across branches. The hyperbolic distance roughly tracks tree distance, so jumping to a node in the destination's subtree registers as progress.
Congestion only 9% above Euclidean. Pure tree routing funnels traffic through the root and trunk (+233%). The same short-cuts that cut stretch also spread traffic off the trunk.
Run the experiment yourself. Each run builds fresh random networks, routes every ordered pair three ways and reports the same statistics.
Worst-case stretch is still linear in network size; Kleinberg lists that as open. Each join or leave can force O(n) re-embedding work, which Cvetkovski and Crovella later attacked with online embedding and "gravity–pressure" routing. And coordinates crowd toward the rim exponentially with tree depth, so deep trees need many bits per coordinate; Eppstein and Goodrich later gave a succinct version. In this re-run the deepest nodes sit about 10−7 to 10−8 from the rim, still comfortable in double precision.
The ball 𝔹d is the disk with more coordinates: points with |x| < 1, the same distance formula, geodesics that are arcs meeting the boundary sphere at right angles. Izgorodin embeds WordNet's 82,000 noun synsets in 𝔹10. Each extra dimension gives more directions to spread siblings, but the key resource is still the exponential room near the boundary.
Machine learning on the ball swaps Möbius maps for "Möbius addition" ⊕ and uses exp/log maps to step between the curved space and flat tangent planes. Izgorodin's Algorithm 1 is exactly that: log-map the points to the tangent plane at the current guess, average, exp-map back, repeat.
In 2D, x ⊕ y is the Möbius map z ↦ (z + y)/(1 + ȳz) applied to x: the same translations you dragged above. Izgorodin's own ablation found the ball mattered mostly for deciding nearest neighbors (about 5.7 points of mid-level clustering accuracy over Euclidean), not for the later averaging step.
The Hadwiger–Nelson problem asks: how many colors do you need so that no two points exactly 1 apart share a color? Since 1950 the answer was known to be between 4 and 7. Aubrey de Grey raised the lower bound to 5 in 2018. On September 23, 2026, OpenAI released a preprint proving that 5 colors cannot work, with the argument formalized in Lean, so the answer is now 6 or 7. It has not been peer reviewed yet.
The upper bound 7 comes from a picture any radio engineer knows. Tile the plane with hexagons slightly less than 1 across and color them in the 7-color pattern. Two points 1 apart can't be in the same hexagon, and same-colored hexagons are more than 1 apart. Drag the unit-length bar below and try to land both ends on one color.
This is the same 7-cell cluster as classic cellular frequency planning, where each hexagon is a cell and each color a channel group. The math problems differ, though. Hadwiger–Nelson forbids one exact distance; radio planning forbids every distance below a threshold, which is a much stricter and better-understood problem.
| Surface | Known colors needed |
|---|---|
| Flat plane, distance 1 | 6 or 7 |
| Hyperbolic plane, distance d | ≥ 4 for every d |
| …measurable colorings, large d | ≥ 6 |
| …upper bound | grows linearly in d |
No. At small d the hyperbolic plane looks flat, so it behaves like the flat case. At large d the exponential growth makes coloring harder, not easier: the best known colorings need more colors as d grows. Nothing drops to zero.
Here is the cleanest picture of why hyperbolic space fits trees. Take one hub with n spokes and try a greedy embedding: every leaf must be closer to the hub than to any other leaf, or a packet from one leaf to another would hop leaf-to-leaf and get stuck. In the flat plane two leaves need at least 60° between them, so at most 5 spokes fit. This is the same kissing argument behind Kleinberg's Lemma III.1, which shows normed spaces need Ω(log n) dimensions. In the hyperbolic plane, push the leaves outward and the room grows exponentially, so any n works once the leaves sit at radius about 2 ln(n/π).
Suppose cells were tiles of Kleinberg's hyperbolic tiling instead of hexagons, and co-channel cells had to be at least m tiles apart. Below, both are colored with the fewest channel groups that satisfy the rule. The surprise: with 6 neighbors per cell and m = 3, both need exactly 7 groups. The difference is how many co-channel cells sit at the reuse distance. The hexagon plane has 6. The hyperbolic tiling has 30.
Real radio waves travel through flat (Euclidean) space; Earth's curvature is negligible across a cell. So no physical network can choose to be hyperbolic. What is genuinely hyperbolic in a mobile network is its logical structure: core, regional edge, site, cell, beam, device. That is where Kleinberg-style addressing and Izgorodin-style hierarchy apply.
Ringed tile: the reference cell. Dotted tiles: its co-channel cells exactly m steps away, the "first tier" of interferers. On a tree of degree d the minimum is 2 groups for m = 2, d + 1 for m = 3 and 2d for m = 4. On hexagons it is the classic cluster size K = i² + ij + j²: 3, 7, 12.
Shannon–Hartley gives one channel's capacity, C = B log₂(1 + S/N). In a cellular network the denominator is noise plus interference from co-channel cells, so the real quantity is SINR = S / (N₀ + I). Coloring controls I. Using more colors (a bigger cluster K) pushes co-channel cells farther away and raises SINR, but each cell gets only B/K of the spectrum. Capacity per cell is roughly (B/K)·log₂(1 + SIR).
The textbook first-tier estimate on hexagons is SIR ≈ (√(3K))γ / 6, where γ is the path-loss exponent. Move γ and see which K wins.
For realistic γ, small clusters win: dividing the spectrum costs more than the extra SINR earns. That is why LTE and 5G run reuse-1 (every cell uses every frequency) and manage interference with scheduling, power control and beamforming instead of a fixed coloring. Wi-Fi 6/7 "BSS coloring" is related but different: it tags each network with one of 63 colors so a radio can tell a neighbor's frame from its own and transmit over it more aggressively. It is a reuse aid, not a frequency plan.
So the coloring number never "drops to zero". It trades against bandwidth, and the best trade depends on propagation, not on the curvature of a map.