Spring 2019

Counting Colorings Deterministically Using Spatial Mixing and Complex Zeros

Tuesday, September 8th, 2020 9:00 am9:50 am

Add to Calendar


Piyush Srivastava (Tata Institute of Fundamental Research)

We explore connections between the phenomenon of correlation decay and the location of Lee-Yang and Fisher zeros for various spin systems. In particular, we show that results on strong spatial mixing in the anti-ferromagnetic Potts model can be lifted to the complex plane to give new zero-freeness results for the associated partition function. This extension allows us to give the first deterministic FPTAS for counting the number of q-colorings of a graph of maximum degree Δ provided only that q≥2Δ. This matches the natural bound for randomized algorithms obtained by a straightforward application of Markov chain Monte Carlo. We also give an improved version of this result for triangle-free graphs. We also note that for the special case of trees of maximum degree Δ, the same method extends up to the threshold for weak spatial mixing for proper colorings, but falls short of the strongest possible zero-freeness result that can be obtained for this special case.

This framework also allows us to give unified proofs of several recent results of this kind, including the resolution by Peters and Regts of the Sokal conjecture for the partition function of the hard core lattice gas. It also allows us to prove new results on the location of Lee-Yang zeros of the anti-ferromagnetic Ising model.

Joint work with Jingcheng Liu (Caltech) and Alistair Sinclair (UC Berkeley). Available at arXiv:1906:01228.