Markoy Random Fields (MRF) Gibbs distribution u:voelg] network G(E): L()II Ac(ou,o)IIbu(o) e=(u,v)∈E o proper q-coloring: X∈[q] ⊙bv 1 independent set: a-b周&-日 ∈[g]y follows u local conflict colorings [Fraigniaud,Heinrich,Kosowski'16] Ae∈{0,1}9x9,b,∈{0,1}9 Hammersley-Clifford theorem (Fundamental Thm of random fields): MRFs are universal for conditional independent positive distributions.Markov Random Fields network G(V,E): Ae bv Xv∈[q] u v X ~ 2 [q] V follows µ (MRF) • Gibbs distribution µ : ∀σ∈[q]V µ(￾) / Y e=(u,v)2E Ae(￾u, ￾v) Y v2V bv(￾v) • proper q-coloring: Ae = 2 6 6 6 4 0 0 ... 0 3 7 7 7 5 1 1 bv = 2 6 4 1 . . . 1 3 7 5 • independent set: bv =  1 1 ￾ Ae =  1 1 1 0￾ Hammersley–Clifford theorem (Fundamental Thm of random fields): MRFs are universal for conditional independent positive distributions. • local conflict colorings : [Fraigniaud, Heinrich, Kosowski’16] Ae 2 {0, 1}q⇥q, bv 2 {0, 1}q