Equitable Partitions and Random Walks

Resumen

A random walk on a graph is a stochastic process in which a “walker” moves between vertices, selecting the next vertex uniformly at random from its neighbors. This concept has significant applications in physics, particularly in the analysis of spring and resistor networks [5]. For a random walk on a finitary graph, the probability that a walker at vertex v transitions to vertex u is defined to be proportional to the weight of the edge e_uv. This leads to the definition of the transition matrix W := MD^-1, (1) where D is the diagonal matrix of vertex degrees. The matrix W is stochastic, meaning that W1 = 1, and it governs the probability distribution after t steps, given by W^tu, where u is the initial probability distribution. If the graph is unweighted, undirected, and simple, the associated matrix W is similar to the normalized Laplacian, a matrix that encodes many important spectral properties of the graph and is widely studied [2]. In graphs exhibiting regularities—often arising from symmetries, but not restricted to them—we can partition the vertex set into cells such that the probability of transitioning from v to u in t steps depends only on the cells containing v and u. When this occurs, the partition is an equitable partition of M. The study of equitable partitions appears in various graph-theoretical contexts. Notably, it arises in two polynomial-time algorithms that provide necessary conditions for the graph isomorphism problem. The Weisfeiler–Leman algorithm [6] and fractional isomorphism [4] both involve relaxations of graph isomorphism and determine whether two graphs share a common equitable partition. We can introduce three types of quotients based on equitable partitions. In our previous work [1], we studied and extended conditions under which two graphs can have a common quotient of one of these types. Another important concept is that of a pseudo-equitable partition, a generalization of equitable partitions that is particularly useful in the study of quantum walks. In particular, it serves as a tool for constructing graphs with Perfect State Transfer (PST) [3]. In [1], we provided new characterizations of pseudo-equitable partitions and established conditions under which two graphs can share a common quotient. Pseudo-equitable partitions also arise naturally in the context of random walks, where edge weights can be interpreted as an initial probability distribution. All the theorems mentioned above apply equally well to the study of random walks. [...]