Top Qs
Timeline
Chat
Perspective

Lieb's square ice constant

Mathematical constant used in combinatorics From Wikipedia, the free encyclopedia

Lieb's square ice constant
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.

Quick Facts Representations, Decimal ...
Remove ads
Thumb
An Eulerian orientation of a 4×4 periodic grid graph. The orientation (assignment of a direction to the edges of an undirected graph) is Eulerian because every vertex has equally many edges entering and leaving.

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

Loading content...
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads