On large girth regular graphs and random processes on trees

2014/06/17 by Ágnes Backhausz, Backhausz, Ágnes, Balázs Szegedy +1 · 2 citations
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.1406.4420

33 pages

arxiv created 2015/07/27 · arxiv updated 2015/07/28

Abstract

We study various classes of random processes defined on the regular tree T_d that are invariant under the automorphism group of T_d. 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. Typical processes are defined in a way that they create a correspondence principle between random d-reguar graphs and ergodic theory on T_d. Using this correspondence principle together with entropy inequalities for typical processes we prove a family of combinatorial statements about random d-regular graphs.

Cited by

• Skeletons and Spectra: Bernoulli graphings are relatively Ramanujan
• Boosted second moment method in random regular graphs

Related

• Typicality and entropy of processes on infinite trees
• Local limit of the random degree constrained process
• The degree-restricted random process is far from uniform
• Rapid Mixing on Random Regular Graphs beyond Uniqueness
• Rank-k random graphs and finite type branching processes