Monotonic normalized heat diffusion for distance-regular graphs with classical parameters of diameter 3 3
Shiping Liu, Heng Zhang · 2025
Read Monotonic normalized heat diffusion for distance-regular graphs with classical parameters of diameter 3 3 by Shiping Liu, Heng Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-04314.txt.
Introduction
Shiping Liu and Heng Zhang prove a heat flow trait for a special family of graphs in a 2025 paper. The trait says that a normalized heat spread, watched from a fixed start, behaves in a monotone way. Counterexamples exist: a known Cayley graph breaks the trait. Yet the trait has been proven for several broad graph families, among them graphs with only three distinct eigenvalues.
The family handled here, distance-regular graphs with classical parameters and diameter three, has four distinct eigenvalues. Such graphs need not be symmetric under vertex swaps, nor split into two parts, so past proofs do not reach them. The new proof widens the map of where monotone heat flow can be trusted.
Catalog record
| CREATOR | Shiping Liu, Heng Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-04314
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Monotonic normalized heat diffusion for distance-regular graphs with classical parameters of diameter 3 3 Shiping Liu, Heng Zhang Abstract We prove the monotonic normalized heat diffusion property on distance-regular graphs with classical parameters of diameter 3 3 . Regev and Shinkar found a Cayley graph for which this property fails. On the other hand, this property has been proved on abelian Cayley graphs, graphs with 3 3 distinct eigenvalues and regular bipartite graphs with 4 4 distinct eigenvalues by Price, Nica and Kubo-Namba, respectively. A distance regular graph with classical parameters of diameter 3 3 has 4 4 distinct eigenvalues and is not necessarily bipartite or vertex transitive. 1 Introduction In this paper, we study the heat kernel H:[0,\infty)\times V\times V\to\mathbb{R} on a simple finite connected graph G=(V,E) . For any two vertices u,v\in V and any t\geq 0 , H_{t}(u,v) can be considered as the probability that a continuous-time random walker starting at vertex u , is at vertex v at time t . For any two distinct vertices u,v\in V , we consider the function t\mapsto r_{t}(u,v):=\frac{H_{t}(u,v)}{H_{t}(u,u)}. Clearly, we have r_{0}(u,v)=0,\,\,\text{and}\,\,\lim_{t\to\infty}r_{t}(u,v)=1. (1) It is natural to ask whether the above function is monotonically non-decreasing or not. This question has been considered by Regev and Shinkar [ 15 ] . We will refer to this property as the monotonic normalized heat diffusion property , or the MNHD property for short, following [ 8 , 10 ] . Due to ( 1 ), a necessary condition for the MNHD property is that r_{t}(u,v)\leq 1 holds for any t\geq 0 . However, there do exist graphs for which the function r_{t}(u,v) exceeds 1 for certain vertices u,v at certain time t . This is observed by Regev and Shinkar [ 15 , Proposition A.1] . Regev and Shinkar mentioned that this observation was brought to their attention by Cheeger. They also provided an explicit example which is a 4 -regular graph with 10 vertices [ 15 , Figure 2] . A sufficient condition to ensure that r_{t}(u,v)\leq 1 is a heat homogeneity , that is, the heat kernel has constant diagonal, which means that the value of H_{t}(u,u) is independent of the choice of u (see [ 15 , Section 1] and [ 10 , Section 1] ). In fact, the heat homogeneity holds if and only if the graph is walk-regular [ 10 , Theorem A.1] . Recall that a graph is walk-regular if for every \ell\geq 2 , the number of closed walks of length \ell starting from and ending at every vertex is constant. Typical walk-regular graphs includes vertex-transitive graphs, distance-regular graphs, and regular graphs with at most 4 distinct eigenvalues. Peres asked in 2013 (see [ 15 , Section 1] ) whether the MNHD property holds for all vertex transitive graphs or not. Regev and Shinkar [ 15 ] showed that there exists a Cayley graph for which the MNHD property fails. This provides a negative answer to Peres’ question. On the other hand, Price [ 13 ] proved that the MNHD property does hold for all finite abelian Cayley graphs. Nica [ 10 ] showed that the MNHD property holds for graphs with 3 distinct Laplacian eigenvalues. We stress that the result of Nica does not require the graph to be regular. Kubo and Namba [ 8 ] confirmed the MNHD property for regular bipartite graphs with 4 distinct eigenvalues. It is natural to ask whether the MNHD property holds for all regular graphs with at most 4 distinct eigenvalues . Distance-regular graphs are introduced by Biggs [ 1 ] as a natural extension of distance-transitive graphs. A graph is distance-regular if for any two vertices u,v at distance h , the number of vertices that are at distance i to u and at distance j to v only depends on the three numbers h,i and j . Every distance-regular grpah has diameter D if and only if it has D+1 distinct eigenvalues. For a regular graph G with 4 distinct eigenvalue, van Dam and Haemers [ 5 ] showed that G is distance-regular if and only if the number of vertices at distance 2 from each given vertex satisfies an expression in terms of eigenvalues of G . We identify a class of distance-regular graphs with 4 distinct eigenvalues that are not necessarily bipartite , for which the MNHD property holds true. Our main result states as follows. Theorem 1 . Let G=(V,E) be a distance-regular graph with classical parameters of diameter 3 . Then G has the monotonic normalized heat diffusion (MNHD) property. Most distance-regular graphs related to classical groups and groups of Lie type have classical parameters. Lots of interesting graphs constructed from algebraic structures are either distance-regular graphs with classical parameters (see, e.g., [ 7 ] and [ 3 , Tables 6.1 and 6.2] ) or are closely related to distance-regular graphs with classical parameters (see, e.g., [ 4 ] and [ 6 , Section 3.2] ). We refer to Subsection 2.3 for the precise definition of a distance-regular graph with classical parameters. Although there exist various classification results for distance-regular graphs with classical parameters of large diameter (see, e.g. [ 6 ] ), relatively fewer results are known for the diameter 3 case. We believe that our investigation into the monotonic normalized heat diffusion (MNHD) property sheds new light on the structure of distance-regular graphs with classical parameters. In [ 2 ] , Biggs classified the distance-regular graphs of diameter 3 into three categories: antipodal, bipartite and primitive. We show in Section 5 that the MNHD property holds for all antipodal distance-regular graphs of diameter 3 . Notice that the bipartite case follows from the result of Kubo and Namba [ 8 ] . Relevance of the MNHD property in other areas It is very natural to study whether the MNHD property holds on a given graph. In general, it is highly concerned to understand how certain properties of solutions to differential/difference equations depend on the structure of the underlying graphs. Moreover, the MNHD property is very useful and relevant to other research areas. It is also very interesting to study the MNHD property in the setting of Riemannian geometry. Similarly, the MNHD property does not always hold for Riemannian manifolds [ 13 , Appendix A] . In the other direction, it was shown that the MNHD property holds on all flat tori [ 15 ] and some other Riemannian symmetric spaces including the 3 -dimensional hyperbolic space [ 13 , Section 5 and Appendix B] . It is still open whether the MNHD property holds on all Riemannian symmetric spaces of compact type and on all hyperbolic spaces. In a lattice in \mathbb{R}^{n} , the MNHD property reduces to a monotonicity property of the periodic Gaussian function. An extension of this monotonicity property to the non-spherical Gaussian case [ 16 , Proposition 4.2] can be used to derive a monotonicity property of the normalized heat diffusion on a torus with respect to different flat Riemannian metrics [ 12 , 16 ] . Such an application also leads to a key ingredient in the framework of the so-called numerical cohomology theory [ 11 , 14 ] . 2 Preliminaries In this