Two arrows in and two out

A walk that splices in its own detours proved the condition Euler found for the bridges of Königsberg: a connected graph has a closed walk using every edge exactly once if and only if every point has even degree. It ended with a question about counting. Finding one circuit is easy; counting all of them is, for undirected graphs, as hard as counting gets, while for directed graphs a formula exists. This essay is about the object that sits between the two, and turns out to be interesting in its own right.

Walk an Eulerian circuit and give every edge an arrow in the direction it is walked. Each time the walk passes through a point it arrives along one edge and leaves along another, so every point ends with exactly as many arrows in as out. An assignment of arrows with that balance is an Eulerian orientation. Every circuit makes one, many circuits make the same one, and an orientation can be counted without any circuit at all. On the square grid, where every point has four edges, the balance means two arrows in and two out — and that is a rule chemists had already written down for ice.

Ice #

In ice, every oxygen atom has four hydrogen atoms around it on the bonds to its neighbours, and Linus Pauling proposed in 1935 that two of the four sit close to it and two close to the neighbouring oxygens — two “in” and two “out” — so that each water molecule keeps its identity. The rule fixes the local arrangement and leaves a great deal free: there are very many ways to satisfy it across a crystal, and even at absolute zero ice keeps that freedom, a residual entropy that calorimetry measures. On the square grid, a flattened model of the crystal, the hydrogen arrangements are exactly the Eulerian orientations: put an arrow on each bond pointing towards the oxygen its hydrogen is near, and the ice rule is two in, two out.

Pauling estimated the count with an argument that is worth seeing because it is nearly right. Each edge has 2 possible directions, and the grid has twice as many edges as points, so there are $4^N$ orientations of an $N$-point grid. At each point, 6 of the 16 ways of orienting its four edges are balanced. If the points’ constraints were independent, the count would be $4^N \times (6/16)^N = 1.5^N$, and 1.5 per point gave a residual entropy within a few per cent of the measured value for real ice.

Why the points are not independent #

Pauling’s estimate is wrong for a reason that can be seen on the smallest possible grid. Each point’s six balanced patterns are counted as if any of them could sit next to any other, but neighbouring points share an edge, and around every little square of the grid four points share four edges in a ring. Whether the four edges of a square point consistently round it — all clockwise, all anticlockwise — or in some mixed pattern is decided jointly by four points, and the independent estimate weights those joint patterns wrongly. The correction is a sum over all such loops, of every size, and it is what lifts 1.5 to 1.5396.

The widths in the transfer figure show the effect from the other side. A cylinder two points round is the extreme case of correlation: every ring of horizontal edges is a loop of length two, the constraints are as tightly linked as they can be, and the count per point is $\sqrt 3 = 1.732$, far above both values. As the circumference grows the loops that wrap round the cylinder become long and rare, the local loops take over, and the count settles. That the settled value turns out to be a clean algebraic number, rather than something that can only be computed, is the content of Lieb’s theorem, and it is not visible in any finite width.

The same independent-points reasoning is the first step in the statistical physics of almost every lattice model, under the name of the mean-field or Bethe approximation, and ice is one of the few cases in which it can be compared with an exact answer. It undercounts here by 2.6%; on a tree, where there are no loops at all, it would be exact. The loops are the whole of the error, which is the theme of the streets a postman walks twice and every edge on exactly two cycles seen from a different direction: in each case it is the cycles of the graph that make a local rule globally hard.

Heights and three colours #

The pictures are drawn from a different description that makes the ice rule automatic. Write a whole number in every face of the grid, and require the numbers in neighbouring faces to differ by exactly one. Then orient each edge so that, walking along it, the higher face is on the left. Around each point the four faces must go up and down by one in some order and return to where they started, so there are two steps up and two steps down — and two steps each way is two arrows in and two out. The construction runs backwards too: from any Eulerian orientation of the grid the heights can be recovered, up to a constant, by walking from face to face.

That turns ice into a height function, a random surface over the grid, and the figures make random ice by making random surfaces: starting from a checkerboard of 0s and 1s, a face whose four neighbours all hold the same value is moved from one side of it to the other, over and over. Reduced modulo 3 the heights give something else again: a colouring of the faces with three colours in which no two neighbours match, since neighbouring heights differ by one. Every proper three-colouring of the faces comes from heights this way. So Eulerian orientations of the square grid are the same as three-colourings of its faces, which ties the count to the chromatic polynomial of the grid’s dual and explains why Lieb’s paper is cited by people who never think about ice.

Counting ring by ring #

To count ice exactly on a large grid, wrap it into a cylinder $L$ points round and build it up one ring at a time. The state between two rings is the set of directions of the $L$ vertical edges crossing between them — $2^L$ possibilities — and the transfer matrix records, for each pair of states below and above a ring, how many ways there are to orient that ring’s horizontal edges so that every point on it is balanced. The number of orientations of a cylinder $M$ rings long is then a sum over products of $M$ entries of the matrix, and as $M$ grows it is dominated by the matrix’s largest eigenvalue $\lambda_L$. Per point, the count is $\lambda_L^{1/L}$.

The figure computes it for widths 2 to 9. Even and odd widths approach from two sides — narrow cylinders impose extra structure that depends on the parity of the circumference — and both close in on the line Elliott Lieb found in 1967:

$$W = \left(\frac43\right)^{3/2} = 1.5396\ldots$$

At width 9 the count is 1.5446, within 0.005 of it. Lieb’s derivation solved the same transfer matrix for every width at once, by noticing that its eigenvectors can be written down in a form Hans Bethe had invented for magnets in 1931; the answer came out as an algebraic number, which was the surprise. Pauling’s 1.5 is 2.6% below it. Real ice, three-dimensional, has its own value, about 1.507, computed by John Nagle in 1966 by series methods; no exact formula is known for it.

Pauling’s guess is always a floor #

Pauling’s argument works for any graph with even degrees. A point of degree $d$ has $\binom{d}{d/2}$ balanced orientations of its $2^d$, every edge is shared by two points, and treating the points as independent gives

$$\prod_{v} \frac{\binom{d_v}{d_v/2}}{2^{d_v/2}}$$

orientations. Alexander Schrijver proved in 1983 that this is always a lower bound: no graph with even degrees has fewer Eulerian orientations than Pauling’s estimate. Michel Las Vergnas gave a matching upper bound, $\prod_v \binom{d_v}{d_v/2}^{1/2}$. The figure tests both on complete graphs, where every point has even degree when the number of points is odd and an Eulerian orientation is a regular tournament — every team in a round robin winning exactly half its games.

The counts, by enumeration, are 2, 24, 2,640 and 3,230,080 for 3, 5, 7 and 9 points, and each lies between the bounds: 2,640 between 610 and 35,777, 3,230,080 between 587,222 and 200,882,072. On the square grid Schrijver’s bound is exactly Pauling’s 1.5 per point and the truth is 1.5396 — so the bound is close for ice and further off for dense graphs, where the constraints at neighbouring points overlap more.

A regular tournament is also a schedule. A round robin among an odd number of teams in which every team wins exactly half its games is a balanced season, and the counts say how many ways there are to have one: 24 for five teams, 2,640 for seven, 3,230,080 for nine. Each is an Eulerian orientation of the complete graph, and Schrijver’s bound says that a balanced season can always be found in at least Pauling’s proportion of all possible seasons — a statement about schedules proved by thinking about ice.

From orientations to circuits #

Counting orientations is the first half of counting circuits. For a directed graph with every point balanced, the BEST theorem — named for Nicolaas de Bruijn, Tatyana van Aardenne-Ehrenfest, Cedric Smith and William Tutte — gives the number of Eulerian circuits exactly: the number of spanning trees with every edge pointing towards one chosen point — a directed version of the trees Cayley counted, which a determinant counts — times $(d^+_v - 1)!$ for every point $v$. It is the formula that counted de Bruijn sequences. An undirected circuit with a direction chosen is a directed circuit of exactly one orientation, so the circuits of an undirected graph can be counted by summing the BEST formula over its Eulerian orientations.

For the complete graph on five points the 24 orientations carry 264 directed circuits between them, and walking every circuit from one point confirms it: 528 walks, each circuit seen twice because it passes the starting point twice. Up to direction there are 132. For seven points the 2,640 orientations carry 129,976,320 directed circuits. The method’s weakness is visible: it needs every orientation, and the number of orientations grows exponentially. Graham Brightwell and Peter Winkler proved in 2005 that counting Eulerian circuits of undirected graphs is #P-complete, and the orientations are where the hardness lives — the BEST theorem disposes of everything after them in polynomial time.

Fixed walls, and the sign matrices #

The boundary of a patch of ice can be fixed instead of wrapped. Take an $n \times n$ grid of points and fix the arrows on its outer edges: pointing in along the left and right sides, pointing out along the top and bottom. This domain-wall boundary leaves the inside free, subject to two in, two out at every point, and the figure counts the possibilities by direct enumeration: 1, 2, 7, 42, 429, 7,436 and 218,348 for $n = 1$ to 7.

Those are the numbers of alternating-sign matrices: square matrices of 0s, 1s and −1s in which every row and column sums to 1 and the non-zero entries in each row and column alternate in sign. The correspondence is direct. At a point whose two horizontal arrows both point towards it, write $+1$; where both point away, $-1$; elsewhere 0. The figure shows a square of order 4 whose matrix has a $-1$ in its third row, and checks that the 42 squares of order 4 give 42 different matrices. William Mills, David Robbins and Howard Rumsey found the numbers in 1982 and conjectured that they are

$$\prod_{k=0}^{n-1} \frac{(3k+1)!}{(n+k)!},$$

and the conjecture was proved by Doron Zeilberger in 1996, in a paper checked by eighty-eight referees, and then by Greg Kuperberg the same year with a short proof that used exactly this correspondence: count the domain-wall squares of ice with Izergin’s determinant formula from physics, and the product falls out. The same numbers count totally symmetric self-complementary plane partitions and descending plane partitions, and no bijection between those families and the alternating-sign matrices is known.

Six patterns at a point #

The balanced orientations at a single point of the square grid are six, and physicists label them: two in which the horizontal arrows pass straight through and the vertical arrows pass straight through, two in which they pass straight through in opposite senses, and two in which both horizontal arrows point in and both vertical arrows point out, or the reverse. Giving the six patterns different weights — energies, in the physical reading — produces the six-vertex model, of which ice is the case with all weights equal. Other choices model ferroelectric crystals such as potassium dihydrogen phosphate, in which one pair of patterns is favoured, and the model’s phase changes as the weights vary were among the first exactly solved phase transitions after Onsager’s.

The last two patterns are the ones the matrix in the domain-wall figure records: the point where both horizontal arrows point in is a $+1$, where both point out a $-1$, and the four straight-through patterns are 0s. The domain-wall boundary forces each row to have one more $+1$ than $-1$, which is the alternating-sign condition. Kuperberg’s proof weighted the six patterns with variables, evaluated Izergin’s determinant at a special value of the weights where it can be computed in closed form, and read off the product formula. The plane partitions that share the counts are symmetric relatives of the partitions piled into a corner, stacks of cubes with every symmetry of the cube imposed at once, and why they should match a model of ice is the open question below.

What the figures show and assume #

The ice patches are samples, not counts: a random surface built by local moves, guaranteed to satisfy the ice rule — every inner point is checked — but not guaranteed to be uniformly random among all patches, since the moves start from a checkerboard and run for a fixed number of sweeps. The transfer-matrix values are exact up to the convergence of a power iteration, and they are counts on cylinders, which differ from counts on flat patches by boundary effects that vanish per point as the patch grows. The complete-graph counts are exhaustive, the circuit counts are exact integer arithmetic checked for five points by direct enumeration, and the domain-wall counts are a direct enumeration of every arrow pattern, compared with the product formula.

What the computations do not touch is the reason. Lieb’s $(4/3)^{3/2}$ comes from the Bethe ansatz, which no computation on narrow cylinders explains; the cylinders only approach it.

Still open: ice in three dimensions, and the bijections #

No exact value is known for the residual entropy of three-dimensional ice, nor for the Eulerian orientations of the cubic lattice or most other lattices: the square grid is solvable because its transfer matrix has a hidden structure that ordinary three-dimensional lattices lack. The best values come from series expansions and Monte Carlo methods, and they agree with calorimetry to the precision of the measurements.

On the combinatorial side, the alternating-sign matrices, the descending plane partitions and the totally symmetric self-complementary plane partitions are all counted by the same product, and no bijection between the alternating-sign matrices and either kind of plane partition is known, though they have been sought since the 1980s; the proofs that the counts agree all go through algebraic identities, and the question of why three such different families should be the same size is still without a combinatorial answer.

A rule from chemistry, counted #

An Eulerian circuit leaves an Eulerian orientation behind, and counting the orientations rather than the circuits turns graph theory into the physics of ice: two arrows in and two out at every point of the square grid, (4/3)^(3/2) = 1.5396 arrangements per point, against Pauling’s independent-points estimate of 1.5, which Schrijver proved is a lower bound for every graph. Heights on the faces make the rule automatic and turn the orientations into three-colourings; the BEST theorem turns them into circuits, 264 for five points and 129,976,320 for seven; and with the walls fixed, the arrows in a square of ice are the alternating-sign matrices, counted by a product that took fourteen years to prove.