On large‐girth regular graphs and random processes on trees. Issue 3 (27th February 2018) - Backhausz, Ágnes; Szegedy, Balázs
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.