PVSeminar

About 

PVSeminar YouTube channel

Past seminars

Upcoming seminars

 

  •  PVSeminar #35, 26 May 2022  / 17:00 AEST 

Cecilia Holmgren (Uppsala University, Sweden): Split trees — A unifying model for many important random trees of logarithmic height

Abstract: Split trees were introduced by Devroye (1998) as a novel approach for unifying important random trees of logarithmic height. They are interesting not least because of their usefulness as models of sorting algorithms in computer science; for instance the well-known Quicksort algorithm (introduced by Hoare [1960]) can be depicted as a binary search tree (which is one example of a split tree). In 2012, I introduced renewal theory as a novel approach for studying split trees*. This approach has proved to be highly useful for investigating such trees and has allowed several general results valid for all split trees. In my presentation, I will introduce split trees and illustrate some results for this large class of random trees, e.g. on the size, total path length, number of cuttings and number of inversions as well as on the size of the giant component and other clusters after bond percolation.
*Holmgren C., Novel characteristic of split trees by use of renewal theory. Electronic Journal of Probability 2012.

Zoom link:  https://unimelb.zoom.us/j/86283331377?pwd=cjgyaElERWt6R3MvTGFDWW9pK3JvUT09

Password: 750965

PDF file with slides: maybe here

About PVSeminar

This online probability seminar is an initiative of the Probability Victoria group, inspired by the example of the One World Probability seminar.

One World Probability seminar was a great initiative. From our time zone (UTC+10/11) and other countries in East Asia and Oceania perspective, its main drawback is that it is run around midnight. So we thought it would be great to have an additional online seminar run at a time more suitable for our region (but also acceptable for some other parts of the world).

The seminar is supposed to be run on Zoom weekly (or fortnightly, depending on the availability of speakers), on Thursdays, usually starting at 17:00 or 19:00 AEST (Australian East Standard Time, UTC+10, the timezone of Melbourne & Sydney) or AEDT (Australian Eastern Daylight Time, UTC+11, the daylight saving timezone of Melbourne & Sydney). Please check the time difference between your timezone and AEST/AEDT — and beware of the switches to/from daylight saving time that tend to occur from time to time.

If you sign to our seminar mailing list, you will receive a Zoom link to the webinar a few days before the talk. This link will also appear on this Website. To subscribe to the mailing list, please send an empty email (completely empty, no automatic signatures etc.) with the subject “subscribe pvseminar [your name]” to probvicseminar(at)gmail.com

To leave the mailing list, send an empty email (completely empty, no automatic signatures, etc.) with the subject “unsubscribe pvseminar [your name]” to probvicseminar(at)gmail.com

PVSeminar board

Kostya Borovkov (founder & main seminar series organizer)

Back to top