Open Problem Garden

Importance: Medium ✭✭

Author(s):

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

Open Problem Garden

Bibliography

Reply

Navigate

Recent Activity