Probability and Mathematical Physics Seminar

---

Residual entropy and spanning tree entropy of ice-type models on graphs

Speaker: Mikhail Isaev, UNSW Sydney

Location: Warren Weaver Hall 1302

Date: Friday, May 2, 2025, 11:10 a.m.

Notes:

The probability that every vertex in a random orientation of the edges of a given graph has the same in-degree and out-degree is equivalent to counting Eulerian orientations, a problem that is known to be #P-hard in general. This count also appears under the name residual entropy in physical applications, most famously in the study of the behaviour of ice. Using a new tail bound for the cumulant expansion series, we derive an asymptotic formula for graphs of sufficient density. The formula contains the inverse square root of the number of spanning trees, for which we do not have a heuristic explanation. We will also show a strong experimental correlation between the number of spanning trees and the number of Eulerian orientations even for graphs of bounded degree. This leads us to propose a new heuristic for the number of Eulerian orientations which performs much better than previous heuristics for graphs of chemical interest. The talk is based on two recent papers arXiv:2309.15473 and arXiv:2409.04989 joint with B.D. McKay and R.-R. Zhang.