The proper way to color a grid

Sun, 11/03/2018 - 12:00

We consider the task of coloring the vertices of a large discrete box in the integer lattice Z^d with q colors so that no two adjacent vertices are colored the same. In how many ways can this be done? How does a typical coloring look like? What is the proportion of proper colorings in which two opposite corners of the box receive the same color? Is it about one in q?

We discuss these questions and the way their answers depend on the dimension d and the number of colors q, presenting recent results with Yinon Spinka.

Motivations are provided from statistical physics (anti-ferromagnetic materials, square ice), combinatorics (proper colorings, independent sets) and the study of random Lipschitz functions on a lattice.