Eulerian Orientations

Abstract

An Eulerian orientation of a graph is an orientation of the edges such that, at each vertex, the number of incoming edges and the number of outgoing edges are equal. This implies that the degree of each vertex is even, which is easily seen to be also a sufficient condition.

This talk concerns the number EO(G) of Eulerian orientations. The quantity eo(G) = (1/n) log EO(G) is known as the residual entropy and can also be defined by a limiting process for infinite graphs with a periodic structure. A famous lower bound on eo(G) was introduced in 1967 by the chemist Linus Pauling in his study of the behaviour of water ice.

We will consider three issues.

1. We will obtain precise estimates of EO(G) for graphs that are sufficiently dense and have sufficient expansion. This reveals an unexpected inverse relationship to the number of spanning trees that so far does not have a heuristic combinatorial explanation.

2. We will show that Pauling’s bound is low by at most a constant and find an estimate for eo(G) in the case of regular graphs of low degree that outperforms previous estimates.

3. We will show that under weak conditions on the number of short cycles Pauling’s estimate is asymptotically precise for regular graphs of increasing degree.

This is joint work with Mikhail Isaev, Tejas Iyer and Rui-Ray Zhang.