Public Lecture: Graph Joinings and Reversible Markov Chains

Thời gian: 14:00 đến 16:00 Ngày 07/01/2026

Địa điểm: Institute for Advanced Study in Mathematics (VIASM), 161 Huynh Thuc Khang Street, Lang Ward, Hanoi.

Speaker: Andrew Nobel, University of North Carolina at Chapel Hill, USA

Abstract

 Every weighted undirected graph describes a simple random walk on its vertex set, which is a reversible Markov chain.  I will describe recent work on graph joinings, which leverages this connection, in conjunction with ideas from optimal transport, to gain insights into both graph isomorphism and couplings of Markov chains.  Informally, a joining of two graphs is a product graph that describes a reversible coupling of their random walks. 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. The OGJ problem can be written as a linear program with a convex polyhedral solution set. I will discuss several conditions on graph families that are sufficient to ensure that for every pair of graphs G and H in the family (i) G and H are isomorphic if and only if their optimal joining cost is zero, and (ii) if G and H are isomorphic, the the extreme points of the solution set of the OGJ problem are deterministic joinings corresponding to the isomorphisms from G to H. In a different direction, I will show how joinings yields new insights into the rigidity of reversible couplings of reversible Markov chains.

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

About speaker 

Andrew Nobel is Paul Ziff Distinguished Professor in the Department of Statistics and Operations Research, and the Department of Biostatistics, at UNC Chapel Hill. After receiving his Ph.D. in Electrical Engineering from Stanford University in 1992, he was a Beckman-Institute Fellow at the University of Illinois Urbana-Champaign from 1992-1995, before joining the Statistics Department at UNC Chapel Hill in 1995.  

Nobel’s research interests include network analysis, statistical genomics, machine learning, and inference from dynamical systems.  His work has appeared in a variety of theoretical and applied journals.  Nobel is a member of the UNC Lineberger Comprehensive Cancer Center, and the UNC Computational Medicine program. He has served on the editorial boards of the IEEE Transactions on Information Theory, the Annals of Statistics, and the Journal of the Royal Statistical Society, Series B. He is the recipient of an NSF CAREER award, and is a Fellow of the IMS. 

Mode of participation: Hybrid (online participation is available only for participants from outside Hanoi area).

Language: English

Registration: Registration is free but compulsory.  

Please register via link: https://forms.gle/m14A1BLrPonXXQgk9 

Deadline of registration: January 06, 2026

Contact

Ms. Nguyễn Hồng Anh, email: nguyenhonganh@viasm.edu.vn