Home » Subject » Graph Theory » Coloring » Vertex coloring

Counting 3-colorings of the hex lattice

Importance: Medium ✭✭
Author(s): Thomassen, Carsten
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords: coloring
Lieb's Ice Constant
tiling
torus
Recomm. for undergrads: no
Posted by: mdevos
on: July 5th, 2008
Problem   Find $ \lim_{n \rightarrow \infty} (\chi( H_n , 3)) ^{ 1 / |V(H_n)| } $.

We'll begin by putting in place the necessary notation. Let $ {\mathcal T} $ be the regular triangular tiling of the plane. For every $ n \ge 1 $ there is a regular map which triangulates the torus, denoted $ T_n $, which may be obtained from a regular hexagonal piece of $ {\mathcal T} $ of side-length $ n $ by identifying points on opposite edges of this hexagon. Let $ H_n $ be the dual of $ T_n $ (on the torus). Then $ H_n $ is a regular map on the torus - a hexagonal tiling. One last definition: for any graph $ G $ and any positive integer $ k $ we let $ \chi(G,k) $ denote the number of proper $ k $-coloring of $ G $.

A famous theorem of Lieb [L] shows that $ \lim_{n \rightarrow \infty} (\chi(Q_n,3))^{1 / |V(Q_n)|} = (\frac{4}{3})^{3/2} $ where $ Q_n $ denotes the $ n \times n $ quadrangulation of the torus. This theorem is usually stated in terms of Eulerian orientations, and is of interest to physicists as the constant $ (\frac{4}{3})^{3/2} $ (called Lieb's Ice Constant) determines the "residual entropy for square ice".

Thomassen proved that every planar graph $ G $ with girth $ \ge 5 $ has exponentially many proper 3-colorings. More precisely, he showed that $ (\chi(G,3))^{ 1 / |V(G)| } \ge 2 ^{1 / 10000} $. This gives a lower bound on the limit in the above problem (assuming it exists).

Bibliography

[L] E. H. Lieb, Exact Solution of the Problem of the Entropy of Two-Dimensional Ice. Phys. Rev. Lett. 18, 692-694, 1967.


* indicates original appearance(s) of problem.
add new comment