About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Random Structures and Algorithms
Paper
Strong spatial mixing of list coloring of graphs
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 q≥α*Δ+1where q the number of colors, Δ is the degree and α*=1.763. is the unique solution to xe-1/x=1. It has also been established in (Goldberg et al., SICOMP 35 (2005) 486-517) for bounded degree lattice graphs whenever q≥α*Δ-β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 α>α*whenever the size of the list of each vertex v is at least αΔ(v)+βwhere Δ(v)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.