4 papers
Temporal connectivity of Random Geometric Graphs
Anna Brandenberger, Serte Donderwinkel, Céline Kerriou +2
A temporal random geometric graph is a random geometric graph in which all edges are endowed with a uniformly random time-stamp, representing the time of interaction between vertic…
Random friend trees
Louigi Addario Berry, Simon Briend, Luc Devroye +3
We study a random recursive tree model featuring complete redirection called the random friend tree and introduced by Saramäki and Kaski. Vertices are attached in a sequential mann…
Universal height and width bounds for random trees
Louigi Addario-Berry, Anna Brandenberger, Jad Hamdan +1
We prove non-asymptotic stretched exponential tail bounds on the height of a randomly sampled node in a random combinatorial tree, which we use to prove bounds on the heights and w…
Hipster random walks
Louigi Addario-Berry, Hannah Cairns, Luc Devroye +2
We introduce and study a family of random processes on trees we call hipster random walks, special instances of which we heuristically connect to the min-plus binary trees introduc…