MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEBuilding a Perfect Terrorist Organization par Victor Campos (Univ. Fed. do Ceara, Brazil)
Date : | 07/12/10 | Time : | 11h | Location : | Lagrange Gris |
A transversal in a rooted tree is any set of nodes that meets every path from the root to a leaf. Let c(T, k) denote the number of transversals of size k in a rooted tree T. Given rooted trees T and T' on n nodes, we write T > T' to mean that c(T, k) >= c(T', k) for all k = 1, 2, ..., n and that c(T, k) > c(T', k) for at least one of these values of k. In this case, we say that T' is more robust than T. We'll show some operations on trees that transform it into a more robust tree. We use these operations to show the structure of the unique most robust d-ary tree for any fixed d at least two. Throughout this talk, we relate rooted trees to the hierarchical structure of an organization and robustness of trees to robustness of a terrorist organization suffering disruption for our amusement (this was how this problem was first introduced to us). Next, we study a randomized variation of this problem. We study the probability E(T, p) of obtaining a transversal when we choose each node of T independently with probability p. We give upper and lower bounds for E(T, p) and then show that a random binary search trees achieves the upper bound asymtotically.
These results were obtained by myself together with V. Chvatal, L. Devroye and P. Taslakian.
Page des séminaires
|