Tail bounds for the height and width of a random tree with a given degree sequence

Details Tail bounds for the height and width of a random tree with a given degree sequence Tail bounds for the height and width of a random tree with a given degree sequence

2011-09-21

arxiv.org/abs/1109.4626v1

Mathematics

Probability

8 pages

Scientific paper

Fix a sequence c=(c_1,...,c_n) of non-negative integers with sum n-1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v_1,...,v_n so that for each 1 <= i <= n, v_i has exactly c_i children. Let T be a plane tree drawn uniformly at random from among all plane trees with child sequence c. In this note we prove sub-Gaussian tail bounds on the height (greatest depth of any node) and width (greatest number of nodes at any single depth) of T. These bounds are optimal up to the constant in the exponent when c satisfies c_1^2+...+c_n^2=O(n); the latter can be viewed as a "finite variance" condition for the child sequence.

Affiliated with

Also associated with

No associations

Rating

Tail bounds for the height and width of a random tree with a given degree sequence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tail bounds for the height and width of a random tree with a given degree sequence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tail bounds for the height and width of a random tree with a given degree sequence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-258209