Lemma 1, p. 387 — in a representation, μ_H(u, v) = μ_G(x, C_v) for every x ∈ C_u
ProvedMetricGenerators.IsometryExt.lemma_1graph-isometrygraph-theorymetric-generatorp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be finite connected graphs, a strong metric generator of , an isometry, and let nonempty sets () represent in with respect to . Then for all and every ,
The lemma is the intermediate stage between a representation and an isometry: each candidate for sits at exactly the right distance from the candidate set of every other vertex.
Formalization Note The minimum is stated as two facts: some has , and every has . No forest hypothesis is needed.
Preamble
import Mathlib import Definitions.Def_MetricGenerators_IsometryExt_Basic import Definitions.Def_MetricGenerators_IsometryExt_Representation
Formal statement
namespace MetricGenerators.IsometryExt
/-- Sebő and Tannier, *On Metric Generators of Graphs*, Math. Oper. Res. 29(2):383–393 (2004),
DOI 10.1287/moor.1030.0070, p. 387, **Lemma 1**: if nonempty sets `C_u` represent `H` in `G` with respect to the
strong metric generator `T`, then for all `u, v ∈ V(H)` and `x ∈ C_u`, `μ_H(u, v) = μ_G(x, C_v)`,
where `μ_G(x, C_v) = min {μ_G(x, y) : y ∈ C_v}`.
Formalization Note: the minimum is encoded as "attained and a lower bound": some `y ∈ C_v` has
`μ_G(x, y) = μ_H(u, v)`, and every `y ∈ C_v` has `μ_H(u, v) ≤ μ_G(x, y)` (no `sInf` on `ℕ`).
There is no forest hypothesis: the lemma holds for every strong metric generator. -/
theorem lemma_1 {VH VG : Type*} [Fintype VH] [Fintype VG]
(H : SimpleGraph VH) (G : SimpleGraph VG) (hH : H.Connected) (hG : G.Connected)
(T : Finset VH) (hT : IsStrongMetricGenerator H T) (f : ↥T → VG)
(hf : IsIsometryOn H G T f) (C : VH → Set VG) (hC : Represents H G T f C) :
∀ u v : VH, ∀ x ∈ C u,
(∃ y ∈ C v, G.dist x y = H.dist u v) ∧ (∀ y ∈ C v, H.dist u v ≤ G.dist x y) := by sorry
end MetricGenerators.IsometryExt
Source
Sebő and Tannier, On Metric Generators of Graphs, Math. Oper. Res. 29(2):383–393 (2004), DOI 10.1287/moor.1030.0070, p. 387, Lemma 1 (proof p. 388); μ_G(X, Y) defined on p. 387
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.