Title: Targeted cutting of random recursive trees.
Speaker: Sergio I. López  (Universidad Nacional Autónoma de México)
Date: 16/10/2023
Horário: 3:30 p.m. to 4:30 p.m. (Rio de Janeiro local time)
Local: C116 - Bloco C - CT – Instituto de Matemática – UFRJ. There will be no transmission online.

Abstract: Increasing trees are rooted trees, where each vertex has a unique label and the labels along paths away from the root are in increasing order. A Random recursive tree on ? vertices (abbreviated as RRTs) is a tree chosen uniformly at random from the set of increasing trees with vertex labels {1,…,?}. The idea of cutting random recursive trees was introduced by Meir and Moon in 1974. They studied the following procedure: Start with a random recursive tree on ? vertices. Choose an edge at random and remove it, along with the cut subtree that does not contain the root. Repeat until the remaining tree consists only of the root; at which point, we say that the tree has been deleted.

Let X be the number of edge removals needed to delete a RRT with ? vertices. The random variable X has been thoroughly studied and analogous variables under distinct models of random trees have been analyzed; in particular, X grows asymptotically as ? ln(?). In this talk we propose and study a method for cutting down a random recursive tree that focuses on its largest degree vertices. Enumerate the vertices of a random recursive tree of size ? according to a decreasing order of their degrees. The targeted, vertex-cutting process is performed by sequentially removing vertices according to that order and keeping only the subtree containing the root after each removal. The algorithm ends when the root is picked to be removed.

Joint work with Laura Eslava and Marco L. Ortiz.

More complete information about the seminars can be found at HERE

Sincerely,

Organizers: Giulio Iacobelli e Maria Eulalia Vares