Typicality and entropy of processes on infinite trees

Abstract: When we study random $d$-regular graphs from the point of view of graph limit theory, the notion of typical processes arise naturally. These are certain invariant families of random variables indexed by the infinite regular tree. Since this tree is the local limit of random $d$-regular graphs when $d$ is fixed and the number of vertices tends to infinity, we can consider the processes that can be approximated with colorings (labelings) of random $d$-regular graphs. These are the so-called typical processes, whose properties contain useful information about the structure of finite random regular graphs. In earlier works, various necessary conditions have been given for a process to be typical, by using correlation decay or entropy inequalities. In the work presented in the talk, we go in the other direction and provide sufficient entropy conditions in the special case of edge Markov processes. This condition can be extended to unimodular Galton--Watson random trees as well. Joint work with Charles Bordenave and Balázs Szegedy (https://arxiv.org/abs/2102.02653).

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.