Ramanujan graphings and correlation decay in local algorithms1. Issue 3 (1st July 2014)

• Record Type: Journal Article
• Authors: Backhausz, Ágnes; Szegedy, Balázs; Virág, Bálint
• Is Part Of: Random structures & algorithms. Volume 47:Issue 3(2015)
• Page Start: 424
• Page End: 435
• Publication Date: 2014-07-01
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20562
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Let <italic>G</italic> be a <italic>d</italic>‐regular graph of sufficiently large‐girth (depending on parameters <italic>k</italic> and <italic>r</italic>) and <italic>μ</italic> be a random process on the vertices of <italic>G</italic> produced by a randomized local algorithm of radius <italic>r</italic>. We prove the upper bound <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tvrm3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20562:rsa20562-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mn>2</mml:mn><mml:mi>k</mml:mi><mml:mo>/</mml:mo><mml:mi>d</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:msup><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msqrt><mml:mrow><mml:mi>d</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msqrt></mml:mrow></mml:mfrac><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:math></alternatives></inline-formula> for the (absolute value of the) correlation of values on pairs of vertices of distance <italic>k</italic> and show that this bound is optimal. The same results hold automatically for factor of i.i.d processes on the <italic>d</italic>‐regular tree. In that case we give an explicit description for the (closure) of all possible correlation sequences. Our proof is based on the fact that the Bernoulli graphing of the infinite <italic>d</italic>‐regular tree has spectral radius <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tvrr9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20562:rsa20562-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>2</mml:mn><mml:msqrt><mml:mrow><mml:mi>d</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msqrt></mml:mrow></mml:math></alternatives></inline-formula>. Graphings with this spectral gap are infinite analogues of finite Ramanujan graphs and they are interesting on their own right. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 424–435, 2015</p> </abstract>