318 Hanes Hall, CB #3260 Chapel Hill, NC 27599-3260
919-962-1329
Loading Events

STOR Colloquium: Louigi Addario-Berry, McGill University

April 30, 2018 @ 3:30 pm - 4:30 pm

Louigi Addario-Berry
McGill University

 

Assumptionless bounds for Galton-Watson trees and

random combinatorial trees.

 

Let T be any Galton-Watson tree. Write vol(T) for the volume of T (the number of nodes), ht(T) for the height of T (the greatest distance of any node from the root) and wid(T) for the width of T (the greatest number of nodes at any level). We study the relation between vol(T), ht(T) and wid(T).

 

In the case when the offspring distribution p = (p_i, i \geq 0) has mean one and finite variance, both ht(T) and wid(T) are typically of order vol(T)^{1/2}, and have sub-Gaussian upper tails on this scale (A-B, Devroye and Janson, 2013). Heuristically, as the tail of the offspring distribution becomes heavier, the tree T becomes “shorter and bushier”. I will describe a collection of work which can be viewed as justifying this heuristic in various ways In particular, I will explain how classical bounds on the Lévy’s concentration function for random walks may be used to show that the random variable ht(T)/wid(T) always has sub-exponential tails. I will also describe a more combinatorial approach to coupling random trees with different degree sequences which allows the heights of randomly sampled vertices to be compared.

 

 

Refreshments will be served at 3:00pm in the 3rd floor lounge of Hanes Hall

 

Share This Event

  • This event has passed.

Details

Date:
April 30, 2018
Time:
3:30 pm - 4:30 pm
Event Category:

Venue

Hanes 120