Supermodular finite-difference telescoping inequality
ProvedZeroFreeRRG.Hardcore.finite_supermodular_telescopingLet be a real-valued function of finite sets whose mixed difference is nonnegative whenever two new elements are inserted. For every finite set ,
This is the finite telescoping inequality underlying the supermodularity step in the hardcore Bethe monotonicity argument.
Preamble
import Mathlib open scoped BigOperators
Formal statement
namespace ZeroFreeRRG.Hardcore
theorem finite_supermodular_telescoping {ι : Type} [DecidableEq ι] (v : Finset ι → ℝ)
(hSM : ∀ S : Finset ι, ∀ i j, i ∉ S → j ∉ S → i ≠ j →
v (insert i (insert j S)) + v S ≥ v (insert i S)+v (insert j S))
(S : Finset ι) :
v S ≥ v ∅ + ∑ i ∈ S, (v {i} - v ∅) := by sorry
end ZeroFreeRRG.HardcoreSource
Chen, Wang, and Zhang, Zero-Freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1461.pdf, proof of Lemma 4.17, printed p. 30.