2012/06/14 by David Galvin, Galvin, David · 1 citation
Computer Science · Mathematics · #05C30 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Dynamics and Fractals #math.CO #msc:05C30 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1206.3152
27 pages. Appeared in Israel Journal of Mathematics in 2003
arxiv created 2012/06/14 · openalex publication_date 2012/06/14 · arxiv updated 2012/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Write \cal F for the set of homomorphisms from \0,1\d to \bf Z which send \underline0 to 0 (think of members of \cal F as labellings of \0,1\d in which adjacent strings get labels differing by exactly 1), and \cal Fi for those which take on exactly i values. We give asymptotic formulae for |\cal F| and |\cal Fi|. In particular, we show that the probability that a uniformly chosen member \bf f of \cal F takes more than five values tends to 0 as d → ∞. This settles a conjecture of J. Kahn. Previously, Kahn had shown that there is a constant b such that \bf f a.s. takes at most b values. This in turn verified a conjecture of I. Benjamini \em et al., that for each t > 0, \bf f a.s. takes at most td values. Determining |\cal F| is equivalent both to counting the number of rank functions on the Boolean lattice 2[d] (functions f \colon 2[d] \longrightarrow \bf N satisfying f(∅)=0 and f(A) ≤ f(A ∪ x) ≤ f(A)+1 for all A ∈ 2[d] and x ∈ [d]) and to counting the number of proper 3-colourings of the discrete cube (i.e., the number of homomorphisms from \0,1\d to K3, 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.