Euclidean metric sparsifiers, , , ,
DefinitionBourgainUnion_Euclidean_Supplement_SparsifierModelLet be a finite set, a partition of into nonempty sets, and the class of pseudometrics on whose restriction to every is Euclidean. Fix .
- A weighted graph on (nonnegative symmetric weights, zero diagonal, no weight outside ) is a Euclidean metric sparsifier of a weighted graph on with quality if, for every Euclidean pseudometric on ,
with the same for every (Definition 4.1, inequality (4)); is the published optimal extension cost (3). 2. is the least such that every loopless weighted graph on has a sparsifier of quality . 3. is the least such that for every , every and every map that is -Lipschitz for , some extends and is -Lipschitz for on all of . 4. and are the suprema of and over all finite sets , all partitions of into at most nonempty sets, and all choices .
All four quantities take values in : an infimum over an empty set of admissible constants is .
Formalization Note Lipschitz conditions in are with respect to the varying pseudometric , not a fixed metric instance; the suprema range over finite types in Type.
import Mathlib
import Definitions.Def_BourgainUnion_Euclidean_GraphModel
set_option autoImplicit false
open scoped BigOperators ENNReal
noncomputable section
namespace BourgainUnion.Euclidean.Supplement
open BourgainUnion.Euclidean
/-- Definition 4.1, p. 13: `h` is a weighted graph on `A` (nonnegative, symmetric, zero diagonal,
no weight outside `A × A`) and a Euclidean metric sparsifier of the graph with weights `w` for the
class `D` of `U`, with quality `Q ≥ 1`: inequality (4) holds for every Euclidean `ρ` on `A`, with
the same `h` for all such `ρ`. -/
def IsSparsifier {X : Type*} [Fintype X] {k : ℕ} (U : Fin k → Set X) (A : Finset X)
(w h : X → X → ℝ) (Q : ℝ) : Prop :=
1 ≤ Q ∧ (∀ x y, 0 ≤ h x y) ∧ (∀ x y, h x y = h y x) ∧ (∀ x, h x x = 0) ∧
(∀ x y, x ∉ A ∨ y ∉ A → h x y = 0) ∧
∀ ρ : X → X → ℝ, RawEuclidean ρ (A : Set X) →
ENNReal.ofReal (energy h ρ A / Q) ≤ minExt U A ρ w ∧
minExt U A ρ w ≤ ENNReal.ofReal (energy h ρ A)
/-- `Q(D, A)`, p. 13: the least quality guaranteed for every (loopless) weighted graph on `X`;
`⊤` when no finite quality works. -/
def sparsifierQuality {X : Type*} [Fintype X] {k : ℕ} (U : Fin k → Set X) (A : Finset X) :
ℝ≥0∞ :=
sInf {q | ∃ Q : ℝ, (∀ G : ClusterDecomp.WGraph X, Loopless G →
∃ h : X → X → ℝ, IsSparsifier U A G.w h Q) ∧ q = ENNReal.ofReal Q}
/-- `e(D, A)`, pp. 13–14: the least `Λ ≥ 1` such that, for every pseudometric `d` in the class
`D` of `U`, every `L`-Lipschitz map `(A, d) → ℓ₂` extends to a `ΛL`-Lipschitz map `(X, d) → ℓ₂`.
Lipschitz conditions are with respect to `d`, which varies over the class. -/
def extensionConstantD {X : Type*} {k : ℕ} (U : Fin k → Set X) (A : Set X) : ℝ≥0∞ :=
sInf {q | ∃ Λ : ℝ, 1 ≤ Λ ∧
(∀ d : X → X → ℝ, MetricClass U d → ∀ L : ℝ, 0 ≤ L → ∀ f : X → H2,
(∀ x ∈ A, ∀ y ∈ A, dist (f x) (f y) ≤ L * d x y) →
∃ F : X → H2, Set.EqOn F f A ∧ ∀ x y, dist (F x) (F y) ≤ Λ * L * d x y) ∧
q = ENNReal.ofReal Λ}
/-- `Q_k`, p. 14: the supremum of `Q(D, A)` over finite sets `X`, partitions of `X` into at most
`k` nonempty sets, and choices `A = U_i`. -/
def Qk (k : ℕ) : ℝ≥0∞ :=
⨆ (X : Type) (_ : Fintype X) (j : ℕ) (_ : j ≤ k) (U : Fin j → Set X) (_ : Partition U)
(i : Fin j), sparsifierQuality U (U i).toFinite.toFinset
/-- `e_k`, p. 14: the supremum of `e(D, A)` over the same data as `Q_k`. -/
def ek (k : ℕ) : ℝ≥0∞ :=
⨆ (X : Type) (_ : Fintype X) (j : ℕ) (_ : j ≤ k) (U : Fin j → Set X) (_ : Partition U)
(i : Fin j), extensionConstantD U (U i)
end BourgainUnion.Euclidean.Supplement