Range of cube-indexed random walk

DOI10.1007/BF02772616MaRDI QIDQ5951488zbMATH OpenOpenAlexFDO

Authors J. Kahn

Publication date 11 August 2003

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02772616

zbMATH Keywords

Hamming cuberandom graph homomorphismsrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Review text

For the Hamming cube \(G\), that is \(\{0,1\}^{n}\) with the usual adjacency, one denotes by \(\mathcal F\) the set of graph homomorphisms from \(G\) to \(\mathbb Z\) normalized to vanish at 0. The author proves that there is a fixed \(b\) such that if \(f\) is chosen uniformly from \(\mathcal F\), the probability that \(f\) takes more than \(b\) values is at most \(e^{-\Omega(n)}\) [see also a conjecture of \textit{I. Benjamini, O. Häggström} and \textit{E. Mossel}, J. Comb. Theory, Ser. B 78, No.~1, 86-114 (2000)].

Recommendations

• On random graph homomorphisms into \({\mathbb{Z}}\)
• On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
• An inequality for functions on the Hamming cube
• On the support of harmonic measure for the random walk
• A note on random homomorphism from arbitrary graphs to \(\mathbb{Z}\)

Cites work

• An entropy approach to the hard-core model on bipartite graphs
• Generalized rank functions and an entropy argument
• scientific article; zbMATH DE number 3586931 (Why is no real title available?)
• scientific article; zbMATH DE number 1495913 (Why is no real title available?)
• On random graph homomorphisms into \({\mathbb{Z}}\)
• Some intersection theorems for ordered sets and graphs

Cited in

(18)

• A note on random homomorphism from arbitrary graphs to \(\mathbb{Z}\)
• On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
• On random graph homomorphisms into \({\mathbb{Z}}\)
• Rigidity of 3-colorings of the discrete torus
• Graph-indexed random walks on pseudotrees
• Logarithmic variance for the height function of square-ice
• The number of 4-colorings of the Hamming cube
• Delocalization of uniform graph homomorphisms from \({\mathbb{Z}}^2\) to \({\mathbb{Z}} \)
• On the distribution of range for tree-indexed random walks
• Random mappings of scaled graphs.
• Rigidity of proper colorings of \(\mathbb{Z}^d \)
• Lipschitz functions on expanders are typically flat
• The diameter of a random subgraph of the hypercube
• \(H\)-colouring bipartite graphs
• Homomorphisms from the torus
• Lipschitz functions on weak expanders
• The number of colorings of the middle layers of the Hamming cube
• H-coloring tori

This page was built for publication: Range of cube-indexed random walk

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5951488)