Sannolikhet, statistik och kombinatorik: Cutting resilient networks

  • Datum:
  • Plats: Ångströmlaboratoriet 64119
  • Föreläsare: Xing Shi Cai (Uppsala)
  • Kontaktperson: Tony Johansson
  • Seminarium

Abstract: We define the (random) k-cut number of a rooted graph to model the difficulty of the destruction of a resilient network. The process is as the cut model of Meir and Moon except now a node must be cut k times before it is destroyed. The k-cut number of a path of length n, X_n, is a generalization of the concept of records in permutations. The first order terms of the expectation and variance of X_n, with explicit formula for the constant factors, are proved. We also show that X_n, after rescaling, converges in distribution to a limit. The k-cut numbers in some other graphs, in particular complete binary trees, will also be discussed.