Nonuniform recursive trees with vertex attraction depending on their labels
type: Item
instance of: scholarly article
title: Nonuniform recursive trees with vertex attraction depending on their labels
zbMATH Open document ID: 1447.05182
author: Marek Gałązka
author: Krzysztof Krzywdziński
author: Jerzy Szymański
author: Rafał Witkowski
published in: Functiones et Approximatio. Commentarii Mathematici
publication date: 2020-07-29T00:00:00Z
full work available at URL: https://projecteuclid.org/euclid.facm/1592618415
review text: The paper under review proposes a non-uniform model of random recursive trees (recall that a tree on vertex set \([n]=\{1,2,\ldots, n\}\) with root vertex 1 is said to be recursive if, for all \(2\leq k\leq n\), the labels of the vertices on the unique path from 1 to \(k\) are an increasing sequence). A model of random recursive trees is a distribution on the set of all recursive tress on \([n]\). The model introduced makes the choice of the parent \(i\) for the new node -- say \(n\) -- depends on the label of the parent \(i\), say it is \(p_{ni}\), where \(p_{ni}>0\) for all \(1\leq i\leq n-1\) and \(\sum_{i=1}^{n-1}p_{ni}=1\). The models where the attraction of vertices is proportional to their labels (i.e. \(p_{ni}=2i/(n(n-1))\)) and where the attraction is proportional to \(n-i\) (i.e. \(p_{ni}=2(n-i)/(n(n-1))\)) are of particular importance. The main results, often unsurprisingly relying on analysis of recurrent sequences, are about the degrees of vertices in the model.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C07
zbMATH DE Number: 7225513
zbMATH Keywords: recursive tree
zbMATH Keywords: random tree
zbMATH Keywords: vertex degree
reviewed by: David B. Penman
MaRDI profile type: Publication
OpenAlex ID: W3036951067
cites work: Q5668821
cites work: Q3682518
cites work: The degree sequence of a scale-free random graph process
cites work: Depth properties of scaled attachment random recursive trees
cites work: Asymptotic Analysis of Hoppe Trees
cites work: Q4940321
cites work: On the structure of random plane‐oriented recursive trees and their branches
cites work: Q3137211
cites work: Q3789583
cites work: Concentration of vertex degrees in a scale‐free random graph process
DOI: 10.7169/FACM/1882
description: scientific article; zbMATH DE number 7225513