Theorem 4, p. 388 — with H − T a forest, f extends to an isometry of H iff H has a representation in G; then C* is the greatest representation
ProvedMetricGenerators.IsometryExt.theorem_4graph-isometrygraph-theoryisometric-embeddingmetric-generatorp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be finite connected graphs, let be a strong metric generator of such that (the subgraph of induced on ) is a forest, and let be an isometry. Then:
- there exists an isometry from to extending if and only if there exist sets () that represent in with respect to ;
- if such an isometry exists, the sets () produced by the candidate procedure are the unique inclusionwise maximal sets that represent in with respect to : they form a representation, and
The theorem gives a good characterization of the extendability of an isometry given on a strong metric generator, under the forest condition; Figure 2 of the paper shows the characterization fails when contains a triangle.
Formalization Note "Unique inclusionwise maximal" is encoded as " is a representation containing every representation", i.e. a greatest element for componentwise inclusion, which is in particular the unique maximal one. An isometry here preserves all distances, not just adjacency.
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. 388, **Theorem 4** (both paragraphs). Let `H` and `G` be finite connected graphs,
`T` a strong metric generator of `H` such that `H − T` (the subgraph of `H` induced on
`V(H) ∖ T`) is a forest, and `f : (T, μ_H|T) → G` an isometry. Then
1. there is an isometry from `H` to `G` extending `f` if and only if there exist sets `C_u`
(`u ∈ V(H)`) that represent `H` in `G` with respect to `T`;
2. if such an isometry exists, the sets `C*_u` represent `H` in `G` with respect to `T` and
contain every representation (`C_u ⊆ C*_u` for all `u`).
Formalization Note: "the sets `C*_u` are the unique inclusionwise maximal sets that represent
`H`" is encoded as "`C*` is a representation that contains every representation" (a greatest
element of the representations under componentwise inclusion). A greatest element is the unique
maximal element; this is also what the paper's proof establishes. -/
theorem theorem_4 {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)
(hforest : (H.induce ((↑T : Set VH)ᶜ)).IsAcyclic)
(f : ↥T → VG) (hf : IsIsometryOn H G T f) :
((∃ φ : VH → VG, IsIsometry H G φ ∧ Extends T f φ) ↔
(∃ C : VH → Set VG, Represents H G T f C)) ∧
((∃ φ : VH → VG, IsIsometry H G φ ∧ Extends T f φ) →
Represents H G T f (cStar H G T f) ∧
∀ C : VH → Set VG, Represents H G T f C → ∀ u : VH, C u ⊆ cStar H G T f u) := 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. 388, Theorem 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.