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
| 
