Cumulant expansion for counting Eulerian orientations

Abstract

An Eulerian orientation is an orientation of the edges of a graph such that every vertex is balanced: its in-degree equals its out-degree. Counting Eulerian orientations corresponds to the crucial partition function in so-called “ice-type models” in statistical physics and is known to be hard for general graphs. For all graphs with good expansion properties and degrees larger than log8⁡n, we derive an asymptotic expansion for this count that approximates it to precision O(n−c) for arbitrarily large c, where n is the number of vertices. The proof relies on a new tail bound for the cumulant expansion of the Laplace transform, which is of independent interest.