Mossel
Le Jeudi 30 Septembre 1999 à 14h30
au LRI, Salle 101
Université Hébraïque de Jérusalem et LRI
On random graph homomorphisms into Z
Résumé/Abstract :
The study of Lipschitz functions on graphs and metric spaces is rather
advanced. The uniform measure on graph homomorphisms into Z provides
a model for looking at typical Lipschitz functions.
Given a bipartite connected finite graph G=(V,E) and a vertex
v
in V, we consider the uniform
probability measure on the set of graph homomorphisms
f: V --> Z satisfying f(v)=0.
This measure can be viewed as a G-indexed random walk on Z,
generalizing both the usual time-indexed random walk and tree-indexed random
walk. We will present several general inequalities for
G-indexed random walks, including an upper bound on fluctuations
implying that the distance d(f(u),f(v)) between f(u) and
f(v), is stochastically dominated by the distance to 0 of a simple
random walk on Z having run for d(u,v) steps.
We will also discuss various special cases, some conjectures and
algorithmic aspects of these models.
The talk is based on joint work with Itai Benjamini and Olle Haggstrom.