Probability Seminar

Nov 17, 2026   2:00 - 3:00 pm  
2018 Campus Instructional Facility
Sponsor
Department of Mathematics
Speaker
Janos Englander (U Colorado, Boulder)
Views
71

Title: Random graph or random walk?

Abstract: We study the "tree builder random walk:" 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, then moves to a uniform random neighbor on the possibly modified tree. We show that, in the appropriate regime, the tree process at its growth times, after a random finite number of steps, can be coupled to be identical to the Barabási–Albert preferential attachment tree model. Thus, 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 e.g. diameter and degree distribution, can be directly transferred to our TBRW-model, extending previous results. Time permitting, we will discuss the behavior of the walker and more general leaf-distributions as well.

This is joint work with G. Iacobelli (Rio), G. Pete (Budapest) and R. Ribeiro (Rio). The talk is based on the recent papers - "Recurrence, transience and degree distribution for the tree builder random walk,”  Engländer; Iacobelli; Ribeiro, Ann. Inst. Henri Poincaré Probab. Stat. 61 (2025), no. 4, and "Structural results for the tree builder random walk,"  Engländer; Iacobelli; Pete; Ribeiro, Ann. Appl. Probab. 35 (2025), no. 2.

link for robots only