Winner-label changes are bounded by suffix records
ProvedStabilityDichotomies.Bijunctive.root_change_count_le_suffix_record_countConsider distinct real candidate scores in a fixed removal order, with one final candidate always remaining. At each deletion, choose a maximizing candidate before and after the deletion and read any fixed label from it. The number of label changes is at most the number of deleted candidates that are strict maxima of their remaining suffix.
Preamble
import Mathlib open scoped Classical BigOperators
Formal statement
theorem StabilityDichotomies.Bijunctive.root_change_count_le_suffix_record_count {α : Type} [DecidableEq α] (n : ℕ)
(score : Fin (n+1) → ℝ) (hinj : Function.Injective score)
(label : Fin (n+1) → α) (before after : Fin n → Fin (n+1))
(hbefore : ∀ i, i.val ≤ (before i).val) (hafter : ∀ i, i.val + 1 ≤ (after i).val)
(hmaxBefore : ∀ i k, i.val ≤ k.val → score k ≤ score (before i))
(hmaxAfter : ∀ i k, i.val + 1 ≤ k.val → score k ≤ score (after i)) :
(∑ i : Fin n, if label (before i) ≠ label (after i) then (1 : ℕ) else 0) ≤
∑ i : Fin n, if ∀ k : Fin (n+1), i.val < k.val → score k < score (Fin.castSucc i)
then (1 : ℕ) else 0 := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, proof of Theorem 4.9, feasibility-root record analysis.