A finite walk uses at most its length many arc labels
ProvedStabilityDichotomies.Bijunctive.finite_walk_uses_at_most_length_labelsIf each directed arc in a walk carries at least one label, a walk of length admits a choice of at most labels covering all of its arcs. The labels can represent constraint occurrences whose deletions can destroy that walk.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Bijunctive open scoped Classical BigOperators open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.finite_walk_uses_at_most_length_labels {α ι : Type} (arc : ι → α → α → Prop)
(n : ℕ) (a b : α) (hw : WalkLength (fun x y => ∃ i, arc i x y) n a b) :
∃ S : Finset ι, S.card ≤ n ∧
WalkLength (fun x y => ∃ i ∈ S, arc i x y) n a b := 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, graph-deletion sensitivity step.