Strong spatial mixing of list coloring of graphs. Issue 4 (11th October 2013)

• Record Type: Journal Article
• Authors: Gamarnik, David; Katz, Dmitriy; Misra, Sidhant
• Is Part Of: Random structures & algorithms. Volume 46:Issue 4(2015)
• Page Start: 599
• Page End: 613
• Publication Date: 2013-10-11
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20518
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>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 #<italic>P</italic> hard. In the context of coloring, strong spatial mixing has been established for Kelly trees in (Ge and Stefankovic, arXiv:1102.2886v3 (2011)) when <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0nv" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20518:rsa20518-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>q</mml:mi><mml:mo>≥</mml:mo><mml:msup><mml:mo>α</mml:mo><mml:mo>*</mml:mo></mml:msup><mml:mo>Δ</mml:mo><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>where <italic>q</italic> the number of colors, Δ is the degree and <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0pc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20518:rsa20518-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mo>α</mml:mo><mml:mo>*</mml:mo></mml:msup><mml:mo>=</mml:mo><mml:mn>1.763</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>.. is the unique solution to <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0kt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20518:rsa20518-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>x</mml:mi><mml:msup><mml:mi>e</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>x</mml:mi></mml:mrow></mml:msup><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>. It has also been established in (Goldberg et al., SICOMP 35 (2005) 486–517) for bounded degree lattice graphs whenever <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0mb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20518:rsa20518-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>q</mml:mi><mml:mo>≥</mml:mo><mml:msup><mml:mo>α</mml:mo><mml:mo>*</mml:mo></mml:msup><mml:mo>Δ</mml:mo><mml:mo>−</mml:mo><mml:mo>β</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>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 <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0hs" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20518:rsa20518-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>α</mml:mo><mml:mo>></mml:mo><mml:msup><mml:mo>α</mml:mo><mml:mo>*</mml:mo></mml:msup></mml:mrow></mml:math></alternatives></inline-formula>whenever the size of the list of each vertex <italic>v</italic> is at least <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0j9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20518:rsa20518-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>α</mml:mo><mml:mo>Δ</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>v</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mo>β</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>where <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7m0fr" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20518:rsa20518-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Δ</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>v</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>is the degree of vertex <italic>v</italic> 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</p> </abstract>