Strong spatial mixing of list coloring of graphs

DOI10.1002/RSA.20518MaRDI QIDQ5265338zbMATH OpenOpenAlexFDO

Authors

Publication date 23 July 2015

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.1223

zbMATH Keywords

correlation decaygraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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 regular trees when $qgeqalph{a}^{\ast }Delta+1$ where $q$ the number of colors, $Delta$ is the degree and $alph{a}^{\ast }=\mathrm{1.763..}$ is the unique solution to $x{e}^{-1/x}=1$. It has also been established for bounded degree lattice graphs whenever $$ for some constant $$, where $Delta$ is the maximum vertex degree of the graph. The latter uses a technique based on recursively constructed coupling of Markov chains whereas the former is based on establishing decay of correlations on the tree. We establish strong spatial mixing of list colorings on arbitrary bounded degree triangle-free graphs whenever the size of the list of each vertex $v$ is at least $$ where $Delta(v)$ is the degree of vertex $v$ and $alpha>alph{a}^{\ast }$ and $$ is a constant that only depends on $alpha$. We do this by proving the decay of correlations via recursive contraction of the distance between the marginals measured with respect to a suitably chosen error function.

Recommendations

• Spatial mixing of coloring random graphs
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
• scientific article; zbMATH DE number 5279368
• Correlation decay up to uniqueness in spin systems

Cites work

• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Counting independent sets up to the tree threshold
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Improved bounds for sampling colorings
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• Uniqueness of uniform random colorings of regular trees

Cited in

(17)

• Counting hypergraph matchings up to uniqueness threshold
• Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees
• The topological strong spatial mixing property and new conditions for pressure approximation
• Mixing properties of colourings of the ℤ^d lattice
• Spatial mixing of coloring random graphs
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• scientific article; zbMATH DE number 7650115 (Why is no real title available?)
• Perfect sampling from spatial mixing
• Correlation decay and the absence of zeros property of partition functions
• Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite -regular tree for large
• Deterministic approximate counting of colorings with fewer than 2 colors via absence of zeros
• Correlation decay and partition function zeros: algorithms and phase transitions
• Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees
• Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
• Decay of correlation for edge colorings when \(q>3\Delta\)
• Rapid mixing via coupling independence for spin systems with unbounded degree
• Finitary codings for spatial mixing Markov random fields

This page was built for publication: Strong spatial mixing of list coloring of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5265338)