A bounded-degree memory-one certificate for the independence polynomial
ProvedZeroFreeRRG.Hardcore.hardcore_memory_one_certificateFor a graph of maximum degree at most , suppose , , , and . Assign to each initial state and to each one-step state. This is a valid memory-one certificate for the independence polynomial. The missing parent neighbor accounts for the exponent in noninitial states.
Preamble
import Mathlib import Definitions.Def_LocalLemmaHierarchy_Completeness_Graph import Definitions.Def_LocalLemmaHierarchy_Completeness_Memory set_option autoImplicit false open LocalLemmaHierarchy.Completeness open scoped Classical BigOperators
Formal statement
theorem ZeroFreeRRG.Hardcore.hardcore_memory_one_certificate {V : Type} [Fintype V] (G : SimpleGraph V) (o : NeighborOrders G)
(d : ℕ) (hd : 1 ≤ d) (hG : ∀ v, G.degree v ≤ d)
(p c : ℝ) (hp : 0 ≤ p) (hc0 : 0 ≤ c) (hc1 : c < 1)
(hbulk : p * ((1-c)⁻¹)^(d-1) ≤ c)
(hroot : p * ((1-c)⁻¹)^d < 1) :
IsMemCertificate (indRep G o) 1 (fun _ => p)
(fun s => if s.moves = [] then p*((1-c)⁻¹)^d else c) := by sorrySource
Supporting proof of the hardcore zero-free radius in Chen–Wang–Zhang, 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, Lemma 5.7.