Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, March 28, 2006 - 4:00pm

David Galvin

University of Pennsylvania

Location

University of Pennsylvania

4N30

Assign integer labels to the vertices of the discrete d-dimensional cube subject to the constraint that adjacent vertices get labels differing by exactly 1. What is the range (the number of different labels used) of the assignment? It can be as small as 2 (assign 0 to all the strings with an even number of 1's, and 1 to all strings with an odd number of 1's) and as large as d+1 (assign k to all strings with exactly k 1's). But typically, the range should be o(d). Thus conjectured Benjamini, Haggstrom and Mossel. Their conjecture was confirmed by Kahn, who showed that the range is almost surely never more than some (large) constant. In this talk I will explain why the range is in fact almost surely never more than 5, and say why the problem is related to counting rank functions, proper 3-colourings and independent sets in the cube.