Range of cube-indexed random walk

For given finite, connected, bipartite graph G = (V, E) with distinguished v₀ ∈ V, set F = {f: V → Z|f(v₀) = 0, {x,y} ∈ E ⇒ |f(x) - f(y)| = 1}. Our main result says there is a fixed b so that when G is a Hamming cube ({0, 1}ⁿ with the usual adjacency), and f is chosen uniformly from F, the probability that f takes more than 6 values is at most e^-Ω(n). This settles in a very strong way a conjecture of I. Benjamini, O. Häggström and E. Mossel [2]. The proof is based on entropy considerations and a new log-concavity result.