Strong spatial mixing of list coloring of graphs. Issue 4 (11th October 2013) - Gamarnik, David; Katz, Dmitriy; Misra, Sidhant
Abstract The property of spatial mixing and strong spatial mixing in spin systems has been of interest because of its implications on uniqueness of Gibbs measures on infinite graphs and efficient approximation of counting problems that are otherwise known to be #P hard. In the context of coloring, strong spatial mixing has been established for Kelly trees in (Ge and Stefankovic, arXiv:1102.2886v3 (2011)) when <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0nv" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />q≥α*Δ+1</alternatives>where q the number of colors, Δ is the degree and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0pc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />α*=1.763</alternatives>.. is the unique solution to <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0kt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />xe−1/x=1</alternatives>. It has also been established in (Goldberg et al., SICOMP 35 (2005) 486–517) for bounded degree lattice graphs whenever <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0mb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />q≥α*Δ−β</alternatives>for some constant β, where Δ is the maximum vertex degree of the graph. We establish strong spatial mixing for a more general problem, namely list coloring, for arbitrary bounded degree triangle‐free graphs. Our results hold for any <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0hs" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />α>α*</alternatives>whenever the size of the list of each vertex v is at least <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0j9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />αΔ(v)+β</alternatives>where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0fr" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Δ(v)</alternatives>is the degree of vertex v and β is a constant that only depends on α. The result is obtained by proving the decay of correlations of marginal probabilities associated with graph nodes measured using a suitably chosen error function. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 599–613, 2015