The proper way to color a grid

Speaker
Prof. Ron Peled, Tel-Aviv University
Date
11/03/2018 - 13:00 - 12:00Add to Calendar 2018-03-11 12:00:00 2018-03-11 13:00:00 The proper way to color a grid 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. Mathematics Colloquium Room 201, Building 216 אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Mathematics Colloquium Room 201, Building 216
Abstract

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.

Last Updated Date : 06/03/2018