Andrew Nobel
Professor of Statistics and Operations Research
University of North Carolina at Chapel Hill
Title: Graph Joinings, Graph Isomorphism, and Reversible Markov Chains
Abstract: Every weighted, undirected graph describes a simple random walk on its vertex set, which is a reversible Markov chain. In this talk I will describe recent work on graph joinings that leverages this elementary connection, in conjunction with ideas from optimal transport, to gain insights into both graph isomorphism and couplings of reversible Markov chains. Informally, a joining of two graphs is a product graph from which the given graphs can be recovered via marginalization. Given two graphs with labeled vertices, the optimal graph joining (OGJ) problem identifies a joining that minimizes the cumulative weighted degree of vertex pairs having different labels. For suitable families of labeled graphs, including trees and forests, OGJ can detect and identify isomorphisms between graphs in the family. In a different direction, I will describe several results showing how graph joinings yield new insights into the rigidity of reversible couplings of reversible Markov chains.
Joint work with Yang Xiang, Phuong Hoang, Bongsoo Yi, and Kevin McGoff.
