§2, p. 387 — the C^(0)_u are pairwise disjoint and C^(0)_t = {f(t)} for t ∈ T
ProvedMetricGenerators.IsometryExt.initial_candidatesgraph-isometrygraph-theorymetric-generatorp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be finite connected graphs, a metric generator of , and an isometry. Let be the initial candidate sets. Then
- whenever ;
- for every .
These are the first observations about the candidate procedure: the candidates for distinct vertices never collide, and the vertices of have exactly their prescribed image as candidate.
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, §2, p. 387 (unnumbered): as `T` is a metric generator of `H`, the initial candidate
sets `C^(0)_u` (`u ∈ V(H)`) are pairwise disjoint; using also that `f` is an isometry on `T`,
`C^(0)_t = {f(t)}` for every `t ∈ T`.
Formalization Note: `H` and `G` are finite and connected (standing assumption, p. 383). The page
invokes only the metric-generator property of `T`, which is the hypothesis used here. -/
theorem initial_candidates {VH VG : Type*} [Fintype VH] [Fintype VG]
(H : SimpleGraph VH) (G : SimpleGraph VG) (hH : H.Connected) (hG : G.Connected)
(T : Finset VH) (hT : IsMetricGenerator H T) (f : ↥T → VG) (hf : IsIsometryOn H G T f) :
(∀ u v : VH, u ≠ v → Disjoint (cand H G T f 0 u) (cand H G T f 0 v)) ∧
(∀ t : ↥T, cand H G T f 0 t = {f t}) := 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, §2 (unnumbered, after the definition of C^(0)_u)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.