§2, p. 387 — C^(0) ⊇ C^(1) ⊇ ⋯ stabilizes after at most |V(G)| steps
ProvedMetricGenerators.IsometryExt.candidates_stabilizegraph-isometrygraph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be finite connected graphs, and , and let , be the candidate procedure. Then the sequences are decreasing,
and they stabilize after at most steps: for every ,
This justifies taking as the final output of the procedure.
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): the sequence `C^(0) ⊇ C^(1) ⊇ ⋯` is decreasing (and so is
each sequence `C^(i)_u`), and the procedure is stabilized after at most `n := |V(G)|` steps:
`C^(k) = C^(n)` and `C^(k)_u = C^(n)_u` for every `k ≥ n` and every `u ∈ V(H)`.
Formalization Note: `H` and `G` are finite and connected (standing assumption, p. 383); the
statement holds for every `T` and `f`. -/
theorem candidates_stabilize {VH VG : Type*} [Fintype VH] [Fintype VG]
(H : SimpleGraph VH) (G : SimpleGraph VG) (hH : H.Connected) (hG : G.Connected)
(T : Finset VH) (f : ↥T → VG) :
(∀ i : ℕ, candSet H G T f (i + 1) ⊆ candSet H G T f i ∧
∀ u : VH, cand H G T f (i + 1) u ⊆ cand H G T f i u) ∧
(∀ k : ℕ, Fintype.card VG ≤ k →
candSet H G T f k = candSet H G T f (Fintype.card VG) ∧
∀ u : VH, cand H G T f k u = cand H G T f (Fintype.card VG) 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. 387, §2 (unnumbered, after the recursive definition of C^(i))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.