Spatial Mixing of Coloring Random Graphs

DOI10.1007/978-3-662-43948-7_89zbMATH Open1412.05079arXiv1402.4556OpenAlexW2962937551MaRDI QIDQ5167816

Yitong Yin

Publication date: 1 July 2014

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

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.

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

zbMATH Keywords

strong spatial mixingblock-wise correlation decay

Mathematics Subject Classification ID

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

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)