Top Qs
Timeline
Chat
Perspective
Lieb's square ice constant
Mathematical constant used in combinatorics From Wikipedia, the free encyclopedia
Remove ads
Lieb's square ice constant is a mathematical constant used in the field of combinatorics to approximately count Eulerian orientations of grid graphs. It was introduced by Elliott H. Lieb in 1967.[1] It is called the square ice constant because the orientations that it counts arise in statistical mechanics of crystalline structures as the states of an ice-type model on a square grid.
Remove ads

The value of Lieb's square ice constant is Based on this, the number of Eulerian orientations of an grid is where the term, an instance of little o notation, hides parts of the formula that tend to zero in the limit as grows.
Remove ads
Definition
An grid graph has vertices. When constructed with periodic boundary conditions (with edges that wrap around from left to right and from top to bottom) it has edges and is 4-regular, meaning that each vertex has exactly four neighbors. An orientation of this graph is an assignment of a direction to each edge. It is an Eulerian orientation if it gives each vertex exactly two incoming edges and exactly two outgoing edges. An Eulerian orientation can be constructed by orienting each row of the grid (including the wraparound edge) as a cycle, and each column as another cycle, but there are many more orientations that are not of this special form.
Denote the number of Eulerian orientations of this graph by . Then this number is approximately exponential in , with Lieb's square ice constant as the base of the exponential. More precisely, is Lieb's square ice constant.[2] Lieb used a transfer-matrix method to compute this exactly.[1]
Remove ads
Exact enumeration
The exact numbers of Eulerian orientations of an grid graph, with periodic boundary conditions, for , are[3]
4, 18, 148, 2970, 143224, 16448400, 4484823396, 2901094068042, 4448410550095612, 16178049740086515288, ...
Remove ads
Applications
Summarize
Perspective
Lieb's original motivation for studying this counting problem comes from statistical mechanics. In this area, the ice-type models are used to model hydrogen bonds in crystalline structures such as water ice where each element of the structure (such as a water molecule) has bonds connecting it to four neighbors, with two bonds of each polarity. A state of this system describes the polarity of the hydrogen bond for each of the four neighbors. If the elements and their adjacencies are described by the vertices and edges of an undirected graph, the polarities of their bonds can be described by orienting this graph, with two edges of each direction at each vertex. With an additional assumption that all consistent choices of orientation have equal energy, the number of possible states equals the partition function, important for calculating the properties of a system at thermodynamic equilibrium. Different crystalline structures have different partition functions; the value calculated by Lieb is for an unrealistic model in which the water molecules or other elements are arranged in a square grid.[1] As well as for hydrogen bonds, analogous arrangements of elements with four neighbors, obeying the same two-in two-out rules, can occur in spin ice, and the same calculation of the partition function applies in that case.
The function also counts the number of 3-colorings of grid graphs, the number of nowhere-zero 3-flows in grid graphs, and the number of local flat foldings of the Miura fold.[4]
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads