Entropy (Sep 2023)

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

  • Alexey V. Gulyaev,
  • Mikhail V. Tamm

DOI
https://doi.org/10.3390/e25091318
Journal volume & issue
Vol. 25, no. 9
p. 1318

Abstract

Read online

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 N instead of logp−1N 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.

Keywords