On homomorphisms from the Hamming cube to Z

WriteF for the set of homomorphisms from {0, 1} ^d toZ which send0 to 0 (think of members ofF as labellings of {0, 1} ^d in which adjacent strings get labels differing by exactly 1), andF ₁ for those which take on exactlyi values. We give asymptotic formulae for |F| and |F|. In particular, we show that the probability that a uniformly chosen memberf ofF takes more than five values tends to 0 asd→∞. This settles a conjecture of J. Kahn. Previously, Kahn had shown that there is a constantb such thatf a.s. takes at mostb values. This in turn verified a conjecture of I. Benjaminiet al., that for eacht>0,f a.s. takes at mosttd values. Determining |F| is equivalent both to counting the number of rank functions on the Boolean lattice 2^d] (functionsf: 2^d]→N satisfyingf( ) andf(A)≤f(A∪x)≤f(A)+1 for allA∈2^d] andx∈d]) and to counting the number of proper 3-colourings of the discrete cube (i.e., the number of homomorphisms from {0, 1} ^d toK ₃, the complete graph on 3 vertices). Our proof uses the main lemma from Kahn’s proof of constant range, together with some combinatorial approximation techniques introduced by A. Sapozhenko. Research supported by a Graduate School Fellowship from Rutgers University.