Lemma 4.7 — Local configurations remain valid after adjoining any multiset of spawned labels; both assertions, for arbitrary L.
OpenGreedyColoringLCA969.LowerBound.Supplement.lemma_4_7graph-theorylocal-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any label set, a labeling problem on all finite simple graphs, an extension rule, and a radius-one local verifier for . Assume every label of is produced by on some graph in some vertex ordering. Then both statements hold:
- For every finite multiset , .
- For all finite multisets , if for every occurring in , then
The two assertions describe exactly the local views that remain acceptable as spawned labels are added. No finiteness hypothesis on is imposed.
Differences from the source:
- encoding: all finite graphs and arbitrary orderings, with multiset union → graphs on Fin n, permutations of Fin n, and Multiset addition; reason: every finite labeled graph and ordering is represented; addition preserves multiplicities
Preamble
import Definitions.Def_GreedyColoringLCA969_LowerBound_Supplement_Labeling open scoped ENNReal BigOperators open MeasureTheory Classical set_option autoImplicit false
Formal statement
namespace GreedyColoringLCA969.LowerBound.Supplement
theorem lemma_4_7 {L : Type} (P : LabelProblem L) (F : Multiset L → L)
(C : Set (L × Multiset L)) (hext : IsExtensionRule P F)
(hloc : IsLocalVerifier P C) (hreal : AllLabelsRealizable F) :
(∀ S : Multiset L, (F S, S) ∈ C) ∧
(∀ S T : Multiset L, (∀ α ∈ T, Spawns F (F S) α) → (F S, S + T) ∈ C) := by sorry
end GreedyColoringLCA969.LowerBound.Supplement
Source
Zi Song Yeoh, Krzysztof Onak, Dragos-Florian Ristache, STOC 2027 submission #969 (October 2026), p. 17 (PDF 18), Lemma 4.7