Close maxima of disjoint groups imply a small top gap
ProvedStabilityDichotomies.Bijunctive.two_groups_close_maxima_give_small_top_gapLet be disjoint nonempty finite sets and be real-valued on their union. If the maxima of on and differ by at most , then the two largest values of on differ by at most . This is the deterministic order-statistic step used in bounding the probability of violating a retained non-unit clause.
Preamble
import Mathlib open scoped Classical
Formal statement
theorem StabilityDichotomies.Bijunctive.two_groups_close_maxima_give_small_top_gap {α : Type} [DecidableEq α]
(s t : Finset α) (hs : s.Nonempty) (ht : t.Nonempty) (hdis : Disjoint s t)
(f : α → ℝ) (a b : α) (ha : a ∈ s) (hb : b ∈ t)
(hamax : ∀ k ∈ s, f k ≤ f a) (hbmax : ∀ k ∈ t, f k ≤ f b)
(r : ℝ) (hab : f a - f b ≤ r) (hba : f b - f a ≤ r) :
∃ i ∈ s ∪ t, ∃ j ∈ s ∪ t, i ≠ j ∧
(∀ k ∈ s ∪ t, f k ≤ f i) ∧
(∀ k ∈ s ∪ t, k ≠ i → f k ≤ f j) ∧
f i - f j ≤ r := 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, approximation paragraph.