Path Counting on Tree-like Graphs with a Single Entropic Trap: Critical Behavior and Finite Size Effects

Abstract

It is known that maximal entropy random walks and partition functions that count long paths on graphs tend to become localized near nodes with a high degree. Here, we revisit the simplest toy model of such a localization: a regular tree of degree $p$ with one special node ("root") that has a degree different from all the others. We present an in-depth study of the path-counting problem precisely at the localization transition. We study paths that start from the root in both infinite trees and finite, locally tree-like regular random graphs (RRGs). For the infinite tree, we prove that the probability distribution function of the endpoints of the path is a step function. The position of the step moves away from the root at a constant velocity $v=(p-2)/p$. We find the width and asymptotic shape of the distribution in the vicinity of the shock. For a finite RRG, we show that a critical slowdown takes place, and the trajectory length needed to reach the equilibrium distribution is on the order of $\sqrt{N}$ instead of ${\log }_{p-1}N$ away from the transition. We calculate the exact values of the equilibrium distribution and relaxation length, as well as the shapes of slowly relaxing modes.

arXiv comment15 pager, 8 figures

References in corpus (15)

• Anderson Transitions
• Random walks and diffusion on networks
• Localization of maximal entropy random walk
• From Anderson localization on Random Regular Graphs to Many-Body localization
• Statistics of eigenstates near the localization transition on random regular graphs
• Critical behavior at the localization transition on random regular graphs
• Localization Transition of Biased Random Walks on Random Networks
• Random walk on Bethe lattice and hyperbolic geometry
• Comment on "Localization Transition of Biased Random Walks on Random Networks"
• Exact Solution for Statics and Dynamics of Maximal Entropy Random Walk on Cayley Trees
• Paths counting on simple graphs: from escape to localization
• On statistical models on super trees
• From generalized directed animals to the asymmetric simple exclusion process
• Peculiar spectral statistics of ensembles of trees and star-like graphs
• From steady-state TASEP model with open boundaries to 1D Ising model at negative fugacity