Premium
Random cutting and records in deterministic and random trees
Author(s) -
Janson Svante
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20086
Subject(s) - random tree , mathematics , tree (set theory) , combinatorics , random binary tree , mathematical proof , struct , k ary tree , discrete mathematics , random graph , tree structure , computer science , binary tree , artificial intelligence , geometry , graph , motion planning , robot , programming language
We study random cutting down of a rooted tree and show that the number of cuts is equal (in distribution) to the number of records in the tree when edges (or vertices) are assigned random labels. Limit theorems are given for this number, in particular when the tree is a random conditioned Galton–Watson tree. We consider both the distribution when both the tree and the cutting (or labels) are random and the case when we condition on the tree. The proofs are based on Aldous' theory of the continuum random tree. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006