Graph Joinings, Graph Isomorphism, and Reversible Markov Chains

Add to your list(s) Download to your calendar using vCal

• Prof Andrew Nobel, UNC Chapel Hill
• Wednesday 04 March 2026, 14:00-15:00
• MR5, CMS Pavilion A.

If you have a question about this talk, please contact Dr Varun Jog.

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 weighted degree of vertex pairs with different labels. For suitable families of labeled graphs, including trees and forests, OGJ can detect and identify isomorphisms between any two 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.

This talk is part of the Information Theory Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Information Theory Seminar
• Interested Talks
• MR5, CMS Pavilion A
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.