§2, p. 386 — a strong metric generator is a metric generator
ProvedMetricGenerators.IsometryExt.strong_is_metric_generatorgraph-theorymetric-generatorp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite connected graph and a strong metric generator of : for every pair of vertices there is with or . Then is a metric generator of :
The paper notes this right after defining strong metric generators; Figure 1 of the paper shows that the converse fails. It lets the later arguments use the disjointness that a metric generator provides.
Formalization Note Connectivity is the paper's standing assumption; distances are -valued.
Preamble
import Mathlib import Definitions.Def_MetricGenerators_IsometryExt_Basic
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. 386 (unnumbered): "a strong metric generator is always a metric generator".
Formalization Note: stated for a finite connected graph (the paper's standing assumption, p. 383;
the definition of a strong metric generator is made for connected graphs). -/
theorem strong_is_metric_generator {V : Type*} [Fintype V] (G : SimpleGraph V)
(hG : G.Connected) (S : Finset V) (hS : IsStrongMetricGenerator G S) :
IsMetricGenerator G S := 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. 386, §2 (unnumbered, paragraph after the definition of a strong metric generator)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.