Forcing spins has bounded fiber size
ProvedZeroFreeRRG.Hardcore.force_spins_fiber_card_boundFor a finite set of vertices S and a finite spin set A, at most |A|^|S| configurations map to any prescribed configuration after all spins in S are forced to a fixed spin.
Preamble
import Mathlib set_option autoImplicit false open scoped Classical BigOperators
Formal statement
theorem ZeroFreeRRG.Hardcore.force_spins_fiber_card_bound {V A : Type*} [Fintype V] [DecidableEq V] [Fintype A]
(S : Finset V) (a₀ : A) (τ : V → A) :
((Finset.univ : Finset (V → A)).filter
(fun σ => (fun v => if v ∈ S then a₀ else σ v) = τ)).card ≤
(Fintype.card A) ^ S.card := by sorrySource
Chunyang Wang et al., Zero-freeness for random regular graphs up to the replica symmetry breaking threshold, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/1461.pdf, Appendix E.3, proof of Lemma 4.20, Step 1 (supporting argument).