We study the tree builder random walk (TBRW): a randomly growing tree, built by a walker as she is walking around the tree. Namely, at each time n, she adds a leaf to her current vertex with probability p_{n}=n^{-γ} where γ∈(0,1], (or some other sequence tending to zero) then moves to a uniform random neighbor on the possibly modified tree.

Thus, the model, depending on one’s point of view, is:

• a self-interacting random walk, in a dynamically evolving environment, or

• an evolving random tree built by the walker itself, as it walks around.

After presenting some results on the behavior of the walker, we show that for γ>2/3 the tree process at its

growth times, can be coupled with the Barabási-Albert preferential attachment tree model.

Hence, our TBRW-model is a local dynamics giving rise to the BA-model. The coupling also implies

that many properties known for the BA-model, such as diameter and degree distribution, can be

directly transferred to our TBRW-model.

This is joint work with G. Iacobelli (Rio de Janeiro), G. Pete (Budapest) and R. Ribeiro (Denver).

# Tree builder random walk

Időpont:

2023. 10. 12. 16:15

Hely:

H306

Előadó:

János Engländer (Boulder, CO)