Graph Joinings, Reversible Markov Chains, and Graph Isomorphism

The correspondence between weighted undirected graphs reversible Markov chains is elementary and well known. I will describe recent work that leverages this correspondence, in conjunction with classical ideas from ergodic theory to study the structural discordance of graphs and Markov chains via graph joining’s. Informally, a joining of two graphs is a graph on the product of their vertex sets giving rise to a coupling of their random walks. Two graphs are strongly disjoint if their only joining is the tensor product and are weakly disjoint if the degree function of every joining is equal to the degree function of the tensor product. I will present spectral characterizations of strong and weak disjointness, and describe corresponding results for reversible Markov chains. In a different direction, I will show how optimal joining’s based on a vertex-label based cost function can detect and identify graph isomorphisms for suitable families of graphs.