[ABE-L] Seminário de Probabilidade - 16 de outubro - Targeted cutting of random recursive trees - Sergio I. López (UNAM)-

[Maria Eulalia Vares]

Dear colleagues,

Our next seminar will be held on Monday, *October 16*, from *3:30 p.m. to
4:30 p.m*. (Rio de Janeiro local time).  This meeting will take place at
room *C116 - Bloco C - CT** – Instituto de Matemática – UFRJ. *There will
be no transmission online.



Speaker: * Sergio I. López  (**Universidad Nacional Autónoma de México*)

Title: Targeted cutting of random recursive trees

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

http://www.dme.ufrj.br/?page_id=3398

Sincerely,

Organizers: Giulio Iacobelli e Maria Eulalia Vares
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://lists.ime.usp.br/pipermail/abe/attachments/20231010/cb61990c/attachment.htm>