Improved Bounds for Sampling Colorings Sitan Chen, Ankur Moitra Merged with: Michelle Delcourt, Guillem Perarnau, Luke Postle Preliminaries Background Main Question: Can we approximately count k-colorings in bounded-degree graphs? When do such colorings even exist? Brooks Theorem: Any graph G of maximum degree d has a (d+1)coloring. Conjecture: We can approximately count arbitrarily well* as long as !

*for any , multiplicative -approximation in time Motivation- counting complexity Can we efficiently approximately count for #P-complete problems whose decision version is easy? matchings (monomer-dimer systems) independent sets (hardcore model) perfect matchings (dimer systems) partition function of Ising model satisfying assignments in bounded-degree CNFs estimating volume of a convex body Motivation- phase transitions In inference in graphical models: Phase

transitions onset of computational hardness #k-colorings is partition function of antiferromagnetic Potts model at zero temperature Uniqueness: decay of long-range correlations [Jonasson 01]: Uniqueness for the infinite dregular tree at Motivation- phase transitions In inference in graphical models:

Phase transitions onset of computational hardness #k-colorings is partition function of antiferromagnetic Potts model at zero temperature Uniqueness: decay of long-range correlations [Jonasson 01]: Uniqueness for the infinite dregular tree at Motivation- phase transitions

Does uniqueness threshold coincide with computational hardness threshold for approximately counting k-colorings? [Sly, Sun 12] + [Weitz 06] + [Sinclair, Srivastava, Thurley 11]: Yes for general antiferromagnetic 2-spin systems on boundeddegree graphs [Galanis, Stefankovic, Vigoda 14]: Hardness for kcolorings at and antiferromagnetic Potts model in (conjectured) non-uniqueness region What about the algorithmic side? Counting vs. sampling Theorem (informal): Given an approximate sampler, you can approximately count. Proof: Successively remove edges of G to get Z(G) = is n isolated vertices, so

Simple candidate sampler Single-site Glauber dynamics Color: 1. Initialize with arbitrary coloring 2. Repeat for T steps: a. Pick a random vertex v and a random color c. b. Recolor v with c if allowed. 3. Output final coloring Fact: If , the stationary distribution is the uniform distribution over kcolorings.

Conjecture: If , single-site Glauber dynamics mixes in time . Simple candidate sampler Single-site Glauber dynamics Color: 1. Initialize with arbitrary coloring 2. Repeat for T steps: a. Pick a random vertex v and a random color c. b. Recolor v with c if allowed. 3. Output final coloring Fact: If , the stationary distribution

is the uniform distribution over kcolorings. Conjecture: If , single-site Glauber dynamics mixes in time . Simple candidate sampler Single-site Glauber dynamics Color: 1. Initialize with arbitrary coloring 2. Repeat for T steps: a. Pick a random vertex v and a random color c. b. Recolor v with c if allowed.

3. Output final coloring Fact: If , the stationary distribution is the uniform distribution over kcolorings. Conjecture: If , single-site Glauber dynamics mixes in time . Simple candidate sampler Single-site Glauber dynamics Color: 1. Initialize with arbitrary coloring 2. Repeat for T steps:

a. Pick a random vertex v and a random color c. b. Recolor v with c if allowed. 3. Output final coloring Fact: If , the stationary distribution is the uniform distribution over kcolorings. Conjecture: If , single-site Glauber dynamics mixes in time . Simple candidate sampler Single-site Glauber dynamics Color:

1. Initialize with arbitrary coloring 2. Repeat for T steps: a. Pick a random vertex v and a random color c. b. Recolor v with c if allowed. 3. Output final coloring Fact: If , the stationary distribution is the uniform distribution over kcolorings. Conjecture: If , single-site Glauber dynamics mixes in time . Simple candidate sampler Single-site Glauber dynamics

Color: 1. Initialize with arbitrary coloring 2. Repeat for T steps: a. Pick a random vertex v and a random color c. b. Recolor v with c if allowed. 3. Output final coloring Fact: If , the stationary distribution is the uniform distribution over kcolorings. Conjecture: If , single-site Glauber dynamics mixes in time .

Simple candidate sampler Single-site Glauber dynamics Color: 1. Initialize with arbitrary coloring 2. Repeat for T steps: a. Pick a random vertex v and a random color c. b. Recolor v with c if allowed. 3. Output final coloring Fact: If , the stationary distribution is the uniform distribution over kcolorings.

Conjecture: If , single-site Glauber dynamics mixes in time . Prior work k/d Jerrum 95 Prior work k/d Jerrum 95 Vigoda Vigoda 99 99 Prior work

k/d Jerrum 95 Vigoda Vigoda 99 99 Dyer, Dyer, Frieze Frieze 01 01 degree girth Prior work

k/d Jerrum 95 Vigoda Vigoda 99 99 Dyer, Dyer, Frieze Frieze 01 01 Molloy Molloy 02 02 degree

girth Prior work k/d Jerrum 95 Vigoda Vigoda 99 99 Dyer, Dyer, Frieze Frieze 01 01 Molloy 02 Molloy 02 Hayes 03 1.489

Hayes 03 1.489 degree girth Prior work k/d Jerrum 95 Vigoda Vigoda 99 99 Dyer, Dyer, Frieze Frieze 01

01 Molloy 02 Molloy 02 Hayes 03 Hayes 03 Hayes, Vigoda 03 Hayes, Vigoda 03 Dyer, Frieze, Hayes, Dyer, Frieze, Hayes, Vigoda 04 Vigoda 04 1.489

1.489 1.489 1.489 1.763 1.763 degree girth Prior work k/d Jerrum 95 Vigoda Vigoda 99

99 Dyer, Dyer, Frieze Frieze 01 01 Molloy 02 Molloy 02 Hayes 03 Hayes 03 Hayes, Vigoda 03 Hayes, Vigoda 03 Dyer, Frieze, Hayes, Dyer, Frieze, Hayes, Vigoda

04 Vigoda 04 1.489 1.489 1.489 1.489 1.763 1.763 degree girth Prior work

k/d Hayes, Vigoda, Vera 15 Mossel, Mossel, Sly Sly 08 08 assumptions planar Efthymiou, Efthymiou, Hayes, Hayes, Stefankovic, Stefankovic, Vigoda

Vigoda 17 17 Efthymiou 16 Efthymiou 16 Gamarnik, Katz 06 Gamarnik, Katz 06 Tetali, Vera, Vigoda, Tetali, Vera, Vigoda, Yang 12 Yang 12 Vardi 17 Vardi 17 (not Markov chain)

2.843 2.843 triangle-free, deterministic triangle-free, deterministic tree tree pathwidth Our results Theorem 1: There is an absolute constant such that as long as , Glauber dynamics mixes in time . Theorem 2: As long as , Glauber dynamics for sampling list colorings also mixes in time . Corollary: The k-state zero temperature antiferromagnetic Potts model on lies in the disordered phase when .

Technical tools Review: coupling A t-step coupling of a Markov chain is a process such that: 1. and are faithful copies of the chain 2. If , then . Take finite state space with metric Lemma: If exists t-step coupling which contracts, i.e. , for all , then chain mixes in time

Review: path coupling Designing a good coupling is often difficult Theorem [Bubley, Dyer 97]: If exists coupling which contracts for all with then chain mixes rapidly. For k-colorings: is Hamming distance Goal: given any two k-colorings differing on exactly one vertex, specify distribution over next step s.t. g tep s e on l in

p u co Review: Given: colorings which differ only on vertex v. Henceforth: say , Use the identity coupling, i.e. same move in both copies of the Markov chain Suppose we attempt to recolor vertex u with c If and not among neighbors of : distance -1 If and : distance +1 Otherwise, distance +0 Expected change:

min #available colors for v {blue/yellow} max #neighbors of v v N(v) Color: Review: Given: colorings which differ only on vertex v. Henceforth: say , Use the identity coupling, i.e. same move in both copies of the Markov chain

Suppose we attempt to recolor vertex u with c If and not among neighbors of : distance -1 If and : distance +1 Otherwise, distance +0 Expected change: min #available colors for v {blue/yellow} max #neighbors of v v N(v) Color:

Review: Given: colorings which differ only on vertex v. Henceforth: say , Use the identity coupling, i.e. same move in both copies of the Markov chain Suppose we attempt to recolor vertex u with c If and not among neighbors of : distance -1 If and : distance +1 Otherwise, distance +0 Expected change: min #available colors for v {blue/yellow} max #neighbors of v

v N(v) Color: Review: Given: colorings which differ only on vertex v. Henceforth: say , Use the identity coupling, i.e. same move in both copies of the Markov chain Suppose we attempt to recolor vertex u with c If and not among neighbors of : distance -1 If and : distance +1

Otherwise, distance +0 Expected change: min #available colors for v {blue/yellow} max #neighbors of v v N(v) Color: Review: Given: colorings which differ only on vertex v.

Henceforth: say , Use the identity coupling, i.e. same move in both copies of the Markov chain Suppose we attempt to recolor vertex u with c If and not among neighbors of : distance -1 If and : distance +1 Otherwise, distance +0 Expected change: min #available colors for v {blue/yellow} max #neighbors of v v

N(v) Color: Review: Given: colorings which differ only on vertex v. Henceforth: say , Use the identity coupling, i.e. same move in both copies of the Markov chain Suppose we attempt to recolor vertex u with c If and not among neighbors of : distance -1 If and : distance +1 Otherwise, distance +0 Expected change:

min #available colors for v {blue/yellow} max #neighbors of v v N(v) Color: Review: Given: colorings which differ only on vertex v. Henceforth: say , Use the identity coupling, i.e. same move in both copies of the Markov chain

Suppose we attempt to recolor vertex u with c If and not among neighbors of : distance -1 If and : distance +1 Otherwise, distance +0 Expected change: min #available colors for v {blue/yellow} max #neighbors of v v N(v) Color:

Review: Given: colorings which differ only on vertex v. Henceforth: say , Use the identity coupling, i.e. same move in both copies of the Markov chain Suppose we attempt to recolor vertex u with c If and not among neighbors of : distance -1 If and : distance +1 Otherwise, distance +0 Expected change: min #available colors for v {blue/yellow} max #neighbors of v

v N(v) Color: Review: Given: colorings which differ only on vertex v. Henceforth: say , Use the identity coupling, i.e. same move in both copies of the Markov chain Suppose we attempt to recolor vertex u with c If and not among neighbors of : distance -1 If and : distance +1

Otherwise, distance +0 Expected change: min #available colors for v {blue/yellow} max #neighbors of v v N(v) Color: Review: Given: colorings which differ only on vertex v.

Henceforth: say , Use the identity coupling, i.e. same move in both copies of the Markov chain Suppose we attempt to recolor vertex u with c If and not among neighbors of : distance -1 If and : distance +1 Otherwise, distance +0 Expected change: min #available colors for v {blue/yellow} max #neighbors of v v

N(v) Color: Review: Given: colorings which differ only on vertex v. Henceforth: say , Use the identity coupling, i.e. same move in both copies of the Markov chain Suppose we attempt to recolor vertex u with c If and not among neighbors of : distance -1 If and : distance +1 Otherwise, distance +0 Expected change:

min #available colors for v {blue/yellow} max #neighbors of v v N(v) Color: Review: [Jerrum 95] Given: colorings which differ only on vertex v. Suppose attempts to recolor vertex u with c If and not in , do the same in :

distance -1 If and , try to recolor u to in : distance +0 If and , try to recolor u to in : distance +1 Otherwise, do the same in , distance doesnt change: distance +0 N(v) Expected change: min #available colors for v v max #neighbors of v

Color: Review: [Jerrum 95] Given: colorings which differ only on vertex v. Suppose attempts to recolor vertex u with c If and not in , do the same in : distance -1 If and , try to recolor u to in : distance +0 If and , try to recolor u to in : distance +1 Otherwise, do the same in , distance doesnt change: distance +0

N(v) Expected change: min #available colors for v v max #neighbors of v Color: Review: [Jerrum 95] Given: colorings which differ only on vertex v. Suppose attempts to recolor vertex u with c If and not in , do the same in :

distance -1 If and , try to recolor u to in : distance +0 If and , try to recolor u to in : distance +1 Otherwise, do the same in , distance doesnt change: distance +0 N(v) Expected change: min #available colors for v v

max #neighbors of v Color: Review: [Jerrum 95] Given: colorings which differ only on vertex v. Suppose attempts to recolor vertex u with c If and not in , do the same in : distance -1 If and , try to recolor u to in : distance +0 If and , try to recolor u to in : distance +1 Otherwise, do the same in , distance doesnt change: distance +0

N(v) Expected change: min #available colors for v v max #neighbors of v Color: Review: [Jerrum 95] Given: colorings which differ only on vertex v.

Suppose attempts to recolor vertex u with c If and not in , do the same in : distance -1 If and , try to recolor u to in : distance +0 If and , try to recolor u to in : distance +1 Otherwise, do the same in , distance doesnt change: distance +0 N(v) Expected change: min #available colors for v

v max #neighbors of v Color: Review: [Jerrum 95] Given: colorings which differ only on vertex v. Suppose attempts to recolor vertex u with c If and not in , do the same in : distance -1 If and , try to recolor u to in : distance +0 If and , try to recolor u to in : distance +1

Otherwise, do the same in , distance doesnt change: distance +0 N(v) Expected change: min #available colors for v v max #neighbors of v Color: Review: [Jerrum 95]

Given: colorings which differ only on vertex v. Suppose attempts to recolor vertex u with c If and not in , do the same in : distance -1 If and , try to recolor u to in : distance +0 If and , try to recolor u to in : distance +1 Otherwise, do the same in , distance doesnt change: distance +0 N(v) Expected change: min #available colors for v

v max #neighbors of v Color: Tight example for Jerrums analysis Each of the d neighbors of v: 1. Is assigned a distinct color 2. May have some yellow or blue neighbors other than v, but not both v

Expected change = #available colors for v #neighbors of v What makes high-girth graphs easier? If G triangle-free, then for a typical , does not have all distinct colors. For any fixing of vertices outside of , conditional distribution on is a product measure. So: (If , ) (Requires extra work/assumptions to get high probability statement about typical colorings encountered in Markov chain)

Vigodas analysis c=blue Kempe components Given coloring , vertex v, and color c, the associated Kempe component is the maximal bichromatic connected component containing v and colored only with and c. Denote the (multi)set of Kempe components by . To flip a Kempe component,

interchange colors and c. v Bigger flips are better v v Bigger flips are better v v

Tradeoff v v Fancier Markov chain SWK dynamics with flip parameters 1. Initialize with arbitrary coloring 2. Repeat for T steps: a. Pick any Kempe component from with probability b. Flip it with probability where | 3. Output final coloring

Fact: If , the stationary distribution is the uniform distribution over k-colorings. Theorem [Vigoda 99]: If , there exist flip parameters for which the SWK dynamics mixes in time . Fancier coupling Given: colorings which differ only on vertex v. Let be the set of distinct colors in . Let be the neighbors of v. Observation: consists of Fancier coupling Given: colorings which differ only on vertex v.

Let be the set of distinct colors in . Let be the neighbors of v. Observation: consists of Fancier coupling Given: colorings which differ only on vertex v. Let be the set of distinct colors in . Let be the neighbors of v. Observation: consists of Fancier coupling Given: colorings which differ only on vertex v. Let be the set of distinct colors in . Let be the neighbors of v. Observation: consists of Fancier coupling Given: colorings which differ only on vertex v.

Let be the set of distinct colors in . Let be the neighbors of v. Observation: consists of Fancier coupling Given: colorings which differ only on vertex v. Let be the set of distinct colors in . Let be the neighbors of v. Observation: consists of Fancier coupling Given: colorings which differ only on vertex v. Let be the set of distinct colors in . Let be the neighbors of v. Observation: consists of Fancier coupling Observation:

Fancier coupling Observation: Fancier coupling Observation: Fancier coupling Fix a color c and let be the neighbors of v colored c Greedily couple flips of and s to flips of and s. 1 2 max

( , ) ( 1 , ( ) ) ( 2 , ( ) ) ( , ( ) )

( , ( ) ) max Contribution to : ( , ) ( 1 , ( ) ) ( 2 , ( ) )

( ( max , ( )) , ( ))

1 where 2 max

some linear function in the flip parameters Fancier coupling If we could find s and so that (*) then if . [Vigoda 99]: Can satisfy (*) using and Our approach Vigodas analysis as an LP Linear Program 1

minimize subject to Q: Is Vigodas solution optimal for this LP? A: Yes! Optimality of 11/6 In fact, optimality of 11/6 can be seen just by looking at the constraints arising from the two extremal configurations: Linear Program 2 minimize subject to Extremal configurations

( , ; , )=(3,2;(2) ,(1) v c=green v Extremal configurations

( , ; , )=(3,2;(2) ,(1) v c=green ( , ) v Extremal configurations ( , ; , )=(3,2;(2) ,(1)

v v c=green ( , ) Extremal configurations ( , ; , )=(3,2;(2) ,(1)

v c=green 1 v 1 (1 , ) Extremal configurations

( , ; , )=(3,2;(2) ,(1) v c=green 1 ( 1 , ) v 1

Extremal configurations ( , ; , )=(7,3;(3,3),(1,1) v c=green v Extremal configurations

( , ; , )=(7,3;(3,3),(1,1) v c=green ( , ) v Extremal configurations

( , ; , )=(7,3;(3,3),(1,1) v v c=green ( , ) Extremal configurations

( , ; , )=(7,3;(3,3),(1,1) v c=green 1 2 v 1

(1 , ) 2 (2 , ) Extremal configurations ( , ; , )=(7,3;(3,3),(1,1) v c=green

1 ( 1 , ) 2 ( 2 , ) v 1 2

Extremal configurations ( , ; , )=(7,3;(3,3),(1,1) v v Extremal configurations

( , ; , )=(7,3;(3,3),(1,1) v v Extremal configurations ( , ; , )=(7,3;(3,3),(1,1) v

v Extremal configurations ( , ; , )=(7,3;(3,3),(1,1) v v

Bottleneck for one-step couplings Theorem: For , there exist no choice of and one-step coupling of the SWK dynamics which contracts simultaneously for both and under the Hamming metric. ( 1 , 1 , 1 ) ( 2 , 2 , 2 )

Variable-length coupling If one-step coupling fails beyond 11/6, lets try t-step coupling. What should t be? Theorem [Hayes, [Bubley,Vigoda Dyer 97]: 07]:IfIfexists existst-step t-stepcoupling coupling, which where t contracts is a random

forstopping all with time, , chainwhich mixes-contracts rapidly. for all with , chain mixes rapidly. Our coupling: take t = first time , i.e. 1. Repeatedly run Vigodas one-step greedy coupling 2. Stop right after distance between two colorings has changed. Brittleness of extremal configurations Brittleness of extremal configurations Brittleness of extremal configurations

Brittleness of extremal configurations Brittleness of extremal configurations Avoiding extremal configurations If you remove the two extremal configuration constraints from Linear Program 1, objective value becomes 161/88=1.8295 Cant hope to never encounter an extremal configuration, but the extremal configurations seem incredibly brittle. In the Nice Scenario, Nice Scenario: Right before the end of the coupling, satisfy wed already beat 11/6. We show the Nice

for some absolute constant Scenario holds in expectation. Avoiding extremal configurations If you remove the two extremal configuration constraints from Linear Program 1, objective value becomes 161/88=1.8295 Cant hope to never encounter an extremal configuration, We will call c-bad if but the extremal configurations seem incredibly brittle. In the Nice Scenario, Nice Scenario: Right before the end of the coupling, satisfy

wed already beat 11/6. We show the Nice for some absolute constant Scenario holds in expectation. Avoiding extremal configurations If you remove the two extremal configuration constraints from Linear Program 1, objective value becomes 161/88=1.8295 Cant hope to never encounter an extremal configuration, but the extremal configurations seem incredibly brittle In the Nice Scenario, Nice Scenario: Right before the end of the coupling, satisfy wed already beat 11/6.

We show the Nice for some absolute constant Scenario holds in expectation. Nice Scenario in expectation Key Lemma: Suppose . Starting from any pair of colorings differing only at v, for some absolute constant , where expectation is over the right before the end of the variable length coupling. Already know Nice Scenario would let us beat 11/6. By linearity of expectation, so does Key Lemma. Proof sketch

Let be the probability c-bad right before the end of the coupling. Let be probability that c-good, i.e. not c-bad and , right before the end of the coupling. By linearity of expectation, enough to show: for some absolute constant . Proof sketch: bad good c-bad v 1

( ) becomes c-good as soon as a is selected and successfully recolored, with total probability Even if thec-good pair of colorings becomes c-good at some point, how 1 2 3 4 do you ensure its more likely to stay

c-good than revert to c-bad? Coupling only terminates when one 1 O ( ) coupling terminates of the components in is chosen, with total probability Provided , but we can add

this for free into the LP Proof sketch: good bad O cgood 1 ( ) c-bad 1

( ) coupling terminates Toy case: suppose . At least ccolored neighbors must be flipped. At most such Kempe components, with total probability Coupling terminates as soon as v is chosen to be recolored with any c not in , with total probability

Recap 1. Reformulated Vigodas analysis as solving an LP. 2. Identified the two extremal configurations that obstruct us from beating 11/6 with any one-step coupling. 3. Modified coupling to only terminate once distance changes. 4. Argued that right before coupling terminates, only a constant fraction of configurations around v are extremal in expectation. An alternative approach Delcourt, Perarnau, Postle 18 independently showed essentially the same result by doing a one-step coupling analysis on a deformation of the Hamming metric. Idea: take Hamming metric minus a bonus term that counts the number of non-extremal configurations around v. Win-win analysis:

1. Few extremal configurations, so Hamming term decreases 2. Many extremal configurations, so bonus term increases Proof very similar to proof of Key Lemma Open questions 1. Can we use this approach + local uniformity results to push on 1.763 or 1.489 for high-girth graphs via SWK dynamics? 2. What other approximate counting problems are amenable to a more aggressive Markov chain and this approach? 3. Deterministic algorithm for ? 4. If , can we show: Thanks!