Heat across an edge of an arc-transitive graph
Aldous and Fill ask whether random walk on an arc-transitive graph has some monotonicity property stronger than the inequality $P_i(X_{2t}=j)\le P_i(X_{2t}=i)$ that holds for every symmetric chain (Open Problem 7.30 of their monograph). We show that on every finite connected $1$-walk-regular graph, and so on every finite connected arc-transitive graph and every distance-regular graph, the ratio $H_t(x,y)/H_t(x,x)$ of the continuous-time heat kernel is strictly increasing in $t$ for every edge $xy$. Its derivative is the variance of the Laplacian eigenvalue under the exponentially tilted spectral measure of $x$, and its distance from $1$ is pinned between the spectral gap and the largest eigenvalue times $1-1/(nH_t(x,x))$. The same holds for the lazy walk in discrete time. The hypothesis cannot be weakened to regularity: on the $4$-regular graph of Regev and Shinkar the ratio across an edge exceeds $1$ and then decreases, although on every regular graph its average over the neighbours of $x$ is increasing.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-08
- DOI
- https://doi.org/10.5281/zenodo.24069898
- Primary Topic
- Stochastic processes and statistical mechanics
- Type
- preprint