Counting degree-constrained orientations

Abstract

We study the enumeration of graph orientations under local degree constraints. Given a finite graph $G=(V,E)$ and a family of admissible sets $\{{\mathsf{P}}_v\subseteq \mathbb{Z}:v\in V\}$, let $\mathcal{N}(G;{\prod }_{v\in V}{\mathsf{P}}_v)$ denote the number of orientations in which the out-degree of each vertex $v$ lies in $P_v$. We prove a general duality formula expressing $\mathcal{N}(G;{\prod }_{v\in V}{\mathsf{P}}_v)$ as a signed sum over edge subsets, involving products of coefficient sums associated with $\{{\mathsf{P}}_v{\}}_{v\in V}$, from a family of polynomials. Our approach employs gauge transformations, a technique rooted in statistical physics and holographic algorithms. We also present a probabilistic derivation of the same identity, interpreting the orientation-generating polynomial as the expectation of a random polynomial product. As applications, we obtain explicit formulas for the number of even orientations and for mixed Eulerian-even orientations on general graphs. Our formula generalizes a result of Borbényi and Csikvári on Eulerian orientations of graphs.

9 pages. Fixed minor typos