Lemma 6.4 — cheap hubs in pseudometrics
OpenSparseIncidenceHom.WidthComparison.Supplement.lemma_6_4combinatoricsmetric-spacesp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There is an absolute constant such that, for every pseudometric on with , some satisfies
Here a pseudometric is nonnegative, symmetric, vanishes on the diagonal and satisfies the triangle inequality; distinct points may be at distance zero, and . The lemma supplies a hub whose total distance to all points is small whenever no two large groups are far apart.
Formalization Note is to base two; is Fin k; the maximum is a supremum over a finite nonempty set.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_SparseIncidenceHom_WidthComparison_Supplement_Widths
Formal statement
namespace SparseIncidenceHom.WidthComparison.Supplement open SparseIncidenceHom.WidthComparison /-- Lanzinger, STOC 2027 submission #662, Lemma 6.4, p. 24 (inequality (10)). -/ theorem lemma_6_4 : ∃ C_H : ℝ, 0 < C_H ∧ HubBound C_H := by sorry end SparseIncidenceHom.WidthComparison.Supplement
Source
Matthias Lanzinger, STOC 2027 submission #662 (October 2026), p. 24, Lemma 6.4 (inequality (10)); proof pp. 24–25