On large‐girth regular graphs and random processes on trees. Issue 3 (27th February 2018)

• Record Type: Journal Article
• Authors: Backhausz, Ágnes; Szegedy, Balázs
• Is Part Of: Random structures & algorithms. Volume 53:Issue 3(2018)
• Page Start: 389
• Page End: 416
• Publication Date: 2018-02-27
• Subjects: factor of i.i.d -- Glauber dynamics -- graphing -- local‐global convergence -- random d‐regular graph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20769
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We study various classes of random processes defined on the regular tree Td that are invariant under the automorphism group of Td . The most important ones are factor of i.i.d. processes (randomized local algorithms), branching Markov chains and a new class that we call typical processes. Using Glauber dynamics on processes we give a sufficient condition for a branching Markov chain to be factor of i.i.d.