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 ideas from ergodic theory, to study the structural discordance of graphs and Markov chains via graph joinings.  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 joinings based on a vertex-label based cost function can detect and identify graph isomorphisms for suitable families of graphs.

Joint work with Yang Xiang, Phuong Hoang, Bongsoo Yi, and Kevin McGoff.