Spatial mixing of coloring random graphs

DOI10.1007/978-3-662-43948-7_89MaRDI QIDQ5167816zbMATH OpenOpenAlexFDO

Authors Yitong Yin

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

block-wise correlation decaystrong spatial mixing

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the strong spatial mixing (decay of correlation) property of proper $q$-colorings of random graph $G(n,d/n)$ with a fixed $d$. The strong spatial mixing of coloring and related models have been extensively studied on graphs with bounded maximum degree. However, for typical classes of graphs with bounded average degree, such as $G(n,d/n)$, an easy counterexample shows that colorings do not exhibit strong spatial mixing with high probability. Nevertheless, we show that for $$ with $alpha>2$ and sufficiently large $$, with high probability proper $q$-colorings of random graph $G(n,d/n)$ exhibit strong spatial mixing with respect to an arbitrarily fixed vertex. This is the first strong spatial mixing result for colorings of graphs with unbounded maximum degree. Our analysis of strong spatial mixing establishes a block-wise correlation decay instead of the standard point-wise decay, which may be of interest by itself, especially for graphs with unbounded degree.

Recommendations

• Strong spatial mixing of list coloring of graphs
• Sampling random colorings of sparse random graphs
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• scientific article; zbMATH DE number 5279368
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs

Cited in

(3)

• Strong spatial mixing of list coloring of graphs
• Local convergence of random graph colorings
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs

This page was built for publication: Spatial mixing of coloring random graphs

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