An Eulerian orientation of a graph GG directs every edge so that each vertex has equal in-degree and out-degree; the number EO(G)\mathrm{EO}(G) of such orientations is the partition function of an ice-type (six-vertex) model, and the per-vertex logarithm ρ(G)\rho(G) is the residual entropy. Pauling's 1935 heuristic predicts ρ(G)≈ρ^(G)=log⁡(dd/2)−d2log⁡2\rho(G)\approx\widehat{\rho}(G)=\log\binom{d}{d/2}-\frac{d}{2}\log 2 for even degree dd. The open question, stated as Conjecture 1.1 of arXiv:2509.20671 (the regular special case of Conjecture 2.2 of Isaev-McKay-Zhang): is ρ(G)=ρ^(G)+o(1)\rho(G)=\widehat{\rho}(G)+o(1) for every sequence of simple dd-regular graphs with even d→∞d\to\infty? This is known only under auxiliary hypotheses — bounds on short closed trails, eigenvalue concentration, growing girth, and Cartesian-product structure.

Background

In 1935, Pauling estimated the residual entropy of water ice — the entropy that remains at zero temperature because the hydrogen bonds admit many arrangements consistent with the local ice rule. On a graph, the same question is purely combinatorial. An orientation of an undirected graph G=(V,E)G=(V,E) assigns a direction to each edge; the orientation is Eulerian if every vertex has in-degree equal to out-degree, which is possible only when all vertex degrees are even. The number EO(G)\mathrm{EO}(G) of Eulerian orientations is the partition function of the ice-type (six-vertex) model of statistical mechanics placed on GG, and the normalized logarithm ρ(G)=1∣V∣log⁡EO(G)\rho(G)=\frac{1}{|V|}\log\mathrm{EO}(G) (natural logarithm) is called the residual entropy. For a dd-regular graph with even dd, Pauling's independence heuristic — each vertex chooses which d/2d/2 of its dd incident edges point outward, with a global correction factor 2−∣E∣2^{-|E|} for double counting — yields the estimate ρ^=log⁡(dd/2)−d2log⁡2\widehat{\rho}=\log\binom{d}{d/2}-\frac{d}{2}\log 2 per vertex, which at d=4d=4 equals log⁡(3/2)\log(3/2), Pauling's classical value for ice. Lieb's exact solution of square ice on the two-dimensional square lattice gives per-vertex entropy 32log⁡43\frac{3}{2}\log\frac{4}{3}, so at fixed degree the estimate is close but not exact; the open question is whether it becomes exact as the degree grows.

Three regimes are known for general graphs. First, ρ(G)≥ρ^(G)\rho(G)\ge\widehat{\rho}(G) for every graph of even degree (Lieb-Wu; Schrijver). Second, upper bounds are only partial: for connected dd-regular multigraphs of girth gg (the length of a shortest cycle), Las Vergnas proved ρ(G)≤ρ^(G)+log⁡d2g+O(1/n)\rho(G)\le\widehat{\rho}(G)+\frac{\log d}{2g}+O(1/n), and Isaev-McKay-Zhang proved that simple graphs (no loops or parallel edges) of minimum degree dmin⁡→∞d_{\min}\to\infty satisfy ρ(G)≤ρ^(G)+log⁡2+O(log⁡2dmin⁡/dmin⁡)\rho(G)\le\widehat{\rho}(G)+\log 2+O(\log^{2}d_{\min}/d_{\min}), with sharper constants for regular graphs. Third, Isaev-McKay-Zhang conjectured (their Conjecture 2.2) that ρ(G)=ρ^(G)+o(1)\rho(G)=\widehat{\rho}(G)+o(1) for every sequence of simple graphs of even degrees whose harmonic mean degree tends to infinity, and verified it for sufficiently dense expanding graphs, for random graphs with given degrees in two broad ranges, and for cycles of cliques; they also recorded that simplicity is essential — for multigraphs the gap ρ−ρ^\rho-\widehat{\rho} is not uniformly bounded — and that regularity cannot be dropped (a disjoint union of a large clique and triangles has gap tending to 16log⁡2\frac{1}{6}\log 2). A stronger conjectured upper bound of Schrijver from 1983, EO(G)≤∏vRT(dv+1)1/(dv+1)\mathrm{EO}(G)\le\prod_{v}\mathrm{RT}(d_{v}+1)^{1/(d_{v}+1)} where RT(m)\mathrm{RT}(m) is the number of regular tournaments (Eulerian orientations of the complete graph on mm vertices), would imply the regular case with gap O(log⁡d/d)O(\log d/d) but has remained open for over forty years.

The source paper (Hasheminezhad-Isaev-McKay-Zhang) proves the regular case — their Conjecture 1.1 — under four sufficient hypotheses: (i) a bound cℓ(G)≤Ce−(ℓ+1)dℓ−1nc_{\ell}(G)\le C e^{-(\ell+1)}d^{\ell-1}n on the number of closed trails of length ℓ\ell (a closed trail is a closed walk that uses no edge more than once; trails differing only in starting point or direction of traversal are identified), for all 3≤ℓ≤ℓmax⁡3\le\ell\le\ell_{\max} with ℓmax⁡=ω(log⁡d)\ell_{\max}=\omega(\log d); (ii) a spectral condition, namely that at most n d−ω(1)n\,d^{-\omega(1)} adjacency eigenvalues of GG lie outside [−d1−δ,d1−δ][-d^{1-\delta},d^{1-\delta}] for some constant δ>0\delta>0; (iii) girth tending to infinity; and (iv) iterated Cartesian products of regular graphs, including the hypercubes (the 11-skeletons of dd-dimensional cubes). Whether the universal statement holds without such hypotheses is left open.

Problem Statement

Let GG be a finite simple graph (no loops, no parallel edges) with all vertex degrees even. An orientation of GG is Eulerian if every vertex has in-degree equal to out-degree; write EO(G)\mathrm{EO}(G) for the number of Eulerian orientations and ρ(G)=1∣V(G)∣log⁡EO(G)\rho(G)=\frac{1}{|V(G)|}\log\mathrm{EO}(G) (natural logarithm) for the residual entropy. For a dd-regular graph with even dd, Pauling's estimate is ρ^(G)=log⁡(dd/2)−d2log⁡2\widehat{\rho}(G)=\log\binom{d}{d/2}-\frac{d}{2}\log 2 per vertex.

Primary question. For every sequence G=G(n)G=G(n) of simple d(n)d(n)-regular graphs on nn vertices such that d(n)d(n) is even and d(n)→∞d(n)\to\infty, does ρ(G)=ρ^(G)+o(1)\rho(G)=\widehat{\rho}(G)+o(1) hold as n→∞n\to\infty? (This is Conjecture 1.1 of Hasheminezhad-Isaev-McKay-Zhang, arXiv:2509.20671, the regular special case of Conjecture 2.2 of Isaev-McKay-Zhang, doi:10.4171/aihpd/207.) By the known universal bounds, the gap satisfies 0≤ρ(G)−ρ^(G)≤log⁡2+o(1)0\le\rho(G)-\widehat{\rho}(G)\le\log 2+o(1) along every such sequence, so the question is whether the gap must tend to zero. A resolution is either a proof of the universal statement, or a counterexample: an explicit sequence of simple d(n)d(n)-regular graphs with even d(n)→∞d(n)\to\infty and a constant ε>0\varepsilon>0 such that ρ(G)−ρ^(G)≥ε\rho(G)-\widehat{\rho}(G)\ge\varepsilon for all large nn.

References

  1. M. Hasheminezhad, M. Isaev, B. D. McKay, R.-R. Zhang, 'On Pauling's residual entropy estimate for regular graphs with growing degree', arXiv:2509.20671 (2025), https://arxiv.org/abs/2509.20671
  2. M. Isaev, B. D. McKay, R.-R. Zhang, 'Correlation between residual entropy and spanning tree entropy of ice-type models on graphs', Ann. Inst. Henri Poincare D (2025), doi:10.4171/aihpd/207, https://doi.org/10.4171/aihpd/207 (preprint arXiv:2409.04989, https://arxiv.org/abs/2409.04989)
  3. L. Pauling, 'The Structure and Entropy of Ice and of Other Crystals with Some Randomness of Atomic Arrangement', J. Am. Chem. Soc. 57 (1935) 2680-2684, doi:10.1021/ja01315a102, https://doi.org/10.1021/ja01315a102
  4. E. H. Lieb, 'Residual Entropy of Square Ice', Phys. Rev. 162 (1967) 162-172, doi:10.1103/PhysRev.162.162, https://doi.org/10.1103/PhysRev.162.162
  5. A. Schrijver, 'Bounds on the number of Eulerian orientations', Combinatorica 3 (1983) 375-380, doi:10.1007/BF02579193, https://doi.org/10.1007/BF02579193
  6. M. Las Vergnas, 'An upper bound for the number of Eulerian orientations of a regular graph', Combinatorica 10 (1990) 61-65, doi:10.1007/BF02122696, https://doi.org/10.1007/BF02122696
  7. M. Isaev, B. D. McKay, R.-R. Zhang, 'Cumulant expansion for counting Eulerian orientations', J. Combin. Theory Ser. B 172 (2025) 263-314, doi:10.1016/j.jctb.2025.01.002, https://doi.org/10.1016/j.jctb.2025.01.002
  8. F. Bencs, M. Borbenyi, P. Csikvari, 'Number of Eulerian orientations for Benjamini-Schramm convergent graph sequences', arXiv:2409.18012 (2024), https://arxiv.org/abs/2409.18012