Increasing vertex-entropy increments for coloring
ProvedZeroFreeRRG.Hardcore.coloring_vertex_entropy_incrementFix and a coloring cavity law . For each integer , write for independent cavity messages. Then . This is the discrete convexity inequality proved via exchangeability and relative-entropy data processing in Lemma 4.27.
Preamble
import Definitions.Def_ZeroFreeRRG_Hardcore_BetheFunctional open MeasureTheory
Formal statement
namespace ZeroFreeRRG.Hardcore
theorem coloring_vertex_entropy_increment (q : ℕ) (hq : 3 ≤ q)
(ν : ProbabilityMeasure ((.potts q : Model).Spin → ℝ)) (hν : ν ∈ cavityLaws (.potts q) 0)
(k : ℕ) :
let A := fun n : ℕ => ∫ xs, xlogx (vertexFactor (.potts q) 0 n xs)
∂(Measure.pi fun _ : Fin n => (ν : Measure ((.potts q : Model).Spin → ℝ)))
A (k+1)-A k ≤ A (k+2)-A (k+1) := 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.27, printed p. 34.