nucleation

LIT-1155: The geometry of graphs and some of its algorithmic applications

3 min read

Properties6
StatusActive — read 2026-10-16 (NOTE-928) in full; worth reading as the place where Bourgain's O(log n) embedding of finite metrics into Euclidean space is restated, reproved by distances to random sets of every scale, and shown tight: constant-degree expanders need distortion Ω(log n) in ℓ_p, 1 ≤ p ≤ 2, of any dimension, because their gap between multicommodity flow and cut is Ω(log n). The same embeddings bound that gap by O(log k) for k commodities. Read it knowing that the O(log n) dimension comes from Johnson–Lindenstrauss, not from the construction, which uses O(log² n) coordinates; that the lower bound rests on Leighton and Rao's gap, cited; that constants are unspecified; and that it says nothing about trees in ℓ₂, for which Sala et al. cite it. Filed as THEORY-394.
Version2
Tagsmathematics, operations-research
ExtendsLIT-1161 — On Lipschitz embedding of finite metric spaces in Hilbert space
Cited as “paper” byNOTE-928 — Linial, London & Rabinovich — the geometry of graphs
Cited as “source” byTHEORY-394 — Every n-point metric space embeds in Euclidean space of O(log n) dimensions with distortion O(log n), by distances to random sets of every scale followed by Johnson–Lindenstrauss, and constant-degree expanders need distortion Ω(log n) in every ℓ_p with 1 ≤ p ≤ 2, of any dimension, so O(log n) is tight in the worst case; the constants are unspecified, the lower bound rests on Leighton and Rao's flow–cut gap, and nothing is shown for trees or for p > 2

Graph View

Nathan Linial, Eran London and Yuri Rabinovich (1995), “The geometry of graphs and some of its algorithmic applications”, Combinatorica 15(2): 215–245 — doi:10.1007/BF01200757

Key takeaways

From the reading, NOTE-928.

  • Bourgain’s theorem as stated (Theorem 3.2(1)). “Every n-point metric space (X, d) can be embedded in an O(log n)-dimensional Euclidean space with an O(log n) distortion.”
  • Reproved and made algorithmic (Claim 5). Distances to O(log n) random sets of each size 2ˡ, O(log² n) coordinates in all, give distortion O(log n) in ℓ_p for any p ≥ 1, in random polynomial time. Johnson–Lindenstrauss (Theorem 3.1, quoted as t = O(log n/ε²)) brings ℓ₂ down to O(log n) dimensions.
  • Least distortion computable (Claim 2, Corollary 3.5). c₂(X) is found to within any ε by semidefinite programming, with a dual characterization over positive semidefinite Q with Q·1⃗ = 0⃗.
  • Tight (Proposition 4.2). Every embedding of a constant-degree expander into ℓ_p, 1 ≤ p ≤ 2, of any dimension, has distortion Ω(log n). Constant distortion in any norm needs Ω(log² n) dimensions. The proof uses Leighton and Rao’s Ω(log n) flow–cut gap.
  • Multicommodity flow (Theorem 4.1). The flow–cut gap is at most the ℓ₁ distortion of the LP-optimal metric, so O(log k) for k commodities, with a deterministic algorithm for the cut.
  • Isometric dimension (§5). Trees O(log n), tight; dim(Kₙ) = ⌈log₂ n⌉; dim(C₂ₘ) = m; dim(m-cube) = m. Separators (Theorem 6.1) and low-diameter decompositions (Theorem 7.1) for low-dimensional graphs.
  • Scope. Constants unspecified; the paper cites neither Johnson and Lindenstrauss’s Problem 4 nor any Euclidean lower bound for trees.

Standing in the record

Filed on 2026-10-16 as later work flagged by NOTE-930 and cited, unread, by NOTE-679 and NOTE-905, and read the same day in NOTE-928. It is how the record reads Bourgain’s theorem (LIT-1161) until a copy of that paper is supplied. Filed as THEORY-394.

The reading confirms NOTE-930’s unchecked remark as far as this paper goes. It states Bourgain’s O(log n), and it shows that expanders need Ω(log n) in ℓ₂. The step to Johnson and Lindenstrauss’s Problem 4, answered in the negative, is the record’s inference, since the paper does not mention the problem. It also confirms NOTE-905’s Fact 4, the embedding of integer ℓ₁ into Hamming space (Corollary 3.8’s proof).

It does not support NOTE-679’s citation. Sala et al. cite it as “Bourgain’s theorem” for the claim that Euclidean space cannot embed trees with low distortion in any dimension. The paper’s Bourgain theorem is an upper bound, its lower bound is for expanders, and its tree result is an isometric embedding in ℓ∞.

operations-research is for the multicommodity flow and cut results. The clustering remark in §3.2 is not an instruction for machine-learning practice, and the paper is held here only.

Backlinks