### Abstract

For given finite, connected, bipartite graph G = (V, E) with distinguished v_{0} ∈ V, set F = {f: V → Z|f(v_{0}) = 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}^{n} 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.

Original language | English (US) |
---|---|

Pages (from-to) | 189-201 |

Number of pages | 13 |

Journal | Israel Journal of Mathematics |

Volume | 124 |

DOIs | |

State | Published - Jan 1 2001 |

### All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Fingerprint Dive into the research topics of 'Range of cube-indexed random walk'. Together they form a unique fingerprint.

## Cite this

Kahn, J. (2001). Range of cube-indexed random walk.

*Israel Journal of Mathematics*,*124*, 189-201. https://doi.org/10.1007/BF02772616